minim

Minim

== include(page="template/taskheader" task_id="minim") ==
 
Poveste ...
 
h2. Cerinta
 
...
 
h2. Restrictii
 
...
 
h2. Date de intrare
 
...
 
h2. Date de iesire
 
...
 
h2. Exemplu
 
| minim.in | minim.out |
| linia1
linia2
linia3
| linia1
linia2
|
 
== include(page="template/taskfooter" task_id="minim") ==

==Include(page="template/taskheader" task_id="minim")==
==Include(page="template/raw")==
 
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.
 
h2. 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.
 
h2. 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.
 
h2. 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.
 
h2. Restrictii si precizari
 
. 5 -L- n -L- 1000 ;
 
. -10000 -L- nr[i] -L- 10000 (i = 1, 2, ..., n).
 
h2. 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
 
 
==Include(page="template/taskfooter" task_id="minim")==