Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2014-03-06 09:16:42.
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 test1 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-zac de ordin k se defineste in felul urmator:

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 urmat de 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 ordinea din fisierul de iesire 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 intre [1 si N-1], si aplicate in ordine ordoneaza vectorul conform restrictiilor.

Exemplu

zigsort.inzigsort.out
This is some
text written on
multiple lines.
This is another
text written on
multiple lines.

Explicaţie

...

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?