== 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. Cerință
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 de intrare $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 de ieșire $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$
* Ultima linie din fișier trebuie să conțină permutarea sortată.
* 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") ==
