4283 - Low Mem 1

From Bitnami MediaWiki
Revision as of 16:35, 13 December 2023 by Raul (talk | contribs) (Pagină nouă: = Cerința = Se citește din fișierul <code>lowmem1.in</code> de pe prima linie un număr <code>k</code>, iar de pe a doua linie un șir de cel mult <code>1.000.000</code> '''numere întregi''', de cel mult <code>9</code> cifre fiecare. Să se determine valoarea maximă <code>S</code>, care se poate obține prin însumarea a <code>k</code> numere consecutive și secvența de numere care formează această sumă maximă. = Date de intrare = Fișierul de intrare <code>lowmem...)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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

Lipește codul aici

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