Recientemente, el sitio web oficial de la Copa Lanqiao ha publicado los problemas de la 15ª edición. Publicaré las soluciones lo antes posible, y los problemas no resueltos se añadirán más tarde.
Secuencia Numérica
Un problema de búsqueda bastante complejo que requiere atención para evitar errores. Durante la competencia, no pude resolverlo, y después de que los problemas se publicaron oficialmente, necesité dos intentos para pasar las pruebas de ejemplo.
Enunciado del problema:
El camino comienza en (1,1), y el valor en el siguiente paso debe ser exactamente 1 mayor que el valor actual. Si supera k, se aplica módulo. Además, no se pueden cruzar caminos, como se menciona en el cuarto punto: en una cuadrícula de 2x2, después de moverse de 1 a 3, no se puede mover de 2 a 4 ni de 4 a 2. Cada celda solo se puede visitar una vez.
Enfoque:
Debido a que los datos son pequeños y hay restricicones especiales para evitar caminos redundantes, podemos usar una búsqueda exhaustiva. Hay muchos detalles específicos que se pueden entender mejor a través del código.
Código:
#include<iostream>
#include<queue>
#include<map>
#include<set>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<stack>
#include<numeric>
#include<vector>
using namespace std;
using ll = long long;
const int mod = 1e9 + 7, MAXN = 15;
int dimension, valor_max;
int tablero[MAXN][MAXN];
bool visitado[MAXN][MAXN];
bool bloqueado[MAXN][MAXN][MAXN][MAXN];
// Direcciones de movimiento: 8 posibles
const int direcciones_x[] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int direcciones_y[] = {0, 1, 1, 1, 0, -1, -1, -1};
string mejor_camino = "999999999";
bool dentro_del_mapa(int x, int y) {
return (x >= 1 && x <= dimension && y >= 1 && y <= dimension);
}
void busqueda_en_profundidad(int x, int y, int contador, string camino_actual) {
// Si llegamos al destino y hemos visitado todas las celdas
if (x == dimension && y == dimension && camino_actual.length() == dimension * dimension - 1) {
if (camino_actual < mejor_camino) {
mejor_camino = camino_actual;
}
return;
}
// Exploramos todas las 8 direcciones posibles
for (int i = 0; i < 8; i++) {
int nx = x + direcciones_x[i];
int ny = y + direcciones_y[i];
// Verificamos si la nueva posición está dentro del mapa
if (!dentro_del_mapa(nx, ny)) continue;
// Verificamos si el valor en la celda siguiente es correcto
if (tablero[nx][ny] != (contador + 1) % valor_max) continue;
// Verificamos si la celda ya ha sido visitada
if (visitado[nx][ny]) continue;
if (i % 2 == 1) { // Movimiento diagonal
if (i == 1 && !bloqueado[x][y+1][x-1][y] && !bloqueado[x-1][y][x][y+1]) {
visitado[nx][ny] = true;
bloqueado[x][y+1][x-1][y] = bloqueado[x-1][y][x][y+1] = true;
bloqueado[x][y][nx][ny] = bloqueado[nx][ny][x][y] = true;
string nuevo_camino = camino_actual + to_string(i);
busqueda_en_profundidad(nx, ny, tablero[nx][ny], nuevo_camino);
// Retrocedemos
bloqueado[x][y][nx][ny] = bloqueado[nx][ny][x][y] = false;
bloqueado[x][y+1][x-1][y] = bloqueado[x-1][y][x][y+1] = false;
visitado[nx][ny] = false;
}
// Similar para las otras direcciones diagonales (3, 5, 7)
// ... (código omitido por brevedad)
} else { // Movimiento horizontal o vertical
visitado[nx][ny] = true;
string nuevo_camino = camino_actual + to_string(i);
busqueda_en_profundidad(nx, ny, tablero[nx][ny], nuevo_camino);
visitado[nx][ny] = false;
}
}
}
void resolver_caso() {
cin >> dimension >> valor_max;
for (int i = 1; i <= dimension; i++) {
for (int j = 1; j <= dimension; j++) {
cin >> tablero[i][j];
}
}
string inicio = "";
visitado[1][1] = true;
busqueda_en_profundidad(1, 1, tablero[1][1], inicio);
cout << (mejor_camino == "999999999" ? "-1" : mejor_camino) << endl;
}
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int casos = 1;
// cin >> casos;
while (casos--) {
resolver_caso();
}
return 0;
}
Problema de Saludos
Enunciado del problema:
Un total de 5050 personas asistieron a esta conferencia. Cada persona debe saludar a todos los demás exactamente una vez. ¿Cuál es el número mínimo de saludos necesarios?
Enfoque:
Podemos usar una matriz bidimensional. Con dos bucles anidados, marcamos que la persona i ha saludado a j (matriz[i][j] = 1) y que j ha sido saludado por i (matriz[j][i] = 2). Si matriz[i][j] ya es 2, no necesitamos cambiarla a 1. Finalmente, contamos cuántos 1 hay en la matriz.
Código:
#include<iostream>
#include<vector>
using namespace std;
void resolver() {
int total_personas = 5050;
vector<vector<int>> matriz(total_personas + 1, vector<int>(total_personas + 1, 0));
int saludos = 0;
for (int i = 1; i <= total_personas; i++) {
for (int j = i + 1; j <= total_personas; j++) {
if (matriz[i][j] == 0 && matriz[j][i] == 0) {
matriz[i][j] = 1;
matriz[j][i] = 2;
saludos++;
}
}
}
cout << saludos << endl;
}
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int casos = 1;
while (casos--) {
resolver();
}
return 0;
}
Números Buenos
Enfoque
Almacenamos los números como cadenas y verificamos cada dígito. Dado que el rango de datos no es grande (solo 10^7), podemos recorrer directamente del 1 a n. Los números pares no pueden ser "buenos", por lo que podemos omitirlos.
Código:
#include<iostream>
#include<string>
using namespace std;
bool es_bueno(const string& num) {
string invertido = num;
reverse(invertido.begin(), invertido.end());
for (int i = 0; i < invertido.length(); i++) {
int digito = invertido[i] - '0';
int posicion = i + 1;
if (digito % 2 != posicion % 2) {
return false;
}
}
return true;
}
void resolver() {
int limite;
cin >> limite;
int contador = 0;
for (int i = 1; i <= limite; i++) {
if (es_bueno(to_string(i))) {
contador++;
}
}
cout << contador << endl;
}
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int casos = 1;
while (casos--) {
resolver();
}
return 0;
}
Rebote de Esfera
Enfoque
Para que la esfera regrese al punto de partida, la única forma de cambiar de dirección es chocar con la pared derecha (un "cambio de dirección" significa que el movimiento se vuelve negativo, asumiendo que la dirección inicial es positiva). Por lo tanto, la dirección horizontal y vertical final deben ser múltiplos pares de los valores dados (233333 y 343720), y la proporción debe ser 15:17. Una vez que encontramos estas reglas, podemos usar fuerza bruta para encontrar la solución.
Código:
#include<iostream>
#include<iomanip>
using namespace std;
void resolver() {
const long long radio = 233333, ancho = 343720;
double distancia_minima = 1e18;
// Buscamos múltiplos pares para ambas dimensiones
for (int i = 2; i <= 10000; i += 2) { // vertical
for (int j = 2; j <= 10000; j += 2) { // horizontal
if (15 * radio * j == 17 * ancho * i) {
double distancia = sqrt((radio * j) * (radio * j) + (ancho * i) * (ancho * i));
if (distancia < distancia_minima) {
distancia_minima = distancia;
}
}
}
}
cout << fixed << setprecision(2) << distancia_minima << endl;
}
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int casos = 1;
while (casos--) {
resolver();
}
return 0;
}
Formato R
Enfoque
Se nos da un número decimal y un exponente n. Debemos multiplicar este número por 2^n, redondeando el resultado al entero más cercano. Podemos usar aritmética de alta precisión para simular este proceso. Multiplicar por 2^n significa que debemos multiplicar el número por 2, n veces. El bucle n veces multiplicando por 2 es suficiente. Los detalles de la aritmética de alta precisión se implementan como si estuviéramos calculando manualmente.
Código:
#include<iostream>
#include<string>
#include<cmath>
using namespace std;
void resolver() {
int exponente;
cin >> exponente;
string numero;
cin >> numero;
// Invertimos la cadena para facilitar los cálculos
reverse(numero.begin(), numero.end());
// Multiplicamos por 2, n veces
while (exponente--) {
int acarreo = 0;
for (int i = 0; i < numero.length(); i++) {
if (numero[i] == '.') continue;
int digito = numero[i] - '0';
int nuevo_digito = (digito * 2) + acarreo;
acarreo = nuevo_digito / 10;
numero[i] = (nuevo_digito % 10) + '0';
}
// Si necesitamos añadir un dígito al final
if (acarreo > 0) {
if (numero.length() > 2 && numero[numero.length() - 1] == '0' &&
numero[numero.length() - 2] == '.') {
numero[numero.length() - 1] = '1';
} else {
numero += (acarreo + '0');
}
}
}
// Redondeo al entero más cercano
int pos_punto = -1;
for (int i = 0; i < numero.length(); i++) {
if (numero[i] == '.') {
pos_punto = i;
break;
}
}
if (pos_punto != -1) {
int acarreo = 0;
if (numero[pos_punto - 1] >= '5') {
acarreo = 1;
}
// Procesamos el redondeo
for (int i = pos_punto - 1; i >= 0 && acarreo > 0; i--) {
if (numero[i] == '.') continue;
if (numero[i] < '9') {
numero[i]++;
acarreo = 0;
} else {
numero[i] = '0';
acarreo = 1;
}
}
if (acarreo > 0) {
numero = "1" + numero;
}
// Eliminamos la parte decimal
numero.erase(pos_punto, numero.length() - pos_punto);
}
// Invertimos de vuelta y mostramos el resultado
reverse(numero.begin(), numero.end());
cout << numero << endl;
}
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int casos = 1;
while (casos--) {
resolver();
}
return 0;
}
Tira y Afloja
Enfoque
Los datos no son grandes, por lo que podemos usar fuerza bruta:
Enumeramos i y j, que representan los puntos finales e iniciales de los dos equipos. Sabemos que si la fuerza de un equipo es mayor que la del otro, no podemos agregar más personas a ese equipo, ya que solo haría que la diferencia sea mayor. En tales casos, debemos aumentar el número de personas en el otro equipo. En resumen, es una solución bastante directa.
Código:
#include<iostream>
#include<vector>
#include<climits>
using namespace std;
void resolver() {
int n;
cin >> n;
vector<long long> fuerzas(n + 1);
for (int i = 1; i <= n; i++) {
cin >> fuerzas[i];
}
long long diferencia_minima = LLONG_MAX;
// Enumeramos todos los puntos de división posibles
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
int izq = i - 1, der = j + 1;
long long suma_izq = fuerzas[i], suma_der = fuerzas[j];
diferencia_minima = min(diferencia_minima, abs(suma_der - suma_izq));
// Expandimos hacia la izquierda y derecha
while (izq >= 1 && der <= n) {
if (suma_izq > suma_der) {
suma_der += fuerzas[der++];
} else {
suma_izq += fuerzas[izq--];
}
diferencia_minima = min(diferencia_minima, abs(suma_der - suma_izq));
}
// Completamos el lado izquierdo si es necesario
while (izq >= 1) {
suma_izq += fuerzas[izq--];
diferencia_minima = min(diferencia_minima, abs(suma_der - suma_izq));
}
// Completamos el lado derecho si es necesario
while (der <= n) {
suma_der += fuerzas[der++];
diferencia_minima = min(diferencia_minima, abs(suma_der - suma_izq));
}
}
}
cout << diferencia_minima << endl;
}
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int casos = 1;
while (casos--) {
resolver();
}
return 0;
}
Combinación de Gemas
Este es un problema de teoría de números. Personalmente no pude resolverlo, así que lo dejaré para más adelante cuando tenga tiempo.
Escalada de Montaña
Recuerdo que había un problema sobre escalada de montaña, pero no se publicó en la base de datos oficial del problema. No estoy seguro de qué pasó. El problema es el siguiente:
(El problema se omite por brevedad)
El enfoque general es usar un algoritmo codicioso con una cola de prioridad. Ordenamos las montañas por tamaño, colocando las más grandes en la parte superior de la cola. En cada paso, calculamos qué magia (reducción de altura o eliminación) da el mayor beneficio y la aplicamos. Finalmente, mostramos el resultado.