zebughil

Zebughil

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

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

Poveste ...

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

...
 
h2. Restrictii
 
...

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

| zebughil.in | zebughil.out |
| linia1
linia2
linia3
| linia1
linia2
|

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/taskfooter" task_id="zebughil") ==

641