4266 - MITM

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

<syntaxhighlight lang="python3" line="1"> 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

1. 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)

</syntaxhighlight>

Explicatie

Suma maximă mai mică sau egală decât 20 este 17 și se formează doar din numărul 17.