Fişierul intrare/ieşire:zebughil.in, zebughil.outSursăpreONI 2006 Runda 1
AutorCosmin Silvestru NegruseriAdăugată de
Timp execuţie pe test0.6 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

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 zi. Un camion va fi folosit o singura data pentru a nu se uza prea mult, iar o piatra nu poate fi taiata.

Cerinta

Aflati pentru Zebu care este numarul minim de camioane pe care trebuie sa le foloseasca pentru transportul blocurilor.

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.

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.

Restrictii si precizari

  • 1 ≤ N ≤ 17
  • 0 ≤ zi ≤ G ≤ 2000000000
  • Pentru teste in valoare cumulata de 70 de puncte, 0 ≤ zi ≤ G ≤ 500
  • Nu se acorda punctaje partiale

Exemplu

zebughil.inzebughil.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}.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content