3846 - KSum2: Diferență între versiuni

De la Universitas MediaWiki
(Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/3846/ksum2 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 ș...)
 
Fără descriere a modificării
Linia 10: Linia 10:


== Date de ieșire ==  
== Date de ieșire ==  
Fișierul de ieșire ksum2.out va conține pe prima 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.
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 '''numărul c''', 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 ==
Linia 22: Linia 24:
: 10 12 14
: 10 12 14
; Ieșire
; Ieșire
: Datele nu corespund restricțiilor impuse.
: Datele sunt introduse correct.
: 3
: 3


Linia 50: Linia 54:
             if current_sum + max_sum[i - w] > max_sum[i]:
             if current_sum + max_sum[i - w] > max_sum[i]:
                 max_sum[i] = current_sum + max_sum[i - w]
                 max_sum[i] = current_sum + max_sum[i - w]
     return max_sum[n - 1]
      
 
     with open("ksum2.out", "w") as fout:
def validate_output(output_file, result):
         fout.write(str(max_sum[n - 1]) + "\n")
     with open(output_file, "r") as fin:
          
         expected_result = int(fin.readline().strip())
    print("Datele sunt introduse corect.")
         return result == expected_result


if __name__ == "__main__":
if __name__ == "__main__":
     n, k, w, v = read_input()
     n, k, w, v = read_input()
     result = solve(n, k, w, v)
     solve(n, k, w, v)
    is_valid = validate_output("ksum2.out", result)
 
    print(result)
    print("Result is valid:", is_valid)




</syntaxhighlight>
</syntaxhighlight>
== Explicatie Rezolvare ==
== Explicatie Rezolvare ==
Pentru rezolvarea acestei probleme putem adapta algoritmul lui Kadane pentru a căuta suma maximă a unei secvențe de lungime cel puțin K și cel mult W.


Putem folosi o listă auxiliară max_sum în care vom memora suma maximă până la fiecare element din vector. În mod similar cu algoritmul lui Kadane, dacă suma până la un anumit element este negativă, o vom ignora și vom începe o nouă secvență de la acel element.
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.


Diferența constă în faptul că trebuie să verificăm la fiecare pas dacă am ajuns la un element din intervalul [K, W], iar în acest caz, dacă suma maximă până la acel element este mai mare decât suma maximă găsită anterior, vom actualiza această valoare.
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, vom returna suma maximă găsită pentru o secvență de lungime cel puțin K și cel mult W.
Î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.

Versiunea de la data 28 aprilie 2023 15:00

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 numărul c, 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

Intrare
8:
12 10 15 17 17
10 12 14
Ieșire
Datele nu corespund restricțiilor impuse.
Datele sunt introduse correct.
3

Rezolvare

Rezolvare ver. 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)

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.

Adus de la „http://wiki.universitas.ro/index.php?title=3846_-_KSum2&oldid=5228”