2084 - water trap: Difference between revisions

From Bitnami MediaWiki
No edit summary
Line 8: Line 8:
* '''2''' ⩽ '''n''' ⩽ '''100.000'''
* '''2''' ⩽ '''n''' ⩽ '''100.000'''
* cele '''n''' numere citite vor fi mai mici decât '''1.000'''
* cele '''n''' numere citite vor fi mai mici decât '''1.000'''
== Exemple ==
== Exemplu 1 ==
;Intrare
; Intrare
: 6
: 6
: 3 0 0 2 0 4
: 3 0 0 2 0 4
;Iesire
; Iesire
: 10
Datele de intrare corespund restrictiilor impuse
;Intrare
10
: 12
<br>
: 0 1 0 2 1 0 1 3 2 1 2 1
== Exemplu 2 ==
;Iesire
; Intrare
: 6
12
0 1 0 2 1 0 1 3 2 1 2 1
; Iesire
Datele de intrare corespund restrictiilor impuse
6
<br>
== Exemplu 3 ==
; Intrare
3
a 2 3
; Iesire
Datele de intrare nu corespund restrictiilor impuse
<br>
 
== Rezolvare ==
== Rezolvare ==
<syntaxhighlight lang="python" line>
<syntaxhighlight lang="python" line>

Revision as of 07:57, 16 November 2023

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

  • 2n100.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

<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 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")

</syntaxhighlight>