0134 - SecvK

Sursa: 0134 - SecvK

---

Cerinţa

Se dă un șir cu n numere naturale și un număr k. Să se determine o secvență de elemente de lungime k cu suma elementelor maximă.

Date de intrare

Fişierul de intrare secvk.in conţine pe prima linie numerele n și k, iar pe a doua linie n numere naturale separate prin spaţii.

Date de ieșire

Fişierul de ieşire secvk.out va conţine pe prima linie k numere, reprezentând elementele secvenței cerute.

Restricţii şi precizări

• 1 ≤ k ≤ n ≤ 100.000
• numerele de pe a doua linie a fişierului de intrare vor fi mai mici decât 1000
• dacă există mai multe secvențe de lungime k cu suma maximă se va afișa prima

Exemplu

Intrare

8 3

5 6 1 2 6 6 4 3

Ieșire

6 6 4

Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line>

1. 0134 - SecvK

def citire():

   n, k = map(int, input().split())
   lst = list(map(int, input().split()))
   return n, k, lst

def secventa_maxima(n, k, lst):

   suma_maxima = 0
   secventa_maxima = []
   for i in range(n-k+1):
       suma = sum(lst[i:i+k])
       if suma > suma_maxima:
           suma_maxima = suma
           secventa_maxima = lst[i:i+k]
   return secventa_maxima

def validare(n, k, lst, secventa):

   assert len(secventa) == k, "Lungimea secventei nu este k"
   assert sum(secventa) == max(sum(lst[i:i+k]) for i in range(n-k+1)), "Suma secventei nu este maxima"
   for x in secventa:
       assert x in lst, "Elementul {} nu se afla in lista initiala".format(x)

if __name__ == "__main__":

   n, k, lst = citire()
   secventa = secventa_maxima(n, k, lst)
   validare(n, k, lst, secventa)
   print(*secventa)

</syntaxhighlight>

Explicatie Rezolvare

Funcția citire citește datele de intrare și le returnează sub forma unei tuple (n, k, lst). Funcția secventa_maxima calculează secvența de lungime k cu suma maximă din lista lst, utilizând o buclă for și metoda sum. Variabilele suma_maxima și secventa_maxima memorează suma și secvența maximă întâlnită până acum. Funcția validare verifică corectitudinea secvenței calculate de secventa_maxima în raport cu datele de intrare. Funcția verifică lungimea secvenței, suma elementelor și faptul că fiecare element se află în lista inițială. Dacă validarea eșuează, funcția generează o excepție cu un mesaj corespunzător. În if __name__ == "__main__", apelăm funcțiile citire, secventa_maxima și validare, și apoi afișăm secvența maximă utilizând print(*secventa) (acest lucru afișează elementele secvenței separate prin spații, fără paranteze sau alte simboluri).