ECOO '14 R3 P1 - Substitute Teacher

View as PDF

Submit solution

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 1 to 26, the lowercase letters a to z are encoded as the integers 27 to 52, the digit characters 0 to 9 are encoded as the integers 53 to 62 and the space, period, comma and question mark are 63, 64, 65 and 66 respectively.

Then she uses the formula c = \text{rem}(m \cdot k_e, 67) to substitute each character in the original message for a new one. In this formula, m is the character number from the original message, k_e is a secret encryption key (2 \le k_e \le 66) and c is the number for the character in the encrypted message and the \text{rem} function gives the remainder after dividing the first argument by the second. The formula maps every integer from 1 to 66 to a different integer in the same range with no repeats. A similar formula will also work for decrypting: m = \text{rem}(c \cdot k_d, 67) where k_d is a decryption key (2 \le k_d \le 66).

If k_e = 18 then an a character (27) in the original message would become a Q character (17) in the encrypted message, because \text{rem}(27 \cdot 18, 67) = 17. For this example the decryption key is k_d = 41.

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 10 test cases. Each test case consists of 3 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 200 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 10 test cases.

Sample Input

*pIZjugwgZ6HkZx6kZjiZg77GtGgHjUkZ76tjiwZ6ZIgvG9wGvgZI tuZ6IZY,LLYLKln*

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


There are no comments at the moment.