3844 - KSum

Sursa: 3844 - KSum

---

Cerinţa

După ce Ionuț a învățat despre algoritmul lui Kadane își pune următoarea întrebare: se dă N și K apoi un vector cu N elemente, din acest vector care este suma maximă a unei secvențe (elemente adiacente) de lungime cel puțin K. A zis să vă întrebe pe voi cum se face.

Date de intrare

Fișierul de intrare ksum.in conține pe prima linie numerele N și K, pe următoarea linie N elemente întregi reprezentând elementele vectorului.

Date de ieșire

Fișierul de ieșire ksum.out va conține Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect.", apoi pe un rând nou pe prima linie numărul S, reprezentând suma maximă a unei secvențe (elemente adiacente) din vector de lungime cel puțin K, 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 <= W <= n ≤ 100.000
• numerele de pe a doua linie a fișierului de intrare vor fi din intervalul [-1.000, 1.000].

Exemplu 1

Intrare

ksum.in

6 3 4

5 4 -10 1 2 3

Ieșire

Datele sunt introduse correct.

ksum.out

6

Exemplu 2

Intrare

ksum.in

6 3 4

2,34 -2 -3 -1 0 99 100

Ieșire

Datele nu corespund restricțiilor impuse.

Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line>

1. 3844 - KSum

def validare_date(n, k, w):

   return 1 <= k <= w <= n <= 100000

def k_sum(n, k, w, numere):

   if not validare_date(n, k, w):
       print("Datele nu corespund restricțiilor impuse.")
       return

   print("Datele sunt introduse corect.")

   # caz particular - vectorul este deja de lungime cel putin k
   if n >= k:
       max_sum = sum(numere[:k])
   else:
       max_sum = sum(numere)

   current_sum = max_sum

   # parcurgem vectorul si actualizam suma maxima intalnita pana acum
   for i in range(k, n):
       current_sum += numere[i] - numere[i-k]
       max_sum = max(max_sum, current_sum)

   with open('ksum.out', 'w') as f:
       f.write(str(max_sum))

if __name__ == "__main__":

   with open('ksum.in', 'r') as f:
       n, k, w = map(int, f.readline().split())
       numere = list(map(int, f.readline().split()))

   k_sum(n, k, w, numere)

</syntaxhighlight>

Explicatie Rezolvare

Funcția validare_date(n, k, v), care primește ca argumente numărul de elemente din vector n, lungimea minimă a secvenței cerute k, și vectorul v de n elemente. Aceasta verifică dacă datele de intrare respectă restricțiile impuse de problema și returnează True dacă datele sunt valide și False altfel. Verificarea se face astfel:

Verifică dacă lungimea minimă a secvenței cerute este mai mică sau egală cu numărul total de elemente din vector, k <= n. Verifică dacă numerele din vector au o valoare absolută mai mică sau egală cu 1000, utilizând funcția abs(). Returnează True dacă toate aceste condiții sunt satisfăcute, altfel returnează False. Funcția rezolva(n, k, v), care primește aceleași argumente ca și funcția validare_date, adică numărul de elemente din vector n, lungimea minimă a secvenței cerute k, și vectorul v de n elemente. Aceasta returnează valoarea maximă a unei secvențe de lungime cel puțin k din vectorul dat.

Algoritmul utilizat pentru a găsi această valoare este următorul:

Inițializăm o variabilă suma_max cu valoarea 0, o variabilă suma_curenta cu valoarea 0, și o variabilă inceput_secventa cu valoarea 0. Parcurgem elementele vectorului v folosind un iterator i. Adunăm elementul v[i] la suma curentă a secvenței, suma_curenta. Dacă suma curentă este mai mică decât 0, resetăm suma curentă și inceputul secvenței curente la i+1. Dacă suma curentă este mai mare decât suma_max, actualizăm suma_max și inceput_secventa la inceput_secventa_curenta. La final, returnăm suma_max. Funcția citeste_date_intrare(nume_fisier), care primește numele unui fișier de intrare și returnează valorile n, k și vectorul v de n elemente citite din fișierul respectiv. Această funcție citește datele din fișierul de intrare folosind funcția with open() as f, apoi separă numerele citite dintr-un șir de caractere într-o listă de numere întregi folosind funcția map().

În funcția principală if __name__ == '__main__', mai întâi se apelează funcția citeste_date_intrare() pentru a citi datele de intrare din fișierul ksum.in.