Editing 3440 - Buldo

== Enunt ==
Dorești să nivelezi terenul pe care l-ai cumpărat, care are lățimea de 1 metru și lungimea de N metri, fiind alcătuit din N zone succesive, fiecare zonă având lungimea de 1 metru. Terenul se reprezintă ca un șir de N numere naturale h1, h2, h3, …, hN reprezentând înălțimile în metri pe care le au zonele din terenul inițial, privite de la stânga spre dreapta.

Pentru a nivela terenul ai închiriat un buldozer care funcționează astfel. Se alege o înălțime H (număr natural) la care ridicăm lama buldozerului. Inițial buldozerul are pe lamă o cantitate C=0 metri cubi de pământ. Buldozerul începe să mergă de la stânga la dreapta și când ajunge la zona i, în funcție de înălțimea hi a acesteia, se va afla în una dintre următoarele situații:

dacă hi ≥ H atunci cantitatea suplimentară hi - H se adaugă la C și nivelul zonei ajunge la H.
dacă hi < H atunci se scade din C diferența H - hi pentru a aduce nivelul zonei la nivelul H.
Remarcăm faptul că H trebuie ales inițial astfel încât de fiecare dată când buldozerul ajunge în a doua situație să aibă pe lamă suficient pământ (C ≥ H - hi). După ce buldozerul parcurge cele N zone de lungime 1 pe lama buldozerului e posibil să mai rămână pământ, dar asta nu te interesează, pentru că la capătul din dreapta al terenului este un râu, și pământul rămas se va vărsa acolo.

== Cerința ==
Scrieţi un program care calculează înălțimea maximă H la care poate fi ridicată lama, astfel încât terenul să poată fi nivelat la acea înălțime.

== Date de intrare ==
Fișierul de intrare buldo.in conține pe prima linie numărul natural N, iar pe a doua linie, separate prin câte un spațiu, cele N numere naturale h1, h2, h3, …, hN, cu semnificația din enunț.

== Date de ieșire ==
Fișierul de ieșire buldo.out va conține o singură linie, pe care va fi scris numărul natural H cerut.

== Restricții și precizări ==
* 1 &les; '''N''' &les; 100.000
* Înălțimile sunt numere naturale, 1 &les; '''hi''' &les; 1.000.000.000, pentru orice i, 1 &les; '''i''' &les; N


== Exemplu 1 ==
; Intrare
; buldo.in
: 4
: 5 2 1 6
; Ieșire
; buldo.out
: 2
<br>
== Exemplu 2 ==
; Intrare
; buldo.in
: 100001
: 5 2 1 6
; Ieșire
: AssertionError
<br>
== Rezolvare ==
<syntaxhighlight lang="python" line>
#3440 - Buldo
def validare_inaltime(h, H, C):
    for hi in h:
        if hi >= H:
            C += hi - H
        elif C < H - hi:
            return False
        else:
            C -= H - hi
    return True


def cautare_binara(h):
    stanga, dreapta = 1, max(h)
    rezultat = 0

    while stanga <= dreapta:
        mijloc = (stanga + dreapta) // 2

        if validare_inaltime(h, mijloc, 0):
            rezultat = mijloc
            stanga = mijloc + 1
        else:
            dreapta = mijloc - 1

    return rezultat


with open('buldo.in', 'r') as f:
    N = int(f.readline())
    h = list(map(int, f.readline().split()))


assert 1 <= N <= 100000
assert all(1 <= hi <= 1000000000 for hi in h)


rezultat = cautare_binara(h)

with open('buldo.out', 'w') as g:
    g.write(str(rezultat) + '\n')
</syntaxhighlight>