2084 - water trap: Difference between revisions

From Bitnami MediaWiki
No edit summary
Line 14: Line 14:
* '''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'''
== Exemplu ==
== Exemplul 1 ==
; Intrare
; Intrare
: 12
6
: 0 1 0 2 1 0 1 3 2 1 2 1
3 0 0 2 0 4
; Iesire
; Ieșire
10
12
0 1 0 2 1 0 1 3 2 1 2 1
; Ieșire
: Datele de intrare corespund restrictiilor impuse
: Datele de intrare corespund restrictiilor impuse
: 6
: 6
<br>
<br>
== Exemplu 2==
== Exemplu 2==
; Intrare
; Intrare

Revision as of 17:37, 15 November 2023

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

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