Fişierul intrare/ieşire:specsort.in, specsort.outSursăLot Sovata 2014 Seniori Baraj 3
AutorAndrei Cristian LambruAdăugată dedariusdariusMarian Darius dariusdarius
Timp execuţie pe test0.6 secLimită de memorie12288 kbytes
Scorul tăuN/ADificultateN/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.inspecsort.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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?