3163 - Secv Max Val

Cerinţa

Se dă un șir de numar_elemente numere naturale și un număr natural valoare_maxima. Determinați lungimea maximă a unei secvențe cu proprietatea că suma numerelor din aceasta este mai mică sau egală cu valoare_maxima.

Date de intrare

Fișierul de intrare secvmaxval.in conține pe prima linie numerele numar_elemente și valoare_maxima, iar pe a două linie numar_elemente numere naturale separate prin spații.

Date de ieșire

Fișierul de ieșire secvmaxval.out va conține pe prima linie lungimea maximă a unei secvențe care satisface proprietatea dată. În cazul în care datele introduse de la tastatură nu îndeplinesc cerințele enunțate, pe ecran se va afișa mesajul "Datele de intrare nu corespund cerintelor impuse.".

Restricţii şi precizări

• 1 ⩽ numar_elemente ⩽ 200000
• numerele de pe a două linie a fișierului de intrare vor fi mai mici decât 1.000.000.000
• 1 ⩽ valoare_maxima ⩽ 2^63

Exemplu 1

Intrare

5 11

4 5 2 3 9

Ieșire

3

Exemplu 2

Intrare

5 10

1000000001 8 5 19 1

Ieșire

Datele de intrare nu corespund cerintelor impuse.

Rezolvare

<syntaxhighlight lang="python" line> def lungime_maxima_secventa(n, val, numere):

   # Verificare restricții date de intrare
   if not (1 <= n <= 200000 and all(1 <= num <= 1000000000 for num in numere) and 1 <= val <= 263):
       with open("secvmaxval.out", "w") as output_file:
           output_file.write("Datele de intrare nu corespund cerințelor impuse.")
       return

   suma_actuala = 0
   lungime_maxima = 0
   stanga = 0

   for dreapta in range(n):
       suma_actuala += numere[dreapta]

       while suma_actuala > val:
           suma_actuala -= numere[stanga]
           stanga += 1

       lungime_maxima = max(lungime_maxima, dreapta - stanga + 1)

   # Scrierea rezultatului în fișierul de ieșire
   with open("secvmaxval.out", "w") as output_file:
       output_file.write(str(lungime_maxima))

def main():

   # Citirea datelor din fișierul de intrare
   with open("secvmaxval.in", "r") as input_file:
       n, val = map(int, input_file.readline().split())
       numere = list(map(int, input_file.readline().split()))

   # Determinarea lungimii maxime a unei secvențe
   lungime_maxima_secventa(n, val, numere)

if __name__ == "__main__":

   main()

</syntaxhighlight>

Explicatie

O secvență de lungime maximă cu suma elementelor mai mică sau egală cu 11 este 5 2 3.