Editing 3440 - Buldo

== Enunț ==
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 buldoin.txt 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 buldoout.txt 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


== Exemplul 1 ==
; Intrare
; buldoin.txt
: 4
: 5 2 1 6
; Ieșire
: Datele de intrare corespund restricțiilor impuse
; buldoout.txt
: 2

=== Explicație ===
Dacă se fixează lama la înălțimea H=2, după ce se trece de zona 1 (primul metru pe lungime), această zonă rămâne la înălțimea 2 și C=3 metri cubi de pământ sunt duși de lamă la zona 2. Acolo se vor obține în total 2+3=5 metri cubi de pământ, dar se păstrează doar 2, iar restul de C=3 se transportă la zona 3. La zona 3 se vor obține în total 1+3=4 metri cubi de pământ, dar se păstrează doar 2, iar restul de C=2 se transportă la zona 4. La zona 4 se vor obține în total 6+2=8 metri cubi de pământ, dar se păstrează doar 2, iar restul de C=6 se aruncă în râu.

Dacă s-ar fixa lama la înălțimea H=3, la zona 3 se poate ajunge doar la înălțimea 2 și încercarea eșuează (fiind o înălțime mai mică decât cea propusă).

== Exemplul 2 ==
; Intrare
; buldoin.txt
: 100001
: 5 2 1 6
; Ieșire
: Datele de intrare NU corespund restricțiilor impuse

== 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('buldoin.txt', 'r') as f:
    N = int(f.readline())
    h = list(map(int, f.readline().split()))


if 1 <= N <= 100000:
    print("Datele de intrare corespund restricțiilor impuse")
else:
    print("Datele de intrare NU corespund restricțiilor impuse")
    exit(0)

for hi in h:
    if not 1 <= hi <= 1000000000:
        print("Datele de intrare NU corespund restricțiilor impuse")
        exit(0)

rezultat = cautare_binara(h)

with open('buldoout.txt', 'w') as g:
    g.write(str(rezultat) + '\n')

</syntaxhighlight>