| Fişierul intrare/ieşire: | talharie.in, talharie.out | Sursă | preONI 2008, Runda finala |
| Autor | Andrei Grigorean | Adăugată de |  Andrei Grigorean •wefgef |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Talharie
Deoarece sunt atatea concerte in aceasta vara, Miruna are nevoie de bani pentru a-si cumpara bilete. Ce alta idee mai buna ar fi putut sa-i vina fetitei decat sa jefuiasca o banca? Zis si facut, iat-o in fata seifului. Dupa ca l-a amenintat cu pistolul la tampla pe directorul bancii, Miruna a reusit sa obtina codul special al seifului. Acesta este un sir cu N caractere ce sunt litere mici ale alfabetului. Lucrurile nu sunt insa atat de simple pe cat par, deoarece pentru a patrunde in camera cu bani codul trebuie descifrat. Miruna stie ca trebuie sa roteasca sirul de caractere cu exact K pozitii spre stanga, iar apoi sa repete acelasi procedeu pana ajunge din nou la sirul initial.
Pentru un sir de N caractere si un numar K, aflati cel mai mic sir din punct de vedere lexicografic pe care il putem obtine din sirul initial operand de mai multe ori rotatii circulare spre stanga cu cate K pozitii.
Date de intrare
Fisierul de intrare talharie.in contine pe prima linie un numar natural T, reprezentand numarul de teste. Urmatoarele T linii vor contine cate doua numere naturale N si K, avand semnficatia din enunt, urmate de un sir de N litere mici ale alfabetului.
Date de iesire
Fisierul talharie.out va contine T linii, pe fiecare linie gasindu-se un sir de caractere reprezentand cel mai mic sir din punct de vedere lexicografic care se poate obtine pentru fiecare test.
Restrictii
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 100000
- 0 ≤ K ≤ N
- Un sir (x1,x2...xN) este mai mic din punct de vedere lexicografic decat un alt sir (y1,y2...yM) daca exista o pozitie p astfel incat xp < yp si x1 = y1, x2 = y2 ... xp-1 = yp-1.
Exemplu
| talharie.in | talharie.out |
|---|---|
| 2 4 0 abcd 4 2 bbaa | abcd aabb |
Explicatie
Pentru primul test, singurul sir care poate fi obtinut este abcd. Pentru al doilea test putem obtine bbaa sau aabb.
