2084 - water trap: Difference between revisions

From Bitnami MediaWiki
No edit summary
Line 1: Line 1:
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 ==
== Cerinţa ==
Determinați cantitatea maximă de apă reținută (exprimată în mililitri).
Determinați cantitatea maximă de apă reținută (exprimată în mililitri).
Line 14: 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'''
== Exemplul 1 ==
== Exemple ==
; Intrare
;Intrare
6
: 6
3 0 0 2 0 4
: 3 0 0 2 0 4
; Ieșire
;Iesire
10
: 10
<br>
;Intrare
12
: 12
0 1 0 2 1 0 1 3 2 1 2 1
: 0 1 0 2 1 0 1 3 2 1 2 1
; Ieșire
;Iesire
Datele de intrare corespund restrictiilor impuse
: 6
6
<br>
 
== Exemplu 2==
; Intrare
5
1 2 3 4 a
; Iesire
Datele de intrare nu corespund restrictiilor impuse
<br>
 
== Rezolvare ==
== Rezolvare ==
<syntaxhighlight lang="python" line>
<syntaxhighlight lang="python" line>
Line 74: Line 57:
         else:
         else:
             # Procesăm similar barele din dreapta
             # Procesăm similar barele din dreapta
             if [dreapta] > max_dreapta:
             if bare2[dreapta] > max_dreapta:
                 max_dreapta = bare2[dreapta]
                 max_dreapta = bare2[dreapta]
             else:
             else:
Line 98: Line 81:
     except IndexError:
     except IndexError:
         print("Datele de intrare nu corespund restrictiilor impuse")
         print("Datele de intrare nu corespund restrictiilor impuse")


</syntaxhighlight>
</syntaxhighlight>

Revision as of 07:54, 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

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