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

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect.", apoi pe un rând nou numărul c, reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: "Datele nu corespund restricțiilor impuse.".

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

Datele nu corespund restricțiilor impuse.

6 6 4

Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line>

1. 0134 - SecvK

def citire():

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

def rezolvare(n, k, sir):

   if k > n:
       return None  # Daca k > n, secventa de lungime k nu poate fi formata
   start = 0  # Primul index al secventei curente
   suma_curenta = sum(sir[:k])  # Suma elementelor primei secvente
   suma_maxima = suma_curenta  # Suma maxima gasita pana acum
   for i in range(k, n):
       suma_curenta += sir[i] - sir[start]  # Adaugam un nou element si eliminam cel mai vechi
       start += 1  # Mutam indexul de inceput al secventei curente
       if suma_curenta > suma_maxima:
           suma_maxima = suma_curenta
   return suma_maxima

def afisare(suma_maxima):

   if suma_maxima is None:
       print("Datele nu corespund restricțiilor impuse.")
   else:
       print("Datele sunt introduse corect.")
       print(suma_maxima)

if __name__ == '__main__':

   # Teste
   n, k, sir = citire()
   suma_maxima = rezolvare(n, k, sir)
   afisare(suma_maxima)

</syntaxhighlight>

Explicatie Rezolvare

Funcția citire() primește datele de intrare de la tastatură și returnează cele trei variabile n, k și sir. Funcția rezolvare(n, k, sir) primește cele trei variabile și calculează suma maximă pentru o secvență de lungime k. Mai întâi verificăm dacă k este mai mare decât n. Dacă da, atunci secvența de lungime k nu poate fi formată, deci returnăm None. Altfel, calculăm suma primelor k elemente și o setăm ca fiind suma maximă găsită până acum. Apoi, parcurgem lista sir de la indexul k până la n-1. La fiecare iterație adăugăm un nou element la secvență și eliminăm cel mai vechi element. Indexul de început al secvenței curente este mutat la dreapta, astfel încât secvența să aibă lungimea k. Dacă suma curentă este mai mare decât suma maximă găsită până acum, o actualizăm. La final, returnăm suma maximă găsită. Funcția afisare(suma_maxima) primește suma maximă și afișează un mesaj corespunzător, în funcție de faptul că datele de intrare sunt corecte sau nu. Dacă sunt corecte, atunci afișează suma maximă găsită. Dacă nu sunt corecte, atunci afișează un mesaj de eroare.