4266 - MITM
De la Universitas MediaWiki
Cerinta
Fie un număr natural s și un șir de n numere naturale nenule. Să se determine suma maximă posibilă, mai mică sau egală cu s ce se poate obține dintr-un subșir al șirului.
Date de intrare
Programul citește de la tastatură numărul n și s, apoi n numere naturale, separate prin spații, reprezentând elementele șirului.
Date de iesire
Programul va afișa pe ecran numărul M, reprezentând suma maximă posibilă, mai mică sau egală cu s ce se poate obține dintr-un subșir al șirului.
Restrictii si precizari
- 3 ⩽ n ⩽ 40
- 1 ⩽ s ⩽ 2.000.000.000
- Șirul va conține numere naturale nenule mai mici decât 50.000.001.
- Toate elementele șirului vor fi mici sau egale decât s.
Exemplul 1
- Intrare
- 5 20
- 5 10 6 8 3
- Iesire
- Datele introduse corespund restrictiilor impuse
- 19
Exemplul 2
- Intrare
- 1 1
- 4 29 2 0
- Iesire
- Datele introduse nu corespund restrictiilor impuse
Rezolvare
def verificare_date_intrare(n, s, sir):
if not (3 <= n <= 40 and 1 <= s <= 2000000000):
return False
if not all(1 <= x < 50000001 for x in sir):
return False
return True
def suma_maxima_subsir(arr, s):
n = len(arr)
suma_maxima = 0
suma_curenta = 0
stanga = 0
for dreapta in range(n):
suma_curenta += arr[dreapta]
while suma_curenta > s:
suma_curenta -= arr[stanga]
stanga += 1
suma_maxima = max(suma_maxima, suma_curenta)
return suma_maxima
# Citire date de intrare
try:
n = int(input("Introduceți numărul de elemente: "))
s = int(input("Introduceți suma dorită: "))
sir = list(map(int, input("Introduceți șirul de numere separate prin spațiu: ").split()))
# Verificare date de intrare
if not verificare_date_intrare(n, s, sir):
raise ValueError("Datele introduse nu corespund restricțiilor impuse.")
# Calculare și afișare rezultat
rezultat = suma_maxima_subsir(sir, s)
print(f"Suma maximă posibilă mai mică sau egală cu {s} este: {rezultat}")
except ValueError as ve:
print(ve)
Explicatie
Suma maximă mai mică sau egală decât 20 este 17 și se formează doar din numărul 17.