zigsort

Zigsort

== include(page="template/taskheader" task_id="zigsort") ==

Fie un vector de numere naturale *A[]* ce contine *N* elemente. O sortare in zig-zac de ordin *k* se defineste in felul urmator:

Fie un vector de numere naturale *A[]* ce contine *N* elemente *cu valori distincte*. O sortare in zig-zag de ordin *k* se defineste ca o rearanjare a elementelor astfel incat :

a{~1~} ≥ a{~2~} ≥ ... ≥ a{~k~} ≥ a{~k+1~}

a{~1~} > a{~2~} > ... > a{~k~} > a{~k+1~}

a{~k+1~} ≤ a{~k+2~} ≤ ... ≤ a{~2*k+1~}

a{~k+1~} < a{~k+2~} < ... < a{~2*k+1~}

a{~2*k+1~} ≥ a{~2*k+2~} ≥ ... ≥ a{~3*k+1~}

a{~2*k+1~} > a{~2*k+2~} > ... > a{~3*k+1~}

si asa mai departe, adica :

primele _*k*_ elemente trebuie sa fie in ordine necrescatoare
elementele de la pozitiile _*k + 1*_ pana la _*2 * k + 1*_ trebuie sa fie in ordine nedescrescatoare
elementele de la pozitiile _*2 * k + 1*_ pana la _*3 * k + 1*_ trebuie sa fie in ordine necrescatoare

primele _*k + 1*_ elemente trebuie sa fie in ordine descrescatoare
elementele de la pozitiile _*k + 1*_ pana la _*2 * k + 1*_ trebuie sa fie in ordine crescatoare
elementele de la pozitiile _*2 * k + 1*_ pana la _*3 * k + 1*_ trebuie sa fie in ordine descrescatoare

In general elementele de la pozitiile _*p * k + 1*_ pana la _*(p + 1) * k + 1*_ trebuie sa fie in ordine necrescatoare daca _*p*_ este par si nedescrescatoare daca _*p*_ este impar.

In general elementele de la pozitiile _*p * k + 1*_ pana la _*(p + 1) * k + 1*_ trebuie sa fie in ordine descrescatoare daca _*p*_ este par si crescatoare daca _*p*_ este impar.

Pentru a rezolva problema trebuie sa implementati o astfel de sortare dar care sa foloseasca interschibari doar de elemente care sunt pe pozitii consecutive (swap *A[i]* si *A[i+1]*).

Pentru a rezolva problema trebuie sa implementati o astfel de sortare dar care sa foloseasca interschimbari doar de elemente care sunt pe pozitii consecutive (swap *A[i]* si *A[i+1]*).

h2. Date de intrare

Fişierul de intrare $zigsort.in$ contine pe prima linie un numar natural *T* reprezentand numarul de teste urmat de descrierile fiecarui test:

Fişierul de intrare $zigsort.in$ contine pe prima linie un numar natural *T* reprezentand numarul de teste apoi urmeaza descrierile fiecarui test:

Pe prima linie numerele *N* si *K* separate printr-un spatiu.
Pe urmatoarea linie *N* numere naturale, valorile initiale ale vectorului *A[]*.
h2. Date de ieşire

În fişierul de ieşire $zigsort.out$ afisati pentru fiecare test, pe cate o linie, interschimarile de tipul celor descrise care sorteaza vectorul *A[]* transformandu-l intr-un vector zigsortat de ordin *K*.

În fişierul de ieşire $zigsort.out$ afisati pentru fiecare test, pe cate o linie, interschimarile de tipul celor descrise care sorteaza vectorul *A[]* transformandu-l intr-un vector zigsortat de ordin *K*:

Primul numar M reprezinta numarul de interschimbari necesare iar urmatoarele M numere reprezinta indici *i* pentru care se apeleaza *swap(A[i], A[i+1])*, in ordinea din fisierul de iesire astfel incat la final sa avem rezultatul dorit.

Primul numar *M* reprezinta numarul de interschimbari necesare iar urmatoarele *M* numere reprezinta indici *i* pentru care se apeleaza *swap(A[i], A[i+1])*, in aceasta ordine astfel incat la final sa avem rezultatul dorit.

h2. Restricţii

* N ≤ 100000

* 1≤ N ≤ 100000

* 1 ≤ K ≤ 4 ≤ N

* Daca K > 1 atunci N % K = 1 (toate secventele necrescatoare / nedescrescatoare au lungime K).

* 1 ≤ A[i] ≤ 100000 pentru orice i
* Daca K > 1 atunci N % K = 1 (toate secventele monotone au lungime K).

* Programul va fi punctat doar daca pentru orice test, M ≤ 375000 iar interschimbarile sunt valide (pozitiile *i* sunt intre [1 si N-1], si aplicate in ordine ordoneaza vectorul conform restrictiilor.

* Programul va fi punctat doar daca pentru orice test *M* *≤* *375000* iar interschimbarile sunt valide (pozitiile *i* sunt din intervalul *[1, N-1]*, si aplicate in ordinea in care au fost afisate sorteaza vectorul conform restrictiilor).
* In fisierul de intrare vor fi maxim 20 teste.

h2. Exemplu
table(example). |_. zigsort.in |_. zigsort.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 2
  4 1
  5 6 3 1
  7 3
  6 7 5 3 2 1 9
| 2 1 2
  4 1 4 5 4

|

h3. Explicaţie

h3. Explicatie

...

Pentru primul test reprezentam interschimbarile:
 
1 2 3 4
5 6 3 1 -> A[] initial, la final trebuie ca @A[1]@ > @A[2]@ < @A[3]@ > @A[4]@
        aplicam swap(1,2) =>
6 5 3 1
        aplicam swap(2,3) =>
6 3 5 1
 
care respecta 6 > 3 < 5 > 1.
 
Au fost necesare 2 interschimbari, pozitia *1* cu 2 si apoi *2* cu 3.

== include(page="template/taskfooter" task_id="zigsort") ==

9721