Canvi mínim amb només un parell de monedes per denominació

Donada una quantitat c, i n valors diferents de monedes, et caldrà
calcular el mínim nombre de monedes que sumen canvi c, al igual que al
problema P81009. La diferència, però, és que aquesta vegada no hi ha
disponibilitat de tantes monedes com es vulgui: hi ha monedes de valor
1, i d’aquestes sí, tantes com es vulgui, però només dues monedes de
cadascuna de les altres denominacions.

Per exemple, si c = 15 i tenim monedes d’1, 5 i 8, en general es pot fer
amb 3 monedes de 5; ara, però, en calen 4: 8+5+1+1, i fer servir totes
dues monedes de 5 porta a una solució pitjor.

Entrada

L’entrada consisteix en diversos casos. El primer valor n indica quants
casos hi ha. Després segueixen els n casos. Per cada cas, s’indica la
quantitat objectiu c i després el nombre de denominacions m, seguits
dels m valors, en ordre ascendent i tot incloent sempre la denominació
unitària, és a dir, el valor 1. (Podem veure que aquesta condició
implica m > 0.) Tots els valors són números naturals; les denominacions
son totes enters positius.

Sortida

El mínim nombre de monedes que tenen suma c, sota la condició de fer
servir un màxim de dues monedes de cadascuna de les denominacions
superiors a 1. (Encara que no s’hagi d’escriure com s’assoleix aquest
mínim per la correcció automàtica, el corrector humà valorarà
positivament que el programa que s’envia al Jutge pugui escriure molt
fàcilment aquesta informació.)

Informació del problema

Autoria: José Luis Balcázar

Generació: 2026-03-30T18:37:08.795Z

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