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 secvmaxvalin.txt 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 secvmaxvalout.txt 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." , iar daca se indeplinesc, se afiseaza mesajul "Datele de intrare 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

secvmaxvalin.txt

5 11
4 5 2 3 9

secvmaxvalout.txt

Datele de intrare corespund cerintelor impuse.
3

Explicatie

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

Exemplu 2

secvmaxvalin.txt

5 10
1000000001 8 5 19 1

secvmaxvalout.txt

Datele de intrare nu corespund cerintelor impuse.

Rezolvare

<syntaxhighlight lang="python" line> def lungime_maxima_secventa(numar_elemente, valoare_maxima, numere):

   # Verificare restricții date de intrare
   if not (1 <= numar_elemente <= 200000 and 1 <= valoare_maxima <= 263 and all(1 <= num <= 1000000000 for num in numere)):
       with open("secvmaxvalout.txt", "w", encoding="utf-8") as output_file:
           output_file.write("Datele de intrare nu corespund restricțiilor impuse.")
       return

   suma_actuala = 0
   lungime_maxima = 0
   stanga = 0

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

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

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

   # Scrierea mesajului în fișierul de ieșire
   with open("secvmaxvalout.txt", "w", encoding="utf-8") as output_file:
       output_file.write("Datele de intrare corespund restricțiilor impuse.\n")
       output_file.write(str(lungime_maxima))

def main():

   # Citirea datelor din fișierul de intrare
   with open("secvmaxvalin.txt", "r", encoding="utf-8") as input_file:
       numar_elemente, valoare_maxima = map(int, input_file.readline().split())
       numere = list(map(int, input_file.readline().split()))

   # Determinarea lungimii maxime a unei secvențe
   lungime_maxima_secventa(numar_elemente, valoare_maxima, numere)

if __name__ == "__main__":

   main()

</syntaxhighlight>