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.", 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()

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__':`.