== include(page="template/taskheader" task_id="specsort") ==
Se consideră o permutare a mulţimii ${1, 2, …, N}$. Pentru această permutare se defineşte un singur tip de operaţie: se extrage din permutare un subşir, iar elementele subşirului se adaugă (în aceeaşi ordine) la începutul permutării. De exemplu, pentru permutarea $(3, 1, 5, 2, 6, 4)$, se poate alege subşirul $(1, 2, 4)$ care se introduce la începutul permutării, obţinându-se $(1, 2, 4, 3, 5, 6)$.
h2. Cerinta
Să se sorteze elementele din permutare efectuând un număr cât mai mic de operaţii.
Poveste şi cerinţă...
h2. Date de intrare
Fişierul $specsort.in$ conţine pe prima linie numărul natural $N$, iar pe linia a doua, separate prin câte un spaţiu, cele $N$ elemente ale permutării.
Fişierul de intrare $specsort.in$ ...
h2. Date de ieşire
Fişierul $specsort.out$ conţine un număr de linii egal cu numărul de operaţii efectuate. Pe a $i$-a dintre aceste linii se găsesc câte $N$ numere naturale separate printr-un spaţiu, reprezentând permutarea obţinută după aplicarea celei de a $i$-a operaţie.
În fişierul de ieşire $specsort.out$ ...
h2. Restricţii
* $1 ≤ N ≤ 50 000$
* Atentie! Numarul de operatii nu trebuie neaparat sa fie minim. Exista totusi, problema "aceasta":http://acm.timus.ru/problem.aspx?space=1&num=1568 care cere numar minim de operatii..
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. specsort.in |_. specsort.out |
| 7
7 4 5 1 3 6 2
| 6 7 4 5 1 3 2
4 5 6 7 1 3 2
1 2 4 5 6 7 3
1 2 3 4 5 6 7
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
Subşirurile mutate la fiecare operaţie sunt:
$6$
$4 5$
$1 2$
$1 2 3$
...
== include(page="template/taskfooter" task_id="specsort") ==
