Revizia anterioară Revizia următoare
Fişierul intrare/ieşire: | minim.in, minim.out | Sursă | Grigore Moisil By Net 2006 |
Autor | Clara Ionescu | Adăugată de | |
Timp execuţie pe test | 0.025 sec | Limită de memorie | 65536 kbytes |
Scorul tău | N/A | Dificultate |
Vezi solutiile trimise | Statistici
Minim
Aceasta pagina a fost importata din infoarena1 si nu este inca prelucrata. Sterge ==Include(file="template/raw")== cand esti multumit cu continutul paginii. |
---|
Minim
Se considera un sir de n numere intregi.
In problema vom lucra cu subsecvente. Precizam ca elementele unei subsecvente sunt elemente avand indici consecutivi in sirul considerat.
Cerinta
Sa se determine subsecventa de suma minima a sirului care are lungimea minima. Daca exista mai multe astfel de subsecvente, sa se elimine cea care are indicele de inceput mai mica. Sa se elimine aceasta subsecventa din sir, apoi sa se determine o alta subsecventa de lungime minima printre cele care au suma minima dintre elementele ramase in sir. Sa se continue procedeul, pana cand sirul devine vid.
Date de Intrare
. Pe prima linie a fisierului minim.in se afla numarul natural n, reprezentand dimensiunea sirului.
. Pe urmatoarele n linii se afla cate un numar intreg.
Date de Iesire
. In fisierul de iesire minim.out se vor scrie k triplete, unde k este numarul subsecventelor depistate.
. Un triplet aflat pe cea de a i-a linie a fisierului este format din numerele s, p, u, unde s reprezinta suma celei de a i-a subsecvente, p reprezinta indicele primului element al subsecventei, iar u este indicele ultimului element al subsecventei. Indicii p si u sunt indicii elementelor respective in sirul original.
. Cele trei numere vor fi despartite prin cate un spatiu.
Restrictii si precizari
. 5 L n L 1000 ;
. 10000 -L nr[i] L 10000 (i = 1, 2, ..., n).
Exemplu
minim.in minim.out
10 -20 2 5
6 -20 7 10
-8 6 1 1
-2 20 6 6
-4
-6
20
-10
-3
12
-19