4169 - Switch Letters

Enunt

Se dă un șir s = s0, s1,…, sn-1 de n litere mici. Prin s[i..j] se înțelege secvența si, si+1, …, sj. Asupra șirului se efectuează de mai multe ori operația switch(i,j,c1,c2), care în secvența s[i..j] modifică orice apariție a literei c1 în litera c2. De exemplu, dacă s=abcdaabcdaaab, atunci switch(0,5,'a','z') face ca șirul să devină s=zbcdzzbcdaaab.

Cerinţa

Dându-se șirul s și m operații switch, să se afișeze șirul s după efectuarea celor m operații.

Date de intrare

Fișierul de intrare switchletters.in conține pe prima linie șirul s, pe a doua linie numărul natural m, iar pe următoarele m linii se află câte două numere naturale și două litere mici ale alfabetului englez, separate prin câte un spațiu i j c1 c2, reprezentând operația switch(i,j,c1,c2).

Date de ieșire

Fișierul de ieșire switchletters.out va conține șirul s după efectuarea celor m operații.

Restricţii şi precizări

• Șirul s conține cel mult 1.000.000 litere mici: 1 ≤ n ≤ 1.000.000.
• Șirul s nu conține alte caractere în afară de litere mici.
• Într-o operație switch(i,j,c1,c2), întotdeauna 0 ≤ i ≤ j < n, iar c1 ≠ c2.
• 1 ≤ m ≤ 217.

Exemplul 1

switchletters.in

aaaabbbbcccc
3
0 2 a y
5 9 b c
1 3 a z

switchletters.out

yyyzbccccccc

Explicație

Pentru primul exemplu, După operația switch(0,2,’a’,’y’), s=yyyabbbbcccc. După operația switch(5,9,’b’,’c’), s=yyyabccccccc. După operația switch(1,3,’a’,’z’), s=yyyzbccccccc

Exemplul 2

switchletters.in

anaaremere
2
3 6 z y
2 7 o x

switchletters.out

anaaremere

Explicație

s rămâne neschimbat, deoarece literele z și o nu apar în șir.

Rezolvare

<syntaxhighlight lang="python" line> def switch_letters(s, operations):

   for op in operations:
       i, j, c1, c2 = op
       for k in range(i, j+1):
           if s[k] == c1:
               s[k] = c2

def main():

   # Citirea datelor de intrare
   s = list(input().strip())
   m = int(input().strip())
   operations = [list(input().split()) for _ in range(m)]

   # Conversia indicele și literelor la valorile numerice corespunzătoare
   for i in range(m):
       operations[i][0] = int(operations[i][0])
       operations[i][1] = int(operations[i][1])

   # Aplicarea operațiilor switch
   switch_letters(s, operations)

   # Afisarea rezultatului
   print("".join(s))

if __name__ == "__main__":

   main()

</syntaxhighlight>