==Include(page="template/taskheader" task_id="subsir2")==
==Include(page="template/raw")==
Link: [1]File-List
Subsir 2
Bronzarel se antreneaza zi de zi pentru a deveni un mare olimpic la informatica, avandu-l pe Zaharel ca mentor/guru. Desigur, sursa lor preferata de probleme este info-arena! Astazi, Bronzarel a rezolvat seria de probleme "Secventa X" (X = 1, 2 3, ...). Vazandu-l foarte increzator, Zaharel vrea sa-l testeze pe Bronzarel cu o noua problema care nu este (inca) pe info-arena si ii spune: "Iti dau un sir de N numere intregi si vreau sa-mi spui care este cel mai scurt subsir crescator maximal. La probleme cu secvente te-ai descurcat, vei reusi si la subsiruri?"
h2. Cerinta
Imaginati-va ca sunteti in locul lui Bronzarel si scrieti un program care rezolva problema primita.
h2. Date de Intrare
Pe prima linie din fisierul subsir2.in se va gasi numarul N. Pe urmatoarea linie vor fi scrie N numere intregi.
h2. Date de Iesire
Prima linie din fisierul subsir2.out va contine un numar L[min], reprezetand lungimea minima a unui subsir crescator maximal. Pe urmatoarea linie se vor afisa L[min] numere in ordine crescatoare, reprezetand poziitile elementelor din sirul initial care fac parte din subsirul ales. Daca exista mai multe solutii, se va afisa cea lexicografic minima , din punct de vedere al valorilor elementelor din subsir.
h2. Restrictii si observatii
S 1 <= N <= 5.000
S 50% din teste vor avea N <= 500
S Sirul dat va contine numere intregi din intervalul [-1.000.000, 1.000.000]
S Considerand ca sirul dat este A=(a[1],a[2]...a[N]) se numeste subsir al lui A, un sir B=(a[i1],a[i2]...a[iK]) cu proprietatea 1<=i[1]<i[2]<...<i[K]<=N.
S Spunem ca un subsir B=(a[i1],a[i2]...a[ik]) este crescator maximal daca a[i1]<=a[i2]<=...<= a[iK] si nu exista nici un x astfel incat: sa existe j<K, i[j]<x<i[j+1] si a[ij]<=a[x]<= a[ij+1,]sau 1<=x<i[1] si a[x]<=a[i1,] sau i[K]<x<=N si a[iK] <= a[x
]S Pentru fiecare test se va acorda 40% din punctaj pentru determinarea corecta a lungimii subsirului, inca 40% pentru determinarea unei solutii corecte, si inca 20% daca solutia determinata este minima din punct de vedere lexicografic
S Un sir (x[1],x[2]...x[K]) este mai mic din punct de vedere lexicografic decat un alt sir (y[1],y[2]...y[K]) daca exista o pozitie p astfel incat x[p]<y[p] si x[1]=y[1,] x[2]=y[2,] ... [,]x[p-1]=y[p-1
]
h2. Exemplu
subsir2.in subsir2.out Explicatie
6 3 Subsirul cu elemente pe poziiile 1,4,6 este (1,2,4). Acesta este maximal si are lungime minima. Alte subsiruri maximale de aceeasi lungime sunt:
1 3 6 2 5 4 1 4 6 (1,2,5)
(1,3,4)
(1,3,5)
Solutia data este minima lexicografic din punct de vedere al valorilor elementelor subsirului.
==Include(page="template/taskheader" task_id="subsir2")==
Bronzarel se antreneaza zi de zi pentru a deveni un mare olimpic la informatica, avandu-l pe Zaharel ca mentor. Desigur, sursa lor preferata de probleme este infoarena! Vazandu-l foarte increzator, Zaharel vrea sa-l testeze pe Bronzarel cu o noua problema si ii spune: "Iti dau un sir de $N$ numere intregi si vreau sa imi spui care este cel mai scurt _subsir crescator maximal_."
h2. Cerinta
Scrieti un program care rezolva problema primita.
h2. Date de intrare
Pe prima linie din fisierul $subsir2.in$ se va gasi numarul $N$. Pe urmatoarea linie vor fi scrie $N$ numere intregi.
h2. Date de iesire
Prima linie din fisierul $subsir2.out$ va contine un numar $L{~min~}$, reprezetand lungimea minima a unui subsir crescator maximal. Pe urmatoarea linie se vor afisa $L{~min~}$ numere in ordine crescatoare, reprezetand poziitile elementelor din sirul initial care fac parte din subsirul ales. Daca exista mai multe solutii, se va afisa cea lexicografic minima, din punct de vedere al valorilor elementelor din subsir.
h2. Restrictii si observatii
* $1 ≤ N ≤ 5 000$
* $50%$ din teste vor avea $N ≤ 500$
* Sirul dat va contine numere intregi din intervalul $[-1 000 000, 1 000 000]$
* Considerand ca sirul dat este {$A=(a{~1~},a{~2~}...a{~N~})$}, se numeste subsir al lui $A$ un sir {$B=(b{~i{~1~}~},b{~i{~2~}~}...b{~i{~N~}~})$} cu proprietatea $1 ≤ i{~1~} < i{~2~} < ... < i{~K~} ≤ N$.
* Spunem ca un subsir {$B=(b{~i{~1~}~},b{~i{~2~}~}...b{~i{~N~}~})$} este _crescator maximal_ daca {$a{~i{~1~}~} ≤ a{~i{~2~}~} ≤ ... ≤ a{~i{~K~}~}$} si nu exista nici un $x$ astfel incat: sa existe $j < K$, {$i{~j~} < x < i{~j+1~}$} si {$a{~i{~j~}~} ≤ a{~x~} ≤ a{~i{~j+1~}~}$}, sau {$1 ≤ x < i{~1~}$} si {$a{~x~} ≤ a{~i{~1~}~}$} sau {$i{~K~} < x ≤ N$} si {$a{~i{~K~}~} <= a{~x~}$}
* Pentru fiecare test se va acorda $40%$ din punctaj pentru determinarea corecta a lungimii subsirului, inca $40%$ pentru determinarea unei solutii corecte, si inca $20%$ daca solutia determinata este minima din punct de vedere lexicografic
* Un sir {$(x{~1~},x{~2~}...x{~K~})$} este mai mic din punct de vedere lexicografic decat un alt sir {$(y{~1~},y{~2~}...y{~K~})$} daca exista o pozitie $p$ astfel incat {$x{~p~} < y{~p~}$} si {$x{~1~} = y{~1~}$}, {$x{~2~} = y{~2~}$} ... {$x{~p-1~} = y{~p-1~}$}.
h2. Exemplu
table(example). |_. subsir2.in|_. subsir2.out|
|6
1 3 6 2 5 4
|3
1 4 6|
_Explicatie_: Subsirul cu elemente pe poziiile {$1$},{$4$},{$6$} este {$(1,2,4)$}. Acesta este maximal si are lungime minima. Alte subsiruri maximale de aceeasi lungime sunt:
{$(1,2,5)$}
{$(1,3,4)$}
{$(1,3,5)$}
Solutia data este minima lexicografic din punct de vedere al valorilor elementelor subsirului.
==Include(page="template/taskfooter" task_id="subsir2")==
References
Visible links
1. file:///home/eval/eval/www/infoarena/docs/arhiva/subsir2/enunt.files/filelist.xml
==Include(page="template/taskfooter" task_id="subsir2")==
