Zebughil

zebughil

==Include(page="template/taskheader" task_id="zebughil")==

== include(page="template/taskheader" task_id="zebughil") ==
 
Poveste ...
 
h2. Cerinta
 
...
 
h2. Restrictii
 
...
 
h2. Date de intrare
 
...
 
h2. Date de iesire
 
...
 
h2. Exemplu
 
| zebughil.in | zebughil.out |
| linia1
linia2
linia3
| linia1
linia2
|
 
== include(page="template/taskfooter" task_id="zebughil") ==

==Include(page="template/raw")==
 
Link: [1]File-List
 
Zebughil
 
 
 
Zebu la ferma lui de gaini, in momentele de pauza in care nu trebuie sa hraneasca gainile sau sa faca curatenie, planuieste creearea unui monopol ovo-lactarian in judetul Bistrita Nasaud. Primul pas pentru indeplinirea acestui vis consta in construirea unei noi hale pentru gaini. Pentru a isi construi hala mult visata el a cumparat N blocuri mari de piatra care vrea sa le aduca la el la firma pentru a le prelucra. Prietenul sau Ghilau are o firma de transporturi si isi ofera serviciile lui gratuit cu conditia ca Zebu sa foloseasca numarul minim de camioane pentru a transporta blocurile de piatra. Fiecare camion de la firma lui Ghilau are aceiasi capacitate maxima de transport G, iar blocurile lui Zebu au greutatile z[i]. Un camion va fi folosit o singura data pentru a nu se uza prea mult, iar o piatra nu poate fi taiata.
 
h2. Cerinta:
 
Aflati pentru Zebu care este numarul minim de camioane pe care trebuie sa le foloseasca pentru transportul blocurilor
 
h2. Restrictii:
 
1 <= N <= 17
 
0 <= z[i] <= G <= 2000000000
 
 
 
Mentiune:
 
Pentru teste in valoare cumulata de 70 de puncte, garantam ca 0 <= z[i] <= G <= 500.
 
h2. Date de Intrare:
 
Fisierul de intrare zebughil.in va contine cate trei teste. Pe prima linie a fisierului se vor afla doi intregi N si G separati printr-un spatiu, reprezentand numarul de blocuri de piatra respectiv greutatea maxima suportata de un camion. Pe urmatoarea linie vor fi n intregi separate prin cate un singur spatiu reprezentand dimensiunile blocurilor. Al doilea test va incepe de pe linia 3 si va fi structurat la fel, iar testul trei va incepe de pe linia 5.
 
h2. Date de Iesire:
 
Fisierul de iesire zebughil.out va contine pe trei linii cate un singur numar intreg reprezentand numarul minim de camioane cerut de pe testul corespunzator liniei respective.
 
h2. Exemplu:
 
zebughil.in zebughil.out
 
4 10 3
 
6 7 5 4 2
 
4 4 1
 
2 3 1 2
 
1 5
 
1
 
Explicatie: pentru primul test putem repartiza blocurile in grupurile {6, 4} {7} {5}, pentru al doilea test repartizam blocurile astfel {2, 2} {3, 1} si pentru al treilea {1}
 
 
 
Nu se acorda punctaje partiale!
 
References
 
Visible links
1. file:///home/eval/eval/www/infoarena/docs/arhiva/zebughil/enunt_files/filelist.xml
==Include(page="template/taskfooter" task_id="zebughil")==