Fișierul intrare/ieșire specsort.in, specsort.out Sursă Lot Sovata 2014
Autor Cristian Lambru Adăugată de avatar spatarel Spatarel Dan-Constantin spatarel
Timp de execuție pe test 0.6 sec Limită de memorie 8192 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip full
open book Poți vedea testele pentru această problemă accesând atașamentele .

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

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 1 categorii