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

Exemple

Intrare

6

3 0 0 2 0 4

Iesire

10

Intrare

12

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

Iesire

6

Rezolvare

<syntaxhighlight lang="python" line> def cantitate_maxima_apa(n, bare):

   # Inițializăm cantitatea de apă și indicii pentru stânga și dreapta
   apa = 0
   stanga = 0
   dreapta = n - 1

   max_stanga = max_dreapta = 0

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

   return apa

1. Punctul de intrare al programului

if __name__ == "__main__":

   n = int(input("Introduceți numărul de bare: "))
   bare = list(map(int, input("Introduceți înălțimile barelor, separate prin spații: ").split()))

   print("Cantitatea maximă de apă reținută este: ", cantitate_maxima_apa(n, bare))

</syntaxhighlight>