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 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.; secvk.out; 2 3 4

Rezolvare

Rezolvare ver. 1

0134 - SecvK

def max_sum_sequence(n, k, arr):

   if k > n:
       return None
   
   max_sum = -float('inf')
   max_seq = []
   
   for i in range(n - k + 1):
       seq = arr[i:i+k]
       seq_sum = sum(seq)
       
       if seq_sum > max_sum:
           max_sum = seq_sum
           max_seq = seq
   
   return max_seq

def main():

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

   if n != len(arr) or k > n or any(x >= 1000 for x in arr):
       print("Datele nu corespund restricțiilor impuse.")
       return

   seq = max_sum_sequence(n, k, arr)

   if seq is None:
       print("Nu exista secventa de lungime k in arr.")
   else:
       print("Datele sunt introduse corect.")
       with open('secvk.out', 'w') as fout:
           fout.write(' '.join(map(str, seq)))

if __name__ == '__main__':

   main()

</syntaxhighlight>

Explicatie Rezolvare

Funcția `max_sum_sequence(n, k, arr)` primește ca argumente numărul de elemente din șir `n`, numărul `k` pentru lungimea secvenței și lista de numere `arr`. Funcția verifică dacă `k` este mai mare decât `n` și, în caz afirmativ, returnează `None`. Apoi, funcția găsește secvența de lungime `k` cu suma maximă din lista `arr`. Variabilele `max_sum` și `max_seq` sunt inițializate cu valori negative și lista goală, respectiv. Pentru fiecare subsecvență de lungime `k` din `arr`, se calculează suma și se compară cu `max_sum`. Dacă este mai mare, atunci valoarea sumei este actualizată, iar lista `max_seq` este setată la subsecvența curentă. La final, funcția returnează lista `max_seq`.

Funcția `main()` începe prin citirea datelor de intrare din fișierul `secvk.in`. Apoi, se verifică dacă datele de intrare respectă restricțiile cerute și se afișează un mesaj corespunzător în cazul în care datele nu corespund. În caz contrar, se calculează secvența de lungime `k` cu suma maximă din lista `arr` folosind funcția `max_sum_sequence()`. Dacă nu există nicio secvență de lungime `k` în `arr`, se afișează un mesaj corespunzător. În caz contrar, se afișează un mesaj de confirmare și se scrie secvența găsită în fișierul `secvk.out`. Funcția `main()` este apelată doar dacă acest script este rulat direct, nu este importat ca modul în alt script, acest lucru se realizează prin instrucțiunea `if __name__ == '__main__':`.