## ECOO '14 R3 P1 - Substitute Teacher

View as PDF

Points: 5 (partial)
Time limit: 2.0s
Memory limit: 64M

Problem type

Your math teacher has created an encrypted message using a substitution cipher. The first person to crack the encryption and find the original message gets to leave class early.

pIZjugwgZ6HkZx6kZjiZg77GtGgHjUkZ76tjiwZ6ZIgvG9wGvgZI tuZ6IZY,LLYLKln

She explained her encryption scheme as follows. First she converts every character in the original message to an integer. The capital letters A to Z are encoded as the integers to , the lowercase letters a to z are encoded as the integers to , the digit characters 0 to 9 are encoded as the integers to and the space, period, comma and question mark are and respectively.

Then she uses the formula to substitute each character in the original message for a new one. In this formula, is the character number from the original message, is a secret encryption key and is the number for the character in the encrypted message and the function gives the remainder after dividing the first argument by the second. The formula maps every integer from to to a different integer in the same range with no repeats. A similar formula will also work for decrypting: where is a decryption key .

If then an a character in the original message would become a Q character in the encrypted message, because . For this example the decryption key is .

You just found a scrap of paper on the floor where the teacher encrypted her name. So you now know that B6Hg is the encrypted word Jane. Can you use this information to decrypt the longer message?

The input will contain test cases. Each test case consists of lines.

The first two lines are a short sample message (unencrypted version, then encrypted version) and the third is the message you have to decrypt using the same method that works for the sample. All three strings will start and end with an asterisk character which is not part of the message. The maximum string length is characters, including asterisks. Your job is to use the sample to decrypt the longer message and then print it out between asterisks.

Note that there are only two test cases below, but the real data sets will contain test cases.

#### Sample Input

*Jane*
*B6Hg*
*pIZjugwgZ6HkZx6kZjiZg77GtGgHjUkZ76tjiwZ6ZIgvG9wGvgZI tuZ6IZY,LLYLKln*
*135*
*29B*
*,40Va0aT.H0az8a0Y08Fl0Y0kpuk1g08ll0aq0fdddd*

#### Sample Output

*Is there any way to efficiently factor a semiprime such as 54775723?*
*Is it true that 2 and 2 ALWAYS add to 4????*

Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org