Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2007-10-15 15:33:24.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:aimin.in, aimin.outSursăHappy Coding 2007
AutorMugurel Ionut AndreicaAdăugată demugurelionutMugurel-Ionut Andreica mugurelionut
Timp execuţie pe test0.05 secLimită de memorie67583 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Aimin

Sa consideram cele N frunze ale unui arbore binar strict (fiecare nod intern al arborelui are exact 2 fii, fiul stanga si fiul dreapta), numerotate de la 1 la N (in ordinea in care apar ele de la stanga la dreapta intr-o parcurgere stanga-radacina-dreapta a arborelui). De fiecare frunza i a fost agatata o panglica de lungime Li. Nivelul fiecarui nod al arborelui este egal cu lungimea drumului de la radacina arborelui la nodul respectiv (nivelul radacinii este 0). Inaltimea unei frunze i este egala cu nivelul acesteia plus Li. Inaltimea intregului arbore este egala cu maximul dintre inaltimile celor N frunze ale sale. Determinati inaltimea minima posibila a arborelui.

Date de intrare

Pe prima linie a fisierului de intrare aimin.in se afla numarul intreg N. Pe a doua linie se afla N numere intregi, separate prin spatii, reprezentand valorile Li, in ordine, de la 1 la N.

Date de iesire

In fisierul de iesire aimin.out veti afisa inaltimea minima posibila a arborelui.

Restrictii

  • 1 ≤ N ≤ 100 000
  • 1 ≤ Li ≤ 100 000 000

Exemplu

aimin.inaimin.out
5
3 1 2 4 2
6
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?