Editing 0134 - SecvK

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 == 
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 ===
<syntaxhighlight lang="python" line>
# 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.