==Include(page="template/taskheader" task_id="invsort")==
 
==Include(page="template/raw")==
 
Invsort
 
 
 
Se da un sir de N numere naturale, care trebuie ordonat crescator. Singura operatie permisa este sa considerati elementele de pe pozitiile i, i+1, ..., j (pentru i si j arbitrare, i<j), si sa inversati ordinea acestor elemente (adica elementul de pe pozitia i ajunge pe pozitia j, i+1 ajunge pe pozitia j-1, ..., j ajunge pe pozitia i). Costul unei astfel de operatii este numarul de elemente din subsirul inversat, si anume j-i+1.
 
h2. Cerinta
 
Scrieti un program care sa determine o secventa de operatii care ordoneaza crescator sirul dat si are un cost total cat mai mic (dar nu obligatoriu minim).
 
h2. Date de Intrare
 
Fisierul de intrare invsort.in contine pe prima linie numarul N, si apoi N linii cu elementele sirului dat (nu neaparat distincte).
 
h2. Date de Iesire
 
Fisierul de iesire invsort.out va contine pe fiecare linie descrierea unei operatii. O operatie este descrisa prin numerele i si j, separate printr-un spatiu. Aceste numere satisfac 1 <= i < j <= N.
 
h2. Restrictii
 
 
 
. 2 <= N <= 32000
 
. valorile sirului care trebuie ordonat sunt intre 0 si 31999
 
 
 
Punctaj
 
. daca sirul de operatii (executate in ordinea din fisierul de iesire) nu ordoneaza intrarea, primiti 0 puncte
 
. in cazul in care costul total este cel mult 4000000 (patru milioane) primiti punctaj maxim
 
. in cazul in care costul total este cel mult 40000000 (patruzeci de milioane) primiti 40% din punctajul pe test
 
. in 50% din teste sirul de intrare contine numai elemente de 0 si 1
 
. pentru toate testele folosite la corectare, N=32000
 
h2. Exemplu
 
 
 
 
|invsort.in |invsort.out |Explicatie |
 
|5 |3 5 |. prima operatie are efectul: 1 0 [1 1 0] (R) 1 0 0 1 1 |
| | | |
|1 |1 3 |. a doua operatie are efectul: [1 0 0] 1 1 (R) 0 0 1 1 1 |
| | | |
|0 | |. costul total este 3 + 3 = 6 |
| | | |
|1 | | |
| | | |
|1 | | |
| | | |
|0 | | |

==Include(page="template/taskheader" task_id="invsort")==
 
Se da un sir de $N$ numere naturale, care trebuie ordonat crescator. Singura operatie permisa este sa considerati elementele de pe pozitiile $i, i+1, ..., j$ (pentru $i$ si $j$ arbitrare, $i<j$), si sa inversati ordinea acestor elemente (adica elementul de pe pozitia $i$ ajunge pe pozitia $j$, $i+1$ ajunge pe pozitia $j-1$, ..., $j$ ajunge pe pozitia $i$). Costul unei astfel de operatii este numarul de elemente din subsirul inversat, si anume $j-i+1$.
 
h2. Cerinta
 
Scrieti un program care sa determine o secventa de operatii care ordoneaza crescator sirul dat si are un cost total cat mai mic (dar nu obligatoriu minim).
 
h2. Date de Intrare
 
Fisierul de intrare $invsort.in$ contine pe prima linie numarul $N$, si apoi $N$ linii cu elementele sirului dat (nu neaparat distincte).
 
h2. Date de Iesire
 
Fisierul de iesire $invsort.out$ va contine pe fiecare linie descrierea unei operatii. O operatie este descrisa prin numerele $i$ si $j$, separate printr-un spatiu. Aceste numere satisfac $1 &le; i < j &le; N$.
 
h2. Restrictii
 
* $2 &le; N &le; 32000$
* valorile sirului care trebuie ordonat sunt intre $0$ si $31999$
 
h2. Punctaj
 
* daca sirul de operatii (executate in ordinea din fisierul de iesire) nu ordoneaza intrarea, primiti $0$ puncte
* in cazul in care costul total este cel mult $4000000$ (patru milioane) primiti punctaj maxim
* in cazul in care costul total este cel mult $40000000$ (patruzeci de milioane) primiti $40%$ din punctajul pe test
* in $50%$ din teste sirul de intrare contine numai elemente de $0$ si $1$
* pentru toate testele folosite la corectare, $N=32000$
 
h2. Exemplu
 
table(example). |_. invsort.in |_. invsort.out |
| 5
1
0
1
1
0 | 3 5
1 3 |
 
h3. Explicatie
 
* prima operatie are efectul: $1 0 [1 1 0] -> 1 0 0 1 1$
* a doua operatie are efectul: $[1 0 0] 1 1 ->  0 0 1 1 1$
* costul total este $3 + 3 = 6$
 
==Include(page="template/taskfooter" task_id="invsort")==

==Include(page="template/taskfooter" task_id="invsort")==

2286