Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2007-11-08 20:45:04.
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

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 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 ≤ 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 Gmax si Nmin, si inca 40% daca s-a determinat si un set de obiecte care pot fi puse in ghiozdan.

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?

remote content