3058 - vip

Cerința

Două personaje ale căror nume se vor da în datele de intrare (momentan îi numim Bossanip și 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 trei linii astfel: pe prima linie a unui set se află scrise două numere naturale 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 și precizări

• 1 ≤ N, K ≤ 100.000
• Suma valorilor lui N din cadrul seturilor de test este mai mică sau egală cu 1.000.000
• 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 un alt șir q1, q2, …, qN, dacă există o poziție i , 1 ≤ i ≤ N, astfel încât pi < qi ș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

Exemplul 1

vipin.txt

2

8 6

corleone

vasilica

5 2

marko

ghita

vipout.txt

Datele introduse corespund restrictiilor impuse.

caaliisv

-1

Exemplul 2

vipin.txt

-9

ioana

ana

vipout.txt

Datele de intrare nu corespund restrictiilor impue.

Rezolvare

<syntaxhighlight lang="python3" line="1"> from itertools import permutations

def numar_diferente(str1, str2):

   return sum(c1 != c2 for c1, c2 in zip(str1, str2))

def anagrame_minim_lexicografice(dicsi, bossanip, K):

   anagrame = [.join(p) for p in permutations(dicsi)]
   anagrame.sort()

   for anagrama in anagrame:
       if numar_diferente(anagrama, bossanip) == K:
           return anagrama

   return "IMPOSIBIL"

def main():

   dicsi = input("Introduceți numele lui Dicsi: ")
   bossanip = input("Introduceți numele lui Bossanip: ")
   K = int(input("Introduceți numărul K: "))

   rezultat = anagrame_minim_lexicografice(dicsi, bossanip, K)
   print(f"Noul nume pentru Dicsi: {rezultat}")

if __name__ == "__main__":

   main()

</syntaxhighlight>