Fişierul intrare/ieşire:butoaie.in, butoaie.outSursăConcurs Clasa a 7-a
AutorTeodor PlopAdăugată deteodor94Teodor Plop teodor94
Timp execuţie pe test0.45 secLimită de memorie8192 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Butoaie

Testele pentru aceasta problema nu sunt destul de bine construite pentru a departaja corect solutii ineficiente sau gresite.

Gigel lucreaza la o firma profesionista de confectionat butoaie. Patronul firmei ii da acestuia N sticle pline cu apa, de anumite cantitati, nu neaparat diferite. Gigel trebuie sa umple butoaie de aceeasi capacitate, dar nu oricum:

  • Sticlele trebuie varsate in ordinea dorita de patronul firmei.
  • Gigel trebuie sa verse intreaga cantitate de apa din toate cele N sticle.
  • Gigel nu are voie sa verse apa dintr-o sticla pe jos.
  • O sticla de apa trebuie varsata intr-un singur butoi.
  • Gigel are voie sa verse apa intr-un butoi doar daca restul butoaielor ce contin apa sunt pline.
  • In final, toate butoaiele care contin apa trebuie sa fie pline.

Ajutati-l pe Gigel sa determine capacitatea minima a butoaielor pe care acesta trebuie sa le umple respectand conditiile de mai sus.

Date de intrare

Fişierul de intrare butoaie.in contine pe prima linie numarul natural N, reprezentand numarul de sticle pline cu apa, iar pe a doua linie un sir c[i] de N numere naturale, reprezentand capacitatile celor N sticle, in ordinea dorita de patronul firmei.

Date de ieşire

În fişierul de ieşire butoaie.out se va gasi un singur numar natural, reprezentand capacitatea minima a butoaielor.

Restricţii

  • 1 ≤ N ≤ 1.000.000
  • 1 ≤ c[i] ≤ 1.000

Exemplu

butoaie.inbutoaie.out
7
3 1 2 2 4 4 2
6

Explicaţie

Daca butoaiele au capacitatea mai mica decat 4, este evident ca nu se pot respecta conditiile problemei.
Daca butoaiele au capacitatea 4, Gigel va umple primul butoi varsand sticla 1 si sticla 2, pe cel de-al doilea butoi varsand sticla 3 si sticla 4, in cel de-al treilea butoi va varsa sticla 5, iar in cel de-al patrulea va varsa sticla 6, dar nu va putea umple ultimul butoi, avand la dispozitie doar o sticla de capacitate 2.
Daca butoaiele au capacitatea 5, Gigel nu va putea umple nici macar primul butoi complet.
Daca butoaiele au insa capacitatea 6, Gigel va umple primul butoi cu sticlele 1, 2 si 3, cel de-al doilea butoi cu sticlele 4 si 5, iar cel de-al treilea butoi cu sticlele 6 si 7.

Trebuie sa te autentifici pentru a trimite solutii. Click aici