| Fişierul intrare/ieşire: | specsort.in, specsort.out | Sursă | Lot Sovata 2014 Seniori Baraj 3 |
| Autor | Andrei Cristian Lambru | Adăugată de |  Marian Darius •dariusdarius |
| Timp execuţie pe test | 0.3 sec | Limită de memorie | 12288 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
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).
Cerinta
Să se sorteze elementele din permutare efectuând un număr cât mai mic de operaţii.
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.
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.
Restricţii
- 1 ≤ N ≤ 50 000
- Atentie! Numarul de operatii nu trebuie neaparat sa fie minim. Exista totusi, problema aceasta care cere numar minim de operatii..
Exemplu
| 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 |
Explicaţie
Subşirurile mutate la fiecare operaţie sunt:
6
4 5
1 2
1 2 3
