Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2007-02-15 00:29:52.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:ghiozdan.in, ghiozdan.outSursăpreONI 2007, Runda 2
AutorMircea Bogdan PasoiAdăugată dedominoMircea Pasoi domino
Timp execuţie pe test1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Ghiozdan

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 Gmax si Nmin cu semnificatia ca se poate umple ghiozdanul cu obiecte de greutate totala Gmax (Gmax ≤ G), iar numarul minim de obiecte pentru a obtine aceasta greutate este Nmin. Urmatoarele Nmin linii vor contine numere naturale reprezentand greutatile obiectelor din ghiozdan. Suma acestor numere trebuie sa fie Gmax.

Restrictii

  • 1 ≤ N ≤ 50.000
  • 0 ≤ G ≤ 200.000

Exemple

ghiozdan.inghiozdan.out
5 9
2
2
2
2
4
8 3
2
2
4
6 24
19
7
7
7
7
2
23 4
2
7
7
7
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?