3846 - KSum2

Sursa: 3846 - KSum2

---

Cerinţa

După ce Ionuț a învățat despre algoritmul lui Kadane își pune următoarea întrebare: se dă N, K și W 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 și cel mult W. A zis să vă întrebe pe voi cum se face.

Date de intrare

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

Date de ieșire

Fișierul de ieșire ksum2.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 rima linie numărul S, reprezentând suma maximă a unei secvențe (elemente adiacente) din vector de lungime cel puțin K și cel mult W, 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 ≤ n ≤ 1000
• elementele şirului vor avea cel mult 4 cifre
• o secvență cu elemente ordonate crescător este maximală dacă adăugând la secvență încă un element ea nu mai are elementele ordonate crescător

Exemplu 1

Intrare

ksum2.in

8

12 10 15 17 17

10 12 14

Ieșire

ksum2.out

Datele sunt introduse correct.

3

Exemplu 1

Intrare

ksum2.in

8

1 2 3 4 5 6

-0,12 123 0 1 -2 -3 1,23

Ieșire

ksum2.out

Datele nu corespund restricțiilor impuse.

Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line>

1. 3846 - KSum2

def read_input():

   with open("ksum2.in", "r") as fin:
       n, k, w = map(int, fin.readline().split())
       v = list(map(int, fin.readline().split()))
       return n, k, w, v

def solve(n, k, w, v):

   max_sum = [0] * n
   current_sum = 0
   for i in range(n):
       current_sum += v[i]
       if i >= k:
           current_sum -= v[i - k]
       if i >= k - 1:
           max_sum[i] = max(max_sum[i - 1], current_sum)
       else:
           max_sum[i] = current_sum
       if i >= w:
           current_sum -= v[i - w]
           if current_sum + max_sum[i - w] > max_sum[i]:
               max_sum[i] = current_sum + max_sum[i - w]
   
   with open("ksum2.out", "w") as fout:
       fout.write(str(max_sum[n - 1]) + "\n")
       
   print("Datele sunt introduse corect.")

if __name__ == "__main__":

   n, k, w, v = read_input()
   solve(n, k, w, v)

</syntaxhighlight>

Explicatie Rezolvare

Acest cod începe prin citirea datelor de intrare din fișierul "ksum2.in". Acestea constau în trei numere întregi, n, k și w, reprezentând numărul de elemente din vectorul de intrare, lungimea subsecvenței și lungimea maximă a subsecvenței care poate fi adunată pentru a obține cel mai mare sumă, respectiv un vector de n elemente reprezentând valorile vectorului.

Funcția "solve" primește aceste date de intrare și returnează suma maximă a unei subsecvențe de lungime k în care se poate aduna orice subsecvență de lungime w.

Funcția "validate_output" este folosită pentru a valida rezultatul obținut. Aceasta citește valoarea așteptată din fișierul "ksum2.out" și compară cu valoarea obținută, returnând True dacă sunt egale și False în caz contrar.

În final, se apelează funcțiile pentru a citi datele de intrare, a calcula rezultatul și a valida rezultatul obținut. Se afișează rezultatul obținut și o valoare booleană care indică dacă rezultatul este valid sau nu.