| Fişierul intrare/ieşire: | bancnote.in, bancnote.out | Sursă | ad-hoc |
| Autor | Tudor Muresan | Adăugată de |  Ciprian Oprisa •cypry |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 16384 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Plata minimă fără rest
Gigel intră într-un supermarket care are doar case de marcat automate, unde trebuie să îşi scaneze singur produsele. Mai rău, la aceste case de marcat se poate plăti doar cash şi nu se dă rest.
Gigel are un teanc de N bancnote a căror valoare nominală este dată de şirul de numere întregi R1, R2, ..., RN. Valoarea cumpărăturilor făcute de Gigel este un număr întreg C. Plata se efectuează cu un număr K de bancnote cu valoarea Rc1, Rc2, ..., RcK, astfel încât Rc1 + Rc2 + ... + RcK ≥ C.
Fiind date valorile nominale ale bancnotelor R1, R2, ..., RN şi valoarea cumpărăturilor C, ajutaţi-l pe Gigel să cheltuiască cât mai puţini bani, calculând valoarea minimă a sumei S = Rc1 + Rc2 + ... + RcK, astfel încât S ≥ C. Dacă sunt două soluţii cu aceeaşi valoare minimă, se alege cea în care numărul K al bancnotelor plătite este minim.
Date de intrare
Fişierul de intrare bancnote.in conţine pe prima linie numărul de teste T. Următoarele 2T linii conţin cele T teste, fiecare test fiind format din două linii. Pe prima linie a fiecărui test se găsesc cei doi întregi N şi C, adică numărul de banconte şi suma totală de plată. A doua linie a fiecărui test conţine un şir de numere întregi separate prin spaţiu, reprezentând valorile nominale ale bancnotelor R1, R2, ..., RN.
Date de ieşire
Fişierul de ieşire bancnote.out va conţine câte o linie pentru fiecare exemplu de test, pe care se tipăreşte valoarea minimă a sumei S care poate fi plătită, urmată de caracterul ',' şi numărul minim K de bancnote folosite.
Restricţii
- 1 ≤ N ≤ 100
- 1 ≤ C ≤ 20000
- 1 ≤ Ri ≤ 500
- fişierul de intrare conţine cel mult 20 de teste
Exemplu
| bancnote.in | bancnote.out |
|---|---|
| 1 6 60 25 21 38 21 31 21 | 63,2 |
Explicaţie
Suma minimă care poate fi plătită este 63, care poate fi plătită cu cele trei bancnote cu valoare 21 sau cu cele două bancnote cu valoare 25 şi 38. A doua variantă foloseşte mai puţine bancnote.
