4283 - Low Mem 1
Cerința
Se citește din fișierul lowmem1.in
de pe prima linie un număr k
, iar de pe a doua linie un șir de cel mult 1.000.000
numere întregi, de cel mult 9
cifre fiecare. Să se determine valoarea maximă S
, care se poate obține prin însumarea a k
numere consecutive și secvența de numere care formează această sumă maximă.
Date de intrare
Fișierul de intrare lowmem1.in
conține pe prima linie numărul k
, iar pe a doua linie numerele întregi cuprinse în intervalul (
, ).
Date de ieșire
Fișierul de ieșire lowmem1.out
va conține pe prima linie numărul S
, reprezentând suma celor k
elemente aflate pe poziții consecutive, iar pe a doua linie aceste elemente din secvență.
Restricții și precizări
1 ≤ k ≤ 11000
k
mai mic decât numărul de numere din fișierul de intrare- dacă avem mai multe secvențe de
k
elemente care formează suma maximă, se va afișa prima dintre ele
Exemplu:
lowmem1.in
5 15 3 -12 -7 8 22 -1 3 -14 33 -18 10
lowmem1.out
43 22 -1 3 -14 33
Explicație
În fișierul de intrare cele 5
numere de pe poziții consecutive care adunate dau suma maximă 43
, sunt 22 -1 3 -14 33
.
Încărcare soluție
<syntaxhighlight lang="ada2005" line="1"> import sys import math
n, k, i, x, dr, st = 0, 0, 0, 0, 0, 0 v = [0] * 11005 s, maxx = 0, -sys.maxsize - 1
with open("lowmem1.in", "r") as f:
k = int(f.readline()) for i in range(k): v[i] = int(f.readline()) s += v[i] maxx = s while True: line = f.readline() if not line: break x = int(line) s = s + x - v[i % k] v[i % k] = x if s > maxx: maxx = s dr = i i += 1
st = dr - k + 1
with open("lowmem1.out", "w") as g:
g.write(str(maxx) + "\n")
with open("lowmem1.in", "r") as f:
k = int(f.readline()) i = 0 while True: line = f.readline() if not line: break x = int(line) if i >= st and i <= dr: g.write(str(x) + " ") i += 1 if i > dr: break
</syntaxhighlight>