Revizia anterioară Revizia următoare
Fişierul intrare/ieşire: | zigsort.in, zigsort.out | Sursă | ONIS 2014, Runda 3 |
Autor | Paul Diac, Stefan Ciobaca | Adăugată de | |
Timp execuţie pe test | 0.5 sec | Limită de memorie | 20480 kbytes |
Scorul tău | N/A | Dificultate | N/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
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.in | zigsort.out |
---|---|
This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...