Dada una cantidad c, y m valores diferentes de monedas, habrás de calcular el mínimo número de monedes que suman c, al igual que en el problema P81009. La diferencia, sin embargo, es que esta vez no hay disponibilidad de tantas monedas como se quiera: dispones de monedas de valor 1, y de éstas sí, tantas como se quiera, pero solamente dos monedas de cada una de las otras denominaciones.
Por ejemplo, si c = 15 y tenemos monedas de 1, 5 y 8, en general, se puede lograr con 3 monedas de 5; pero, ahora, hacen falta 4: 8+5+1+1, y usar las dos monedas de 5 disponibles lleva a una solución peor.
La entrada consiste en diversos casos. El primer valor n indica cuántos casos hay. Después siguen los n casos. Para cada caso, se indica la cantidad objetivo c y después el número de denominaciones m, seguido de los m valores, en orden ascendente e incluyendo siempre la denominación unitaria, es decir, el valor 1. (Podemos ver que esta condición implica m > 0.) Todos los valores son números naturales; las denominaciones son todas enteros positivos.
El mínimo número de monedas que tienen suma c, bajo la condición de usar un máximo de dos monedas de cada una de las denominaciones superiores a 1. (Aunque no se ha de escribir cómo se logra este mínimo para la corrección automática, el corrector humano valorará positivamente que el programa que se envía al Jutge pueda escribir muy fácilmente esta información.)
Autoría: José Luis Balcázar
Generación: 2026-03-30T18:37:12.620Z
© Jutge.org, 2006–2026.
https://jutge.org