0134 - SecvK: Diferență între versiuni
(Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/134/secvk 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 == Fişierul de ieşire secvk.out va conţine pe prima linie k numere, reprezentâ...) |
Fără descriere a modificării |
||
Linia 29: | Linia 29: | ||
# 0134 - SecvK | # 0134 - SecvK | ||
def citire(): | |||
n, k = map(int, input().split()) | n, k = map(int, input().split()) | ||
lst = list(map(int, input().split())) | |||
return n, k, lst | |||
def secventa_maxima(n, k, lst): | |||
suma_maxima = 0 | |||
secventa_maxima = [] | |||
for i in range(n-k+1): | |||
suma = sum(lst[i:i+k]) | |||
if suma > suma_maxima: | |||
suma_maxima = suma | |||
secventa_maxima = lst[i:i+k] | |||
return secventa_maxima | |||
def validare(n, k, lst, secventa): | |||
assert len(secventa) == k, "Lungimea secventei nu este k" | |||
assert sum(secventa) == max(sum(lst[i:i+k]) for i in range(n-k+1)), "Suma secventei nu este maxima" | |||
for x in secventa: | |||
assert x in lst, "Elementul {} nu se afla in lista initiala".format(x) | |||
if __name__ == "__main__": | |||
n, k, lst = citire() | |||
secventa = secventa_maxima(n, k, lst) | |||
validare(n, k, lst, secventa) | |||
print(*secventa) | |||
print(* | |||
</syntaxhighlight> | </syntaxhighlight> | ||
== Explicatie Rezolvare == | |||
Funcția citire citește datele de intrare și le returnează sub forma unei tuple (n, k, lst). | |||
Funcția secventa_maxima calculează secvența de lungime k cu suma maximă din lista lst, utilizând o buclă for și metoda sum. Variabilele suma_maxima și secventa_maxima memorează suma și secvența maximă întâlnită până acum. | |||
Funcția validare verifică corectitudinea secvenței calculate de secventa_maxima în raport cu datele de intrare. Funcția verifică lungimea secvenței, suma elementelor și faptul că fiecare element se află în lista inițială. Dacă validarea eșuează, funcția generează o excepție cu un mesaj corespunzător. | |||
În if __name__ == "__main__", apelăm funcțiile citire, secventa_maxima și validare, și apoi afișăm secvența maximă utilizând print(*secventa) (acest lucru afișează elementele secvenței separate prin spații, fără paranteze sau alte simboluri). |
Versiunea de la data 17 aprilie 2023 20:01
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
Fişierul de ieşire secvk.out va conţine pe prima linie k numere, reprezentând elementele secvenței cerute.
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
- 6 6 4
Rezolvare
Rezolvare ver. 1
# 0134 - SecvK
def citire():
n, k = map(int, input().split())
lst = list(map(int, input().split()))
return n, k, lst
def secventa_maxima(n, k, lst):
suma_maxima = 0
secventa_maxima = []
for i in range(n-k+1):
suma = sum(lst[i:i+k])
if suma > suma_maxima:
suma_maxima = suma
secventa_maxima = lst[i:i+k]
return secventa_maxima
def validare(n, k, lst, secventa):
assert len(secventa) == k, "Lungimea secventei nu este k"
assert sum(secventa) == max(sum(lst[i:i+k]) for i in range(n-k+1)), "Suma secventei nu este maxima"
for x in secventa:
assert x in lst, "Elementul {} nu se afla in lista initiala".format(x)
if __name__ == "__main__":
n, k, lst = citire()
secventa = secventa_maxima(n, k, lst)
validare(n, k, lst, secventa)
print(*secventa)
Explicatie Rezolvare
Funcția citire citește datele de intrare și le returnează sub forma unei tuple (n, k, lst). Funcția secventa_maxima calculează secvența de lungime k cu suma maximă din lista lst, utilizând o buclă for și metoda sum. Variabilele suma_maxima și secventa_maxima memorează suma și secvența maximă întâlnită până acum. Funcția validare verifică corectitudinea secvenței calculate de secventa_maxima în raport cu datele de intrare. Funcția verifică lungimea secvenței, suma elementelor și faptul că fiecare element se află în lista inițială. Dacă validarea eșuează, funcția generează o excepție cu un mesaj corespunzător. În if __name__ == "__main__", apelăm funcțiile citire, secventa_maxima și validare, și apoi afișăm secvența maximă utilizând print(*secventa) (acest lucru afișează elementele secvenței separate prin spații, fără paranteze sau alte simboluri).