Fişierul intrare/ieşire:	ghiozdan.in, ghiozdan.out	Sursă	preONI 2007, Runda 2
Autor	Mircea Bogdan Pasoi	Adăugată de	Mircea Pasoi •domino
Timp execuţie pe test	1 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	5/5

Vezi solutiile trimise | Statistici

Ghiozdan

Testele pentru aceasta problema nu sunt destul de bine construite pentru a departaja corect solutii ineficiente sau gresite. Intra aici daca vrei sa ne ajuti sa imbunatatim calitatea testelor pentru aceasta problema!

Zaharel, Nargy si Fumeanu vor sa plece la munte in vacanta. Pentru asta ei au cumparat un ghiozdan cat mai incapator, care are o capacitate de G grame. Ei au facut si o lista cu N obiecte pe care vor sa le ia cu ei. Nu toate obiectele incap in ghiozdan, si fiindca s-au decis sa nu se complice, vor sa umple cat de mult se poate ghiozdanul (desigur nu cu mai mult de G grame in total), dar cu un numar minim de obiecte.

Date de intrare

Prima linie a fisierul de intrare ghiozdan.in va contine numerele naturale N si G separate prin spatii. Urmatoarele N linii vor contine cate un numar natural pe linie, reprezentand greutatile celor N obiecte.

Date de iesire

Pe prima linie din fisierul de iesire ghiozdan.out se vor afisa doua numere naturale G_max si N_min cu semnificatia ca se poate umple ghiozdanul cu obiecte de greutate totala G_max (G_max ≤ G), iar numarul minim de obiecte pentru a obtine aceasta greutate este N_min. Urmatoarele N_min linii vor contine numere naturale reprezentand greutatile obiectelor din ghiozdan. Suma acestor numere trebuie sa fie G_max.

Restrictii

• 1 ≤ N ≤ 20.000
• 0 ≤ G ≤ 75.000
• Greutatile celor N obiecte sunt numere naturale intre 1 si 200
• Pentru un test se va acorda 60% din punctaj pentru determinarea corecta a numerelor G_max si N_min, si inca 40% daca s-a determinat si un set de obiecte care pot fi puse in ghiozdan.

Exemple

Cum se trimit solutii?