Pracsiu Dan (dnprx) Algoritmul Radix Sort folosit pentru sortarea unui vector format din elemente numere naturale presupune parcurgerea următorilor paşi:
- se sortează elementele vectorului după ultima cifră, iar în caz de egalitate după poziţia iniţială din şir;
- se sortează elementele vectorului după penultima cifră, iar în caz de egalitate după poziţia de la pasul precedent;
- se repetă această operaţie până la cifra cea mai semnificativă (de ordin maxim) din scrierea numerelor din şir.
De exemplu, pentru şirul 525, 417, 381, 291, 455, algoritmul presupune efectuarea următorilor paşi:
- sortăm după ultima cifră şi obţinem:
381, 291, 525, 455, 417; - sortăm după penultima cifră şi obţinem:
417, 525, 455, 381, 291; - sortăm după prima cifră şi obţinem:
291, 381, 417, 455 , 525.
Dacă în şirul iniţial elementele au asociaţi indicii 1, 2, 3, 4, 5, iar după fiecare pas al algoritmului de sortare aceşti indici se scriu în ordinea corespunzătoare elementelor asociate în şirul iniţial, atunci ordinea indicilor după fiecare etapă va fi:
3, 4, 1, 5, 2;2, 1, 5, 3, 4;4, 3, 2, 5, 1.
Observăm că valorile acestor șiruri reprezintă indicii inițiali ai vectorului pe care dorim să îl sortăm. Aceștia formează astfel, la fiecare pas, o permutare a numerelor de la 1 la N.
Asemănător, şirul poate să fie sortat în orice bază de numeraţie B dacă transformăm numerele în baza B şi apoi aplicăm acelaşi procedeu. De exemplu, dacă şirul pe care dorim să îl sortăm este 6, 8, 5 şi dorim să apelăm Radix Sort în baza 2, numerele vor fi transformate în 110 (6), 1000 (8) şi 101 (5). În continuare vom obţine următoarele şiruri pentru fiecare bit:
- sortăm după ultimul bit:
110,1000,101; - sortăm după penultimul bit:
1000,101,110; - sortăm după antepenultimul bit:
1000,101,110; - sortăm după cel mai semnificativ bit:
101,110,1000.
Prin urmare, permutările obţinute sunt, în ordine:
1, 2, 3;2, 3, 1;2, 3, 1;3, 1, 2.
Cerința
Pisica Pia are un şir iniţial de lungime N asupra căruia a apelat algoritmul Radix Sort în baza B. Din păcate, sora ei Mitzu s-a jucat cu şirul Piei şi acesta a fost pierdut, dar Pia în continuare are permutările obţinute la fiecare pas în urma apelării algoritmului. Ajutaţi-o pe Pia să descopere un posibil şir iniţial.
Date de intrare
Pe prima linie a fişierului de intrare xidartros.in se află numărul T, reprezentând numărul de teste din problemă. Prima linie a fiecărui test va conţine 3 numere naturale: N – reprezentând numărul elementelor din şir, B – reprezentând baza folosită în apelarea algoritmului de Radix Sort şi K – reprezentând numărul de paşi ai algoritmului. Următoarele K linii conţin câte N numere naturale reprezentând permutarea indicilor inițiali ai elementelor din şir după fiecare pas al algoritmului.
Date de ieșire
În fişierul de ieşire xidartros.out se vor afişa T linii, linia i conţinând răspunsul pentru cel de al i-lea test. Dacă testul admite soluţie, acesta va conţine N numere naturale reprezentând elementele şirului iniţial (scrise în baza 10), astfel încât, aplicând algoritmul Radix Sort în baza dată în test acestui şir, permutările indicilor elementelor din şir după fiecare pas al algoritmului să fie aceleaşi cu cele date în fişierul de intrare. Dacă testul în schimb nu admite soluţie, pe linia i se va afişa -1.
Restricții și precizări
1 ≤ N, T ≤ 1.000.0002 ≤ B ≤ 1.000.000.0001 ≤ K ≤ 64- Numărul total de elemente citite în input din toate permutarile nu depaseste
1.000.000(suma deN * Kdin fiecare test≤ 1.000.000) - Pentru orice test care admite soluţie, există o soluţie care conţine elemente cuprinse între
0și1018inclusiv. Se admite orice soluție corectă care conține elemente în acest interval.
Exemplu:
xidartros.in
3 5 10 3 3 4 1 5 2 2 1 5 3 4 4 3 2 5 1 3 2 4 1 2 3 2 3 1 2 3 1 3 1 2 3 2 1 3 2 1
xidartros.out
525 417 381 291 455 6 8 5 -1
Explicație
Pentru primele 2 teste, vezi explicaţiile din enunţul problemei. Pentru al treilea test, nu există niciun şir care, sortat cu Radix Sort în baza 2, să fie sortat într-o singură instanţă şi să obţinem permutarea 3, 2, 1.