O subsecventa a un sir este formata din niste elemente ale sirului aflate pe
pozitii consecutive.
Exemplu: Pentru sirul "1 2 3 4 5 6 7"; "1 2 3", "2
3 4 5 6 7" si "3 4 5" sunt subsecvente, dar "1 3 4"
nu este deoarece intre 1 si 3 mai exista si alte elemente (in cazul nostru 2).
Cerinta
Fiind dat un sir A cu numere intregi, se cere sa se gaseasca subsecventa care
are modulul sumei minim.
Date de intrare
Pe prima linie a fisierului suma3.in
se gaseste numarul N reprezentand lungimea sirului. Pe urmatoarele
N linii se afla elementele sirului (cate unul pe fiecare linie).
Date de iesire
Pe prima linie a fisierului suma3.out
se vor gasi 3 numere: S I J cu semnificatia: S este numarul cerut (modulul minim al sumei unei subsecvente), I si J sunt capetele subsecventei gasite.
Restrictii
N <= 100 000
-2 000 000 000 < A[I] < 2 000 000 000
I si J trebuie sa respecte urmatoarele conditii:
I <= J, modul(A[I]+..+A[J])=S
Subsecventele pot avea suma mai mari decat 2 000 000 000
Subsecventele pot avea suma mai mici decat -2 000 000 000
Se recomanda folosirea unor intregi pe 64 biti
Subsecventa din fisierul de iesire trebuie sa contina cel putin
un numar
Toate numerele sunt intregi
S >= 0
Daca exista mai multe solutii se va scrie doar una.
Exemple
suma3.in
suma3.out
5
1
2
-10
3
4
0
1 5
suma3.in
suma3.out
9
1000
2
4
8
16
32
64
-127
-2000
1 2 8
suma3.in
suma3.out
3
1
2
3
1 1 1
Mod de punctare:
Daca modulul sumei este minim atunci se primeste 1 punct. Daca in plus subsecventa
gasita este corecta si are modului sumei S atunci se primesc inca 4 puncte (adica
5 in total). Atentie: Daca S este gresit se primesc 0 puncte (chiar daca subsecventa
este corecta).
Daniel Dumitran
Universitatea Politehnica Bucuresti