Fișierul intrare/ieșire butoaie.in, butoaie.out Sursă Concurs Clasa a 7-a
Autor Teodor Plop Adăugată de avatar teodor94 Teodor Plop teodor94
Timp de execuție pe test 0.45 sec Limită de memorie 8192 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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.in butoaie.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 să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 5 categorii