2084 - water trap: Difference between revisions
Pagină nouă: == 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... |
|||
Line 21: | Line 21: | ||
== Rezolvare == | == Rezolvare == | ||
<syntaxhighlight lang="python" line> | <syntaxhighlight lang="python" line> | ||
def cantitate_maxima_apa( | 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 | # Inițializăm cantitatea de apă și indicii pentru stânga și dreapta | ||
apa = 0 | apa = 0 | ||
stanga = 0 | stanga = 0 | ||
dreapta = | dreapta = nr - 1 | ||
max_stanga = max_dreapta = 0 | max_stanga = max_dreapta = 0 | ||
Line 31: | Line 46: | ||
while stanga <= dreapta: | while stanga <= dreapta: | ||
# Dacă bara din stânga este mai mică decât cea din dreapta | # Dacă bara din stânga este mai mică decât cea din dreapta | ||
if | if bare2[stanga] < bare2[dreapta]: | ||
# Dacă bara curentă este mai mare decât maxima din stânga, o actualizăm | # Dacă bara curentă este mai mare decât maxima din stânga, o actualizăm | ||
if | if bare2[stanga] > max_stanga: | ||
max_stanga = | max_stanga = bare2[stanga] | ||
else: | else: | ||
# Altfel, adăugăm diferența dintre maxima din stânga și bara curentă la cantitatea de apă | # Altfel, adăugăm diferența dintre maxima din stânga și bara curentă la cantitatea de apă | ||
apa += max_stanga - | apa += max_stanga - bare2[stanga] | ||
# Mergem la următoarea bară din stânga | # Mergem la următoarea bară din stânga | ||
stanga += 1 | stanga += 1 | ||
else: | else: | ||
# Procesăm similar barele din dreapta | # Procesăm similar barele din dreapta | ||
if | if [dreapta] > max_dreapta: | ||
max_dreapta = | max_dreapta = bare2[dreapta] | ||
else: | else: | ||
apa += max_dreapta - | apa += max_dreapta - bare2[dreapta] | ||
dreapta -= 1 | dreapta -= 1 | ||
return apa | return apa | ||
print("Cantitatea maximă de apă reținută este: ", | 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> | </syntaxhighlight> |
Revision as of 08:25, 12 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
- 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 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>