Fişierul intrare/ieşire:vip.in, vip.outSursăONI 2019, clasa a 10-a, ziua 2
AutorEugenie Daniel PosdarascuAdăugată deTincaMateiTinca Matei TincaMatei
Timp execuţie pe test1.5 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Vip

Două personaje ale căror nume se vor da în datele de intrare (momentan îi numim Bossanip si Dicsi) îşi petrec nopţile prin discoteci. Toată lumea ştie că Bossanip este membru V.I.P. în toate discotecile din lume şi Dicsi profită mereu de celebritatea prietenului său. Ajuns pe meleaguri străine, Dicsi s-a confruntat cu o problemă foarte mare. Cum intră la V.I.P. când este pe cont propriu? Astfel, Dicsi s-a apucat de infracţiuni precum furtul de identitate. Dicsi doreşte să permute literele din numele lui (să găsească o anagramă a propriului nume) astfel încât noul nume să difere prin exact K poziţii de numele lui Bossanip. Mai mult, doreşte ca această anagramă să fie minimă lexicografic. Dacă reuşeşte, este posibil să se dea drept Bossanip şi să intre şi el ca membru V.I.P.

Date de intrare

În fişierul text vip.in pe prima linie se află numărul natural T. Pe următoarele 3 * T linii sunt descrise T seturi de date de intrare, fiecare set ocupă câte 3 linii astfel: pe prima linie a unui set se află scrise două numere N (lungimea numelor reale ale lui Bossanip şi Dicsi) şi K; pe a doua linie a unui set este scris numele lui Bossanip dat printr-un şir de caractere s1; pe a treia linie a unui set este scris numele lui Dicsi dat printr-un şir de caractere s2. Din fericire pentru Dicsi, cele două personaje au nume de aceeaşi lungime.

Date de ieşire

În fişierul text vip.out se vor scrie, pe fiecare din cele T linii câte un şir de caractere, pe a j-a linie este scrisă anagrama corespunzătoare testului j (noul nume al lui Dicsi) sau -1 dacă nu există o astfel de anagramă.

Restricţii

  • 1 ≤ N, K ≤ 105
  • Suma valorilor lui N din cadrul seturilor de test ≤ 106
  • Toate literele sunt litere mici ale alfabetului englez
  • Dacă nu există soluţie pentru un test, atunci se va afişa valoarea -1
  • Un şir p1, p2, ..., pN este mai mic lexicografic decât alt şir q1, q2, ..., qN, dacă există o poziţie i, 1 ≤ i ≤ N, astfel încât pi < pi şi pj = qj, pentru orice j, 1 ≤ j < i
  • Pentru 25% din punctaj se poate afişa orice soluţie corectă care nu este neapărat minimă lexicografic

Exemplu

vip.invip.out
2
8 6
corleone
vasilica
5 2
marko
ghita
caaliisv
-1

Explicaţie

În primul set cea mai mică anagramă a şirului vasilica, din punct de vedere lexicografic, care diferă de şirul corleone pe exact 6 poziţii, este caliisv.

În al doilea set nici una din anagramele şirului ghita nu poate să difere pe exact două poziţii de şirul marko.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?