Fişierul intrare/ieşire:specsort.in, specsort.outSursăLot Sovata 2014
AutorCristian LambruAdăugată despatarelSpatarel Dan-Constantin spatarel
Timp execuţie pe test0.6 secLimită de memorie8192 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Specsort (lot liceu)

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).

Cerinţă

Să se sorteze elementele din permutare efectuând un număr cât mai mic de operaţii.

Date de intrare

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.

Date de ieşire

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.

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 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