ACM RTK - 1. skupina

Dano je zaporedje n celih števil, recimo jim a₁, a₂, ..., a_n-1, a_n. Vsa števila so večja od 0.  Poleg tega je dano tudi celo število m. Opiši postopek (algoritem), ki poišče v tem zaporedju najkrajše tako strnjeno podzaporedje, pri katerem je vsota števil v podzaporedju večja od m. Poišče naj torej tak začetni indeks z in dolžino podzaporedja d, da bo a_z + a_z+1 + a_z+2 + ...  + a_{z + d - 2}+ a_{z + d - 1} > m
in da bo $d$ čim manjši.

Tvoj postopek naj bo čim bolj učinkovit, tako da bo hitro našel pravi odgovor tudi pri zelo dolgih zaporedjih (takih z nekaj milijoni členov). Bolj učinkovite rešitve dobijo več točk.

Primer: recimo, da imamo zaporedje

5, 6, 5, 6, 9, 9, 9, 6

in m = 24.  Najkrajše strnjeno podzaporedje z vsoto, večjo od m, je dolgo 3 člene: 9 + 9+ 9 = 27, kar je večje od 24. (Do vsote 25 pri tem primeru ne moremo priti z nobenim strnjenim podzaporedjem, do vsote 26 pa sicer lahko, vendar potrebujemo za to vsaj štiri člene: 6 + 5 + 6 + 9 = 26.)  Pravilni rezultat pri tem primeru je torej z = 5, d = 3.

Pri tej nalogi ti ni treba pisati programa ali podprograma v kakšnem konkretnem programskem jeziku (lahko pa, če ti je lažje).  Tvoj postopek sme predpostaviti, da so števila že podana v nekakšni tabeli ali seznamu, na primer takole:

const int n = ...;             /* v C/C++ */
int a[n];

const n = ...;                 { v pascalu }
var a: array [0..n-1] of integer;

int[] a = ...;                 // v javi
int n = a.length;

a = [...]                      # v pythonu
n = len(a)

<PDF>