3844 - KSum: Difference between revisions

From Bitnami MediaWiki
Flaviu (talk | contribs)
No edit summary
Flaviu (talk | contribs)
No edit summary
Line 22: Line 22:
: 5 4 -10 1 2 3
: 5 4 -10 1 2 3
; Ieșire
; Ieșire
: Datele sunt introduse correct.
: ksum.out
: ksum.out
: Datele sunt introduse correct.
: 6
: 6


Line 32: Line 32:
: 2,34 -2 -3 -1 0 99 100
: 2,34 -2 -3 -1 0 99 100
; Ieșire
; Ieșire
: ksum.out
: Datele nu corespund restricțiilor impuse.
: Datele nu corespund restricțiilor impuse.


Line 42: Line 41:
# 3844 - KSum
# 3844 - KSum


def read_input_file():
def validare_date(n, k, w):
     with open("ksum.in", "r") as input_file:
     return 1 <= k <= w <= n <= 100000
        n, k = map(int, input_file.readline().split())
 
        v = list(map(int, input_file.readline().split()))
        return n, k, v


def ksum(n, k, v):
def k_sum(n, k, w, numere):
     s = [0] * (n + 1)
     if not validare_date(n, k, w):
    for i in range(1, n + 1):
         print("Datele nu corespund restricțiilor impuse.")
        s[i] = s[i-1] + v[i-1]
        return
    m = [0] * (n + 1)
    for i in range(k, n + 1):
         m[i] = max(m[i-1], s[i] - s[i-k])
    return max(m)


def write_output_file(result):
     print("Datele sunt introduse corect.")
     with open("ksum.out", "w") as output_file:
        output_file.write(str(result))


if __name__ == '__main__':
     # caz particular - vectorul este deja de lungime cel putin k
     n, k, v = read_input_file()
     if n >= k:
     result = ksum(n, k, v)
         max_sum = sum(numere[:k])
    if result > 0:
         print("Datele sunt introduse corect.")
     else:
     else:
         print("Datele nu corespund restricțiilor impuse.")
         max_sum = sum(numere)
     write_output_file(result)
 
    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>
</syntaxhighlight>
== Explicatie Rezolvare ==
== Explicatie Rezolvare ==
functia read_input_file citeste datele de intrare din fisier si le returneaza sub forma de tuplu (n, k, v), unde n este numarul de elemente din vector, k este numarul minim de elemente consecutive care trebuie sa fie considerate in calculul sumei, iar v este lista cu elementele vectorului.
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:
functia ksum primeste ca parametri n, k si v, si calculeaza suma maxima a unei secvente de lungime cel putin k. Pentru a gasi suma maxima se calculeaza suma elementelor de la 1 la i, pentru fiecare i din vectorul s. De asemenea, se construieste un alt vector, m, care contine pentru fiecare pozitie i din vectorul s, suma maxima a unei secvente de lungime cel putin k care se termina in pozitia i. Suma maxima se va gasi in ultimul element al vectorului m.
 
functia write_output_file scrie rezultatul obtinut in fisierul de iesire.
Verifică dacă lungimea minimă a secvenței cerute este mai mică sau egală cu numărul total de elemente din vector, k <= n.
in cadrul if __name__ == '__main__': se apeleaza cele trei functii in ordinea: citirea datelor de intrare, calculul solutiei si scrierea rezultatului in fisierul de iesire.
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.

Revision as of 21:58, 14 May 2023

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.