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

==Include(page="template/taskheader" task_id="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-si 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. 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. Restrictii si precizari
 
* $1 ≤ N ≤ 17$
* $0 ≤ z{~i~} ≤ G ≤ 2000000000$
* Pentru teste in valoare cumulata de $70$ de puncte, $0 ≤ z{~i~} ≤ G ≤ 500$
* Nu se acorda punctaje partiale
 
h2. Exemplu
 
table(example). |_. zebughil.in |_. zebughil.out |
|4 10
6 7 5 4
4 4
2 3 1 2
1 5
1
|3
2
1|
 
_Explicatie_: pentru primul test putem repartiza blocurile in grupurile ${6, 4} {7} {5}$, pentru al doilea test in ${2, 2} {3, 1}$, iar pentru al treilea in ${1}$.
 
 
==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")==

641