Pagini recente » Istoria paginii utilizator/md14111204 | Diferente pentru utilizator/veleandu intre reviziile 79 si 47 | Diferente pentru utilizator/veleandu intre reviziile 62 si 63 | Istoria paginii utilizator/andrei_ierdna | carburanti

Fişierul intrare/ieşire:	carburanti.in, carburanti.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

Cantitate maximă la transport de carburanți

Într-un depozit de carburanţi există $n$ recipiente pline cu carburant având capacitatea dată de şirul de numere întregi $R_1, R_2, \ldots, R_n$ . De aici carburanţii sunt transportaţi cu vagoane cisternă. La un moment dat, într-un vagon cisternă de capacitate $C$ , unde $C$ este un întreg, se pompează carburant din mai multe recipiente de capacitate $R_{c_1}, \ldots, R_{c_k}$ . Carburantul dintr-un recipient $R_c$ este pompat în totalitate în acelaşi vagon cisternă. Cantitatea de carburant pompată într-un vagon cisternă este $R_{c_1} + \ldots + R_{c_k} \leq C$ .

Fiind date capacităţile recipientelor $R_1, R_2, \ldots, R_n$ si capacitatea vagonului cisterna $C$ , se cere să se determine cantitatea maximă de carburant care poate fi pompată în vagonul cisternă şi numărul recipientelor pompate. Dacă sunt două soluţii cu aceeaşi cantitate maximă, se alege cea în care numărul recipientelor pompate este minim. De exemplu, dacă sunt recipiente de capacitate $23, 18, 77, 18, 31, 18$ , iar capacitatea vagonului cisternă este $60$ , cantitatea maximă de carburant care poate fi pompată în vagonul cisternă este $59$ , iar numărul minim de recipiente este $3$ . ( Având: $23 + 18 + 18 = 59$ )

Date de intrare

Fişierul de intrare carburanti.in conţine pe prima linie numărul de teste $T$ . Următoarele $2 \cdot T$ 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 recipiente şi capacitatea vagonului cisternă. A doua linie a fiecărui test conţine un şir de numere întregi separate prin spaţiu, reprezentând capacităţile recipientelor $R_1, R_2, \ldots, R_n$ .

Date de ieşire

Fişierul de ieşire carburanti.out va conţine câte o linie pentru fiecare exemplu de test, pe care se tipăreşte cantitatea maximă de carburant care poate fi pompată în vagonul cisternă, urmată de caracterul ',' şi numărul minim de recipiente pompate.