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."și fișierul secvk.out va conţine pe prima linie k numere, reprezentând elementele secvenței cerute, 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 1

Intrare: secvk.in; 8 3; 5 6 1 2 6 6 4 3
Ieșire: Datele sunt introduse correct; secvk.out; 6 6 4

Exemplu 2

Intrare: secvk.in; 8 3; 52748
Ieșire: Datele nu corespund restricțiilor impuse.

Rezolvare

Rezolvare ver. 1

0134 - SecvK

def validate_input(n, k, arr):

   if k > n or n > 100000 or k < 1 or n < 1 or any(x >= 1000 for x in arr):
       return False
   return True

def find_max_sequence(n, k, arr):

   if not validate_input(n, k, arr):
       return "Datele nu corespund restricțiilor impuse.", []

   start = 0
   end = k-1
   max_sum = sum(arr[start:end+1])
   result = arr[start:end+1]

   for i in range(k, n):
       start += 1
       end += 1
       current_sum = sum(arr[start:end+1])
       if current_sum > max_sum:
           max_sum = current_sum
           result = arr[start:end+1]

   return "Datele sunt introduse corect.", result

if __name__ == "__main__":

   with open("secvk.in", "r") as f:
       n, k = map(int, f.readline().strip().split())
       arr = list(map(int, f.readline().strip().split()))

   message, result = find_max_sequence(n, k, arr)

   print(message)
   if message == "Datele sunt introduse corect.":
       with open("secvk.out", "w") as f:
           f.write(" ".join(str(x) for x in result)))

</syntaxhighlight>

Explicatie Rezolvare

validate_input(n, k, arr) - această funcție primește trei argumente: n și k, reprezentând numărul total de elemente din listă, respectiv numărul de elemente consecutive din listă pe care trebuie să le adunăm, și arr, o listă de numere întregi. Funcția verifică dacă toate aceste valori respectă restricțiile impuse: 1 ≤ k ≤ n ≤ 100.000, iar toate numerele din listă sunt mai mici decât 1000. În cazul în care aceste condiții nu sunt respectate, funcția returnează False, altfel returnează True.

find_max_sequence(n, k, arr) - această funcție primește aceiași trei argumente ca și funcția de mai sus, și calculează suma maximă a unei secvențe de k elemente consecutive din lista arr. Pentru a face acest lucru, funcția folosește o metodă de tip sliding window, parcurgând lista arr și determinând suma maximă a unei ferestre glisante de lungime k. Dacă argumentele nu respectă restricțiile impuse, funcția returnează un mesaj de eroare și o listă vidă, altfel returnează un mesaj de succes și lista de k elemente consecutive care au suma maximă.

main() - această funcție deschide fișierul secvk.in, citind valorile n, k și lista arr. Apoi, apelează funcția find_max_sequence() cu aceste argumente și afișează mesajul de eroare sau lista de elemente dacă acestea sunt valabile. În cazul în care lista de elemente este validă, scrie rezultatul în fișierul secvk.out.