2084 - water trap

Cerinţa

Determinați cantitatea maximă de apă reținută (exprimată în mililitri).

Date de intrare

Programul citește de la tastatură numărul n, iar apoi n numere naturale, separate prin spații, ce reprezintă înălțimile barelor.

Date de ieșire

Programul va afișa pe ecran numărul W, ce reprezintă cantitatea de apă ce poate fi reținută.

Restricţii şi precizări

• 2 ⩽ n ⩽ 100.000
• cele n numere citite vor fi mai mici decât 1.000

Exemplu 1

Intrare

6

3 0 0 2 0 4

Iesire

Datele de intrare corespund restrictiilor impuse 
10

Exemplu 2

Intrare

12
0 1 0 2 1 0 1 3 2 1 2 1

Iesire

Datele de intrare corespund restrictiilor impuse
6

Exemplu 3

Intrare

3
a 2 3

Iesire

Datele de intrare nu corespund restrictiilor impuse 

Rezolvare

def validare(nr, bare1):  # functia de validare a datelor de intrare

    if len(bare1) != nr:
        raise ValueError

    if nr > 100000:
        raise ValueError

    for bara in bare:
        if not isinstance(bara, int) or bara < 0 or bara > 1000:
            raise ValueError

    print("Datele de intrare corespund restrictiilor impuse")


def cantitate_maxima_apa(nr, bare2):
    # Inițializăm cantitatea de apă și indicii pentru stânga și dreapta
    apa = 0
    stanga = 0
    dreapta = nr - 1

    max_stanga = max_dreapta = 0

    while stanga <= dreapta:
        # Dacă bara din stânga este mai mică decât cea din dreapta
        if bare2[stanga] < bare2[dreapta]:
            # Dacă bara curentă este mai mare decât maxima din stânga, o actualizăm
            if bare2[stanga] > max_stanga:
                max_stanga = bare2[stanga]
            else:
                # Altfel, adăugăm diferența dintre maxima din stânga și bara curentă la cantitatea de apă
                apa += max_stanga - bare2[stanga]
            # Mergem la următoarea bară din stânga
            stanga += 1
        else:
            # Procesăm similar barele din dreapta
            if bare2[dreapta] > max_dreapta:
                max_dreapta = bare2[dreapta]
            else:
                apa += max_dreapta - bare2[dreapta]
            dreapta -= 1

    return apa


if __name__ == '__main__':

    # din cauza datelor de intrare pot aparea 2 tipuri de erori, valueError sau IndexError pe care le tratam
    try:
        n = int(input("Introduceți numărul de bare (N): "))
        bare = list(map(int, input("Introduceți înălțimile barelor, separate prin spații: ").split()))

        validare(n, bare)  # apelul functiei de validare
        result = cantitate_maxima_apa(n, bare)  # apelul functiei de rezolvare
        print("Cantitatea maximă de apă reținută este: ", result)

    except ValueError:
        print("Datele de intrare nu corespund restrictiilor impuse")
    except IndexError:
        print("Datele de intrare nu corespund restrictiilor impuse")