4266 - MITM

From Bitnami MediaWiki
Revision as of 16:13, 12 December 2023 by Mesarosdenisa (talk | contribs) (Pagină nouă: == 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ă...)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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 suma_maxima_subsir(n, s, sir):

   stanga = 0
   suma_curenta = 0
   suma_maxima = 0
   for dreapta in range(n):
       suma_curenta += sir[dreapta]
       while suma_curenta > s:
           suma_curenta -= sir[stanga]
           stanga += 1
       suma_maxima = max(suma_maxima, suma_curenta)
   return suma_maxima

def main():

   # Citire număr de elemente și suma s
   n, s = map(int, input("Introduceti n si s: ").split())
   # Citire elemente șirului
   sir = list(map(int, input("Introduceti n numere separate prin spatii: ").split()))
   # Calcul și afișare rezultat
   rezultat = suma_maxima_subsir(n, s, sir)
   print("Suma maximă posibilă este:", rezultat)

if __name__ == "__main__":

   main()

</syntaxhighlight>

Explicatie

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