3846 - KSum2: Difference between revisions

From Bitnami MediaWiki
Flaviu (talk | contribs)
No edit summary
Flaviu (talk | contribs)
No edit summary
Line 12: Line 12:
Fișierul de ieșire ksum2.out va conține:
Fișierul de ieșire ksum2.out va conține:
Dacă datele sunt introduse corect, pe ecran se va afișa:  
Dacă datele sunt introduse corect, pe ecran se va afișa:  
'''"Datele sunt introduse corect."''', apoi pe un rând nou '''numărul c''', reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: '''"Datele nu corespund restricțiilor impuse."'''.
'''"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 ==
== Restricţii şi precizări ==
Line 18: Line 18:
* elementele şirului vor avea cel mult 4 cifre
* 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
* 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 ==
== Exemplu 1 ==
; Intrare
; Intrare
: 8:
: ksum2.in
: 8  
: 12 10 15 17 17
: 12 10 15 17 17
: 10 12 14
: 10 12 14
; Ieșire
; Ieșire
: Datele nu corespund restricțiilor impuse.
: ksum2.out
: Datele sunt introduse correct.
: Datele sunt introduse correct.
: 3
: 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 ==  

Revision as of 08:13, 3 May 2023

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.