Esta fue mi primera participación en un concurso con premios. Después de un año sin programar activamente, mis habilidades estaban bastante oxidadas. Decidí utilizar C++, un lenguaje que había aprendido recientemente, y casi pierdo todas las pruebas.
Problema 1: El genio matemático
Se define una función D(n) que representa la suma de todos los dígitos de un número. El problema consiste en encontrar todos los valores x en el intervalo [l, r] que satisfagan la ecuación D(x)^k * p + q = x. Los resultados deben imprimirse en orden ascendente.
La solución consiste en notar que D(x) solo puede tomar valores entre 0 y 81, ya que el número máximo con 18 dígitos tiene suma de dígitos máxima de 81. En lugar de iterar sobre todos los posibles x, iteramos sobre todos los valores posibles de D(x), calculmaos el valor resultante y verificamos si su suma de dígitos coincide.
Es importante utilizar variables de tipo long long para evitar desbordamientos.
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
long long exponente, coefA, coefB, limiteInf, limiteSup;
long long resultados[10000];
int cantidad;
long long sumarDigitos(long long numero){
long long suma = 0;
while(numero > 0){
suma += numero % 10;
numero = numero / 10;
}
return suma;
}
long long potencia(long long base, long long exp){
long long resultado = 1;
long long contador;
for(contador = 1; contador <= exp; ++contador){
resultado = resultado * base;
}
return resultado;
}
int main(){
scanf("%lld%lld%lld%lld%lld", &exponente, &coefA, &coefB, &limiteInf, &limiteSup);
long long indice;
cantidad = 0;
for(indice = 0; indice <= 81; ++indice){
long long candidato;
candidato = potencia(indice, exponente) * coefB + coefA;
if((candidato >= 0) && (sumarDigitos(candidato) == indice) &&
(candidato >= limiteInf) && (candidato <= limiteSup)){
resultados[++cantidad] = candidato;
}
}
sort(resultados + 1, resultados + 1 + cantidad);
printf("%lld\n", cantidad);
for(indice = 1; indice <= cantidad; ++indice){
printf("%lld ", resultados[indice]);
}
return 0;
}
Problema 1Problema 2: Estampado perfecto
Se proporciona un contorno y un sello. La pregunta es: ¿cuántas formas existen para que un borde del sello (superior o inferior) coincida con el contour? El sello puede rotarse 180 grados.
La observación clave es que solo importa la diferencia de altura entre celdas adyacentes. Por lo tanto, extraemos las diferencias entre elementos consecutivos y aplicamos el algoritmo KMP四次 veces, considerando todas las rotaciones posibles y el caso cuando el sello está plano. También debemos manejar el caso especial donde n = 1.
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
int longitudSello, longitudContorno;
int diferenciasSello[1000100];
int diferenciasContorno[1000100];
int siguiente[1000100];
int conteo;
int ejecutarKMP(){
int i, j;
// Calcular diferencias del sello
for(i = longitudSello - 1; i > 0; --i){
diferenciasSello[i] = diferenciasSello[i-1] - diferenciasSello[i];
}
// Construir tabla de fallos
siguiente[1] = 0;
siguiente[0] = 0;
for(i = 2; i < longitudSello; ++i){
j = siguiente[i-1];
while((j > 0) && (diferenciasSello[i] != diferenciasSello[j+1])){
j = siguiente[j];
}
if(diferenciasSello[i] == diferenciasSello[j+1]){
siguiente[i] = j + 1;
} else {
siguiente[i] = 0;
}
}
// Búsqueda KMP
i = 0;
j = 0;
while(j < longitudContorno - 1){
if(diferenciasSello[i+1] == diferenciasContorno[j+1]){
++i;
++j;
} else if(i == 0){
++j;
} else {
i = siguiente[i];
}
if(i == longitudSello - 1){
++conteo;
i = siguiente[i];
}
}
// Restaurar diferencias del sello
for(i = 1; i < longitudSello; ++i){
diferenciasSello[i] = diferenciasSello[i-1] - diferenciasSello[i];
}
return 0;
}
int intercambio(int &a, int &b){
int temp;
temp = a;
a = b;
b = temp;
return 0;
}
int main(){
int i;
conteo = 0;
scanf("%d%d", &longitudSello, &longitudContorno);
for(i = 0; i < longitudSello; ++i){
scanf("%d", &diferenciasSello[i]);
}
for(i = 0; i < longitudContorno; ++i){
scanf("%d", &diferenciasContorno[i]);
}
if(longitudSello == 1){
printf("%d\n", 4 * longitudContorno);
return 0;
}
// Calcular diferencias del contorno
for(i = longitudContorno - 1; i > 0; --i){
diferenciasContorno[i] = diferenciasContorno[i-1] - diferenciasContorno[i];
}
// Primera orientación
ejecutarKMP();
// Invertir y negar el sello
for(i = 0; i < longitudSello/2; ++i){
intercambio(diferenciasSello[i], diferenciasSello[longitudSello - i - 1]);
}
for(i = 0; i < longitudSello; ++i){
diferenciasSello[i] = -diferenciasSello[i];
}
ejecutarKMP();
// Tercera orientación (todo ceros)
for(i = 0; i < longitudSello; ++i){
diferenciasSello[i] = 0;
}
ejecutarKMP();
// Cuarta orientación
ejecutarKMP();
printf("%d\n", conteo);
return 0;
}
Problema 2Problema 3: El desafío del jardín fantasma
Se proporcionan dos árboles. Podemos seleccionar un nodo en cada árbol y conectarlos con una arista de longitud t. Se pide:
- Encontrar el valor mínimo posible del camino más largo después de conectar los árboles.
- Calcular la longitud esperada del camino más largo.
Para la primera parte, usamos programación dinámica en árboles para calcular la cadena más larga desde cualquier nodo. Tomamos la cadena más pequeña de cada árbol, las sumamos y agregamos t. También debemos considerar el caso donde el camino más largo no pasa por la nueva arista, que es simplemente la cadena más larga original de cualquiera de los árboles. Tomamos el máximo de estas dos opciones.
Para la segunda parte, necesitamos calcular la esperanza matemática. Generamos todas las combinaciones posibles, calculamos el máximo entre la cadena más larga y la suma de las cadenas de ambos árboles. Después de ordenar las cadenas más largas de ambos árboles, el problema se reduce a calcular la suma de máximos. Usando un enfoque con prefijos, podemos calcular eficientemente esta suma.
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
long long nodosA, nodosB, longitudEnlace, aristas;
long long siguiente[400400];
long long destino[400400];
long long pesoArista[400400];
long long primerArista[200200];
long long mejorCamino1[200200];
long long mejorCamino2[200200];
long long padre[200200];
long long ordenDFS[200200];
long long longitudCamino[200200];
bool visitado[200200];
long long caminoAlternativo[200200];
long long valorTemporal[200200];
long long respuestaMinima;
long long respuestaMaxima;
long long sumaRespuestas;
int agregarArista(int origen, int destino, int peso){
++aristas;
pesoArista[aristas] = peso;
destino[aristas] = destino;
siguiente[aristas] = primerArista[origen];
primerArista[origen] = aristas;
}
int procesarArbol(){
int i, x, y, z;
aristas = 0;
for(i = 1; i <= nodosA; ++i){
primerArista[i] = 0;
visitado[i] = false;
mejorCamino1[i] = 0;
mejorCamino2[i] = 0;
}
// Leer árbol
for(i = 1; i < nodosA; ++i){
scanf("%d%d%d", &x, &y, &z);
agregarArista(x, y, z);
agregarArista(y, x, z);
}
// BFS para establecer orden
visitado[1] = true;
int inicio, fin;
inicio = 1;
fin = 1;
ordenDFS[1] = 1;
for(; inicio <= fin; ++ inicio){
int neighbor;
for(neighbor = primerArista[ordenDFS[inicio]]; neighbor != 0; neighbor = siguiente[neighbor]){
if(!visitado[destino[neighbor]]){
visitado[destino[neighbor]] = true;
ordenDFS[++fin] = destino[neighbor];
longitudCamino[fin] = pesoArista[neighbor];
padre[fin] = inicio;
}
}
}
// Programación dinámica hacia arriba
longitudCamino[1] = 0;
valorTemporal[0] = 0;
mejorCamino1[0] = 0;
mejorCamino2[0] = 0;
for(i = nodosA; i > 1; --i){
if(mejorCamino1[i] + longitudCamino[i] > mejorCamino1[padre[i]]){
mejorCamino2[padre[i]] = mejorCamino1[padre[i]];
mejorCamino1[padre[i]] = mejorCamino1[i] + longitudCamino[i];
} else if(mejorCamino1[i] + longitudCamino[i] > mejorCamino2[padre[i]]){
mejorCamino2[padre[i]] = mejorCamino1[i] + longitudCamino[i];
}
}
// Programación dinámica hacia abajo
long long mejor = 2000000000;
for(i = 1; i <= nodosA; ++i){
if(mejorCamino1[i] + longitudCamino[i] != mejorCamino1[padre[i]]){
caminoAlternativo[i] = mejorCamino1[padre[i]] + longitudCamino[i];
} else {
caminoAlternativo[i] = mejorCamino2[padre[i]] + longitudCamino[i];
}
caminoAlternativo[i] = max(caminoAlternativo[i], caminoAlternativo[padre[i]] + longitudCamino[i]);
mejor = min(mejor, max(caminoAlternativo[i], mejorCamino1[i]));
respuestaMaxima = max(respuestaMaxima, caminoAlternativo[i] + mejorCamino1[i]);
}
sumaRespuestas += mejor;
return 0;
}
long long mcd(long long a, long long b){
if(b == 0) return a;
return mcd(b, a % b);
}
int main(){
scanf("%d%d%d", &nodosA, &nodosB, &longitudEnlace);
respuestaMinima = 0;
respuestaMaxima = 0;
sumaRespuestas = 0;
procesarArbol();
int i, j;
for(i = 1; i <= nodosA; ++i){
valorTemporal[i] = max(caminoAlternativo[i], mejorCamino1[i]);
}
// Intercambiar árboles
swap(nodosA, nodosB);
procesarArbol();
for(i = 1; i <= nodosA; ++i){
caminoAlternativo[i] = max(caminoAlternativo[i], mejorCamino1[i]);
}
sort(valorTemporal + 1, valorTemporal + 1 + nodosB);
sort(caminoAlternativo + 1, caminoAlternativo + 1 + nodosA);
respuestaMaxima -= longitudEnlace;
long long prefijos[200200];
prefijos[1] = valorTemporal[1];
for(i = 2; i <= nodosB; ++i){
prefijos[i] = prefijos[i-1] + valorTemporal[i];
}
j = nodosB;
for(i = 1; i <= nodosA; ++i){
while((j > 0) && (caminoAlternativo[i] + valorTemporal[j] > respuestaMaxima)){
--j;
}
respuestaMinima += respuestaMaxima * j +
caminoAlternativo[i] * (nodosB - j) +
prefijos[nodosB] - prefijos[j];
}
respuestaMinima += longitudEnlace * nodosA * nodosB;
sumaRespuestas = max(sumaRespuestas + longitudEnlace, respuestaMaxima + longitudEnlace);
printf("%lld\n", sumaRespuestas);
long long denominador;
denominador = mcd(respuestaMinima, nodosA * nodosB);
printf("%lld/%lld", respuestaMinista / denominador, (nodosA * nodosB) / denominador);
return 0;
}
Problema 3