2084 - water trap

Plouă, plouă, plouă…

IT -istul Ghită vă propune următoarea problemă: pe o platformă sunt montate pe poziții consecutive n bare verticale de lățime 1cm (vezi exemplul). Vom presupune că platforma este mărginită față/spate de ziduri transparente de înălțime infinită. Cantitatea de apă ce poate fi reținută într-o unitate de volum (1cm x 1cm x 1cm) este de 1 mililitru.

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

Exemplul 1

Intrare

6
3 0 0 2 0 4

Ieșire

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

Ieșire

Datele de intrare corespund restrictiilor impuse

6

Exemplu 2

Intrare

5

1 2 3 4 a

Iesire

Datele de intrare nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python" line> 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 [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")

</syntaxhighlight>