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 vipIN.txt 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 vipOUT.txt 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ă. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

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

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 caaliisv În al doilea set nici una din anagramele șirului ghita nu poate să difere pe exact două poziții de șirul marko.

Exemplul 2:

vipIN.txt

2 
80000000000 6
corleone 
vasilica 
5 2 
marko 
ghita

vipOUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python3" line="1"> def citeste_intrare(nume_fisier):

   with open(nume_fisier, 'r') as f:
       t = int(f.readline().strip())
       cazuri = []
       for _ in range(t):
           n, k = map(int, f.readline().strip().split())
           s1 = f.readline().strip()
           s2 = f.readline().strip()
           cazuri.append((n, k, s1, s2))
   return cazuri

def verifica_invariant(freq1, freq2, egali, diferiti, sigma=26):

   nevoie_extra_op = 0
   max_extra = 0
   for i in range(1, sigma + 1):
       extra_car = freq1[i] + freq2[i] - diferiti
       extra_op = (extra_car + 1) // 2
       if extra_op > min(freq1[i], freq2[i]):
           return False
       max_extra += min(freq1[i], freq2[i])
       if extra_op > 0:
           nevoie_extra_op += extra_op
   return nevoie_extra_op <= egali and egali <= max_extra

def rezolva_caz(n, k, s1, s2):

   freq1 = [0] * 27
   freq2 = [0] * 27
   answer = [] * (n + 1)

   for char in s1:
       freq1[ord(char) - ord('a') + 1] += 1
   for char in s2:
       freq2[ord(char) - ord('a') + 1] += 1

   egali = n - k
   diferiti = k

   if not verifica_invariant(freq1, freq2, egali, diferiti):
       return "-1"

   for i in range(1, n + 1):
       freq1[ord(s1[i-1]) - ord('a') + 1] -= 1
       for j in range(1, 27):
           if freq2[j] == 0:
               continue
           freq2[j] -= 1
           if ord(s1[i-1]) - ord('a') + 1 == j:
               egali -= 1
           else:
               diferiti -= 1

           if verifica_invariant(freq1, freq2, egali, diferiti):
               answer[i] = chr(j + ord('a') - 1)
               break

           if ord(s1[i-1]) - ord('a') + 1 == j:
               egali += 1
           else:
               diferiti += 1

           freq2[j] += 1

   return .join(answer[1:])

def scrie_iesire(nume_fisier, rezultate):

   with open(nume_fisier, 'w') as f:
       for rez in rezultate:
           f.write(f"{rez}\n")

def verifica_restricții(cazuri, nume_fisier_iesire):

   suma_n = sum(caz[0] for caz in cazuri)  # Suma tuturor valorilor lui N
   if not all(1 <= caz[0] <= 100000 and 1 <= caz[1] <= 100000 for caz in cazuri) or suma_n > 1000000:
       with open(nume_fisier_iesire, 'w') as f:
           f.write("Datele nu corespund restrictiilor impuse\n")
       return False
   return True

def main():

   cazuri = citeste_intrare("vipIN.txt")
   if not verifica_restricții(cazuri, "vipOUT.txt"):
       return  # Oprește execuția dacă datele nu corespund restricțiilor
   
   rezultate = []
   for caz in cazuri:
       rezultate.append(rezolva_caz(*caz))
   scrie_iesire("vipOUT.txt", rezultate)

if __name__ == "__main__":

   main()

</syntaxhighlight>