Avui el vostre professor de Programació no ha pogut venir. Com sempre, ha deixat exercicis per fer, però —com que es poden fer a casa— decidiu demanar a la Carme Torras, que avui li toca guardia, si podeu sortir abans.

El problema és que la Carme resulta ser una apassionada dels xifrats i amb un somriure enigmàtic, escriu a la pissarra:

tQ9SAXF9fQ2cQ290QS9Q90QFQM

Aquest, diu, és un missatge secret. Qui aconsegueixi desxifrar-lo abans del final de classe… pot marxar! Naturalment, tothom obre IntelliJ o VS Code de seguida.

La Carme explica que ha fet servir un xifrat per substitució matemàtica molt senzill — segons ella, “massa senzill per a una ment brillant com la vostra”.

Primer, converteix cada caràcter del missatge original en un nombre enter segons aquesta taula:

Després aplica la fórmula d’encriptació: c = rem ( m ⋅ Ke, 67 ) on:

• m és el número del caràcter original,

• Ke és la clau d’encriptació secreta (un nombre entre 2 i 66),

• c és el número del caràcter xifrat,

• i rem(x,67) és el residu de dividir x per 67.

Per desxifrar, utilitza una clau Kd tal que: m = rem ( c ⋅ Kd , 67 )

Per exemple, si Ke = 18, aleshores el caràcter a (que val 27) es converteix en la Q (que val 17), perquè rem ( 27 ⋅ 18 , 67 ) = 17. En aquest cas, la clau de desxifrat seria Kd = 41

La carme, que en el fons també vol que la deixeu tranquila i marxeu cap a casa, deixa caure dissimuladament un paper a terra amb la paraula Carme i a sota 1Q2fV

Perfecte! Ara ja saps com una paraula es transforma en la seva versió xifrada. Amb això pots deduir la clau i desxifrar el missatge llarg de la pissarra.

Entrada

Cada cas de prova consta de 3 línies.

Les dues primeres línies són un missatge de mostra curt (versió sense xifrar, després versió xifrada) i la tercera és el missatge que heu de desxifrar utilitzant el mateix mètode que funciona per a la mostra.

Les tres cadenes començaran i acabaran amb un asterisc que no forma part del missatge. La longitud màxima de la cadena és de 200 caràcters, inclosos els asteriscs.

Sortida

Per cada cas has de desxifrar el missatge i mostrar-lo entre asteriscs.

Exemple d'Entrada

*Carme*
*1Q2fV*
*tQ9SAXF9fQ2cQ290QS9Q90QFQM*
*135*
*29B*
*,40Va0aT.H0az8a0Y08Fl0Y0kpuk1g08ll0aq0fdddd*

Exemple de Sortida

*Ja pots marxar cap a casa.*
*Is it true that 2 and 2 ALWAYS add to 4????*