3844 - KSum: Difference between revisions

Revision as of 07:23, 18 April 2023

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 pe prima linie numărul S, reprezentând suma maximă a unei secvențe (elemente adiacente) din vector de lungime cel puțin K.

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

Intrare: 6 3 4; 5 4 -10 1 2 3
Ieșire: 6

Rezolvare

Rezolvare ver. 1

3844 - KSum

def read_input_file():

   with open("ksum.in", "r") as input_file:
       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):

   s = [0] * (n + 1)
   for i in range(1, n + 1):
       s[i] = s[i-1] + v[i-1]
   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):

   with open("ksum.out", "w") as output_file:
       output_file.write(str(result))

if __name__ == '__main__':

   n, k, v = read_input_file()
   result = ksum(n, k, v)
   write_output_file(result)

</syntaxhighlight>

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. 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. 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.

@@ Line 1: / Line 1: @@
-Sursa: [https://www.pbinfo.ro/probleme/304/secvente 3844 - KSum]
+Sursa: [https://www.pbinfo.ro/probleme/3844/ksum 3844 - KSum]
 ----
 == Cerinţa ==
@@ Line 13: / Line 13: @@
 == Restricţii şi precizări ==
-* 1 ≤ K <= n ≤ 100.000
+* 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 ==
 ; Intrare
-: 6 3
+: 6 3 4
 : 5 4 -10 1 2 3
 ; Ieșire
@@ Line 27: / Line 27: @@
 # 3844 - KSum
-def citeste_date_intrare():
+def read_input_file():
-     n = int(input())
+     with open("ksum.in", "r") as input_file:
-    sir = []
+        n, k = map(int, input_file.readline().split())
-    for i in range(n):
+        v = list(map(int, input_file.readline().split()))
-        sir.append(int(input()))
+        return n, k, v
-    return sir
-def numara_secvente_crescatoare(sir):
+def ksum(n, k, v):
-     numar_secvente = 0
+     s = [0] * (n + 1)
-    lungime_maxima = 1
+     for i in range(1, n + 1):
-    lungime_curenta = 1
+         s[i] = s[i-1] + v[i-1]
-     for i in range(1, len(sir)):
+    m = [0] * (n + 1)
-         if sir[i] >= sir[i-1]:
+     for i in range(k, n + 1):
-            lungime_curenta += 1
+         m[i] = max(m[i-1], s[i] - s[i-k])
-        else:
+     return max(m)
-            if lungime_curenta > lungime_maxima:
-                lungime_maxima = lungime_curenta
-                numar_secvente = 1
-            elif lungime_curenta == lungime_maxima:
-                numar_secvente += 1
-            lungime_curenta = 1
-     if lungime_curenta > lungime_maxima:
-        lungime_maxima = lungime_curenta
-        numar_secvente = 1
-    elif lungime_curenta == lungime_maxima:
-         numar_secvente += 1
-     return numar_secvente
-def valideaza(sir, numar_secvente):
+def write_output_file(result):
-     assert len(sir) > 0
+    with open("ksum.out", "w") as output_file:
-     assert numar_secvente >= 0
+        output_file.write(str(result))
+if __name__ == '__main__':
+     n, k, v = read_input_file()
+     result = ksum(n, k, v)
+    write_output_file(result)
-if __name__ == "__main__":
-    sir = citeste_date_intrare()
-    numar_secvente = numara_secvente_crescatoare(sir)
-    valideaza(sir, numar_secvente)
-    print(numar_secvente)
 </syntaxhighlight>
 == Explicatie Rezolvare ==
-Pentru a rezolva această problemă, putem utiliza o metodă numită "maximum subarray problem", care constă în găsirea subsecvenței continue a unui șir dat, care are cea mai mare sumă. Putem utiliza o variantă a algoritmului Kadane, care funcționează în timp liniar.
+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.
+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.
+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.