El problema HDU-2566 plantea el desafío de encontrar el número de formas de seleccionar exactamente N monedas, dadas denominaciones de 1, 2 y 5 unidades, para que su valor total sume M. Este problema es un clásico en la programación competitiva y puede abordarse de varias maneras, cada una con sus propias características.
Método 1: Programación Dinámica (Variante de la Mochila)
Una forma robusta de resolver este problema es utilizando programación dinámica, tratándolo como una variante del problema de la mochila ilimitada, pero con una restricción adicional en el número exacto de elementos seelccionados. Definimos el estado dp[k][s] como el número de maneras de seleccionar exactamente k monedas que sumen un valor total de s.
La inicialización del estado es crucial: dp[0][0] = 1, lo que significa que hay una forma (no elegir ninguna moneda) de obtener un total de 0 con 0 monedas. Luego, iteramos a través de cada tipo de moneda disponible (1, 2 y 5). Para cada moneda, actualizamos nuestra tabla DP. La transición es la siguiente:
dp[k_monedas][suma_actual] += dp[k_monedas - 1][suma_actual - valor_moneda];
Esta transición significa que, para formar una suma suma_actual con k_monedas utilizando el tipo de moneda actual, podemos añadir esta moneda a cualquier combinación de k_monedas - 1 monedas que ya sumaban suma_actual - valor_moneda. Es importante que los bucles para k_monedas y suma_actual se ejecuten en orden ascendente para permitir el uso repetido de la misma moneda en la construcción de la suma y el conteo de monedas dentro de la iteración actual de tipo de moneda.
#include <iostream>
#include <cstring> // Para memset
// dp[k_monedas][suma_total] almacena el número de maneras
int numCombinaciones[1001][1001];
int denominaciones[] = {0, 1, 2, 5}; // Denominaciones de las monedas (índice 0 no usado)
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL); // Optimización de E/S
int numCasosPrueba;
std::cin >> numCasosPrueba;
while (numCasosPrueba--) {
// Inicializar la tabla DP a cero para cada caso de prueba
memset(numCombinaciones, 0, sizeof(numCombinaciones));
int numMonedas, valorObjetivo;
std::cin >> numMonedas >> valorObjetivo;
// Caso base: 0 monedas, 0 valor total = 1 forma (la combinación vacía)
numCombinaciones[0][0] = 1;
// Iterar sobre cada tipo de denominación de moneda
for (int i = 1; i <= 3; ++i) {
int valorMonedaActual = denominaciones[i];
// Iterar sobre el número de monedas exacto 'k'
for (int k = 1; k <= numMonedas; ++k) {
// Iterar sobre el valor total 's'
for (int s = valorMonedaActual; s <= valorObjetivo; ++s) {
// Si se usa la moneda actual, necesitamos k-1 monedas que sumen s - valorMonedaActual
numCombinaciones[k][s] += numCombinaciones[k - 1][s - valorMonedaActual];
}
}
}
// El resultado final es el número de formas de obtener 'numMonedas' con 'valorObjetivo'
std::cout <> numCombinaciones[numMonedas][valorObjetivo] << std::endl;
}
return 0;
}
Método 2: Enfoque Heurístico o Interpretación Alternativa
Este método, aunque conciso, parece tomar una perspectiva particular del problema o simplificarlo drásticamente. El código intenta encontrar una combinación específica de monedas que satisfaga las condiciones, y luego calcula un valor basado en el número de monedas de 2 unidades (b). La lógica detrás de la expresión 1 + b / 4 no corresponde directamente con el conteo general de todas las combinaciones posibles, que es lo que el problema HDU-2566 usualmente solicita. Podría ser una simplificación para un caso muy específico o una aproximación.
El algoritmo itera a través de posibles cantidades de monedas de 1 (i) y 2 (j) unidades. La cantidad de monedas de 5 unidades se deduce como n - j - i. Si la suma de valores para esta combinación coincide con m, entonces se encontró una solución. Sin embargo, en lugar de contar todas las soluciones, el programa termina la búsqueda y reporta 1 + j / 4.
#include <cstdio> // Para scanf y printf
int main() {
int numCasosPrueba;
scanf("%d", &numCasosPrueba);
while (numCasosPrueba--) {
int n_monedas, m_valor; // N: número total de monedas, M: valor total
scanf("%d%d", &n_monedas, &m_valor);
int cantidad_dos = 0; // Almacena la cantidad de monedas de 2 unidades
// Iterar posibles cantidades de monedas de 1 unidad
for (int i_unidades = 0; i_unidades <= n_monedas; ++i_unidades) {
// Iterar posibles cantidades de monedas de 2 unidades
for (int j_dos_unidades = 0; j_dos_unidades + i_unidades <= n_monedas; ++j_dos_unidades) {
// Calcular la cantidad de monedas de 5 unidades restantes
int k_cinco_unidades = n_monedas - j_dos_unidades - i_unidades;
// Verificar si la suma de valores coincide con el objetivo
if (j_dos_unidades * 2 + i_unidades * 1 + k_cinco_unidades * 5 == m_valor) {
cantidad_dos = j_dos_unidades; // Guardar la cantidad de monedas de 2
// Este break salta el bucle interno, y la siguiente asignación salta el bucle externo
i_unidades = n_monedas + 1; // Usado para salir del bucle exterior
break;
}
}
}
// Imprimir el valor calculado. La lógica de '1 + cantidad_dos / 4' es específica
printf("%d\n", 1 + cantidad_dos / 4);
}
return 0;
}
Método 3: Sistema de Ecuaciones Lineales e Iteración
Este enfoque transforma el problema en un sistema de ecuaciones lineales con tres variables y luego resuelve para dos de ellas en términos de la tercera, que se itera. Sean a, b y c el número de monedas de 1, 2 y 5 undiades, respectivamente.
Las dos condiciones dadas por el problema se pueden expresar como:
- Número total de monedas: a + b + c = N
- Valor total: a * 1 + b * 2 + c * 5 = M
Podemos despejar a y b en términos de c. De la primera ecuación, a = N - b - c. Sustituyendo a en la segunda ecuación:
(N - b - c) + 2b + 5c = M
N + b + 4c = M
Despejando b:
b = M - N - 4c
Ahora sustituimos b de nuevo en la expresión para a:
a = N - (M - N - 4c) - c
a = N - M + N + 4c - c
a = 2N - M + 3c
Con estas dos ecuaciones, podemos iterar sobre los posibles valores de c (desde 0 en adelante). Para cada valor de c, calculamos los valores correspondientes de a y b. Si tanto a como b son no negativos, hemos encontrado una combinación válida y aumentamos nuestro contador de soluciones. Detenemos la iteración cuando b (o a) se vuelve negativo, ya que aumentar c solo hará que b disminuya aún más.
#include <cstdio> // Para scanf y printf
int main() {
int casosPrueba;
scanf("%d", &casosPrueba); // Leer el número de casos de prueba
while (casosPrueba--) {
int numMonedas, valorTotal;
scanf("%d%d", &numMonedas, &valorTotal); // Leer N y M para cada caso
int contadorSoluciones = 0; // Contador de combinaciones válidas
int a_unidades, b_dos_unidades; // Cantidades de monedas de 1 y 2 unidades
int c_cinco_unidades = 0; // Cantidad de monedas de 5 unidades, comienza en 0
while (true) {
// Calcular 'b' y 'a' en función de 'c', N y M
b_dos_unidades = valorTotal - numMonedas - (4 * c_cinco_unidades);
a_unidades = (2 * numMonedas) - valorTotal + (3 * c_cinco_unidades);
// Si ambas cantidades son no negativas, es una solución válida
if (a_unidades >= 0 && b_dos_unidades >= 0) {
contadorSoluciones++;
}
// Si 'b' se vuelve negativo, no habrá más soluciones válidas ya que 'c' solo lo hará más negativo
else if (b_dos_unidades < 0) {
break; // Salir del bucle
}
// También podemos romper si 'a' se vuelve negativo antes que 'b', aunque 'b' suele ser el factor limitante
else if (a_unidades < 0 && (3 * c_cinco_unidades) > valorTotal - (2 * numMonedas)) { // Una condición más precisa para 'a' volviéndose negativo y no recuperarse
break;
}
c_cinco_unidades++; // Incrementar 'c' para la siguiente iteración
}
printf("%d\n", contadorSoluciones); // Imprimir el número total de soluciones
}
return 0;
}