Fişierul intrare/ieşire:zigsort.in, zigsort.outSursăONIS 2014, Runda 3
AutorPaul Diac, Stefan CiobacaAdăugată defmins123FMI No Stress fmins123
Timp execuţie pe test0.5 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Zigsort

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 :

a1 > a2 > ... > ak > ak+1

ak+1 < ak+2 < ... < a2*k+1

a2*k+1 > a2*k+2 > ... > a3*k+1

si asa mai departe, adica :
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 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 interschimbari doar de elemente care sunt pe pozitii consecutive (swap A[i] si A[i+1]).

Date de intrare

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

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:

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.

Restricţii

  • 1≤ N ≤ 100000
  • 1 ≤ K ≤ 4 ≤ N
  • 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 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.

Exemplu

zigsort.inzigsort.out
2
4 1
5 6 3 1
7 3
6 7 5 3 2 1 9
2 1 2
4 1 4 5 4

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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content