0134 - SecvK: Diferență între versiuni
Fără descriere a modificării |
|||
Linia 26: | Linia 26: | ||
: secvk.out | : secvk.out | ||
: 6 6 4 | : 6 6 4 | ||
== Exemplu 2 == | == Exemplu 2 == | ||
; Intrare | ; Intrare | ||
Linia 33: | Linia 34: | ||
; Ieșire | ; Ieșire | ||
: Datele nu corespund restricțiilor impuse. | : Datele nu corespund restricțiilor impuse. | ||
== Rezolvare == | == Rezolvare == | ||
Linia 41: | Linia 41: | ||
# 0134 - SecvK | # 0134 - SecvK | ||
def | def validate_input(n, k, arr): | ||
if k > n | if k > n or n > 100000 or k < 1 or n < 1 or any(x >= 1000 for x in arr): | ||
return False | |||
return True | |||
return | |||
if n | 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> | </syntaxhighlight> | ||
== Explicatie Rezolvare == | == 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. |
Versiunea curentă din 14 mai 2023 20:29
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.
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)))
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.