Cambio mínimo con sólo un par de monedas por denominación

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.

Entrada

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.

Salida

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.)

Información del problema

Autoría: José Luis Balcázar

Generación: 2026-03-30T18:37:12.620Z

© Jutge.org, 2006–2026.
https://jutge.org
