== include(page="template/taskheader" task_id="specsort") ==
Poveste şi cerinţă...
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.
h2. Date de intrare
Fişierul de intrare $specsort.in$ ...
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.
h2. Date de ieşire
În fişierul de ieşire $specsort.out$ ...
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.
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 |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 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
|
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") ==
