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.
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.
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ó.)
Autoria: José Luis Balcázar
Generació: 2026-03-30T18:37:08.795Z
© Jutge.org, 2006–2026.
https://jutge.org