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."ș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.
- 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()
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__':`.