Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2014-03-06 13:37:21.
Revizia anterioară   Revizia următoare  

 

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. O sortare in zig-zag de ordin k se defineste ca o reanranjare 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 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

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.

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

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

  • N ≤ 100000
  • 1 ≤ K ≤ 4 ≤ N
  • Daca K > 1 atunci N % K = 1 (toate secventele necrescatoare / nedescrescatoare 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 intrate vor fi maxim 10 teste.

Exemplu

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

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?