Fişierul intrare/ieşire:minim.in, minim.outSursăGrigore Moisil By Net 2006
AutorClara IonescuAdăugată de
Timp execuţie pe test0.05 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

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 mic. 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 ≤ n ≤ 1000
  • -10000 ≤ nr[i] ≤ 10000 (i = 1, 2, ..., n)

Exemplu

minim.inminim.out
10
6
-8
-2
-4
-6
20
-10
-3
12
-19
-20 2 5
-20 7 10
6 1 1
20 6 6
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content