ECOO '18 R3 P2 - Vegenère

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 13.0s
Memory limit: 256M

Problem types

The Vegenère cipher is a famous cipher which uses a keyboard to shift the value of each character of the message by some amount. For example, if the message is HELLOWORLD, and the keyword is CODE, then the Vegenère cipher first repeats the keyword until it's the same length as the message, then encrypts the message by "adding" the two strings together:

  HELLOWORLD
+ CODECODECO
= KTPQRLSWOS

To add the strings together, we "shift" each character in the message by the character in the keyword. For example, shifting Y by A returns Z, shifting by B returns A, shifting by C returns B, and so on. Note that the shift wraps around the alphabet, i.e. A is after Z.

Alice and Bob have been spreading rumours behind Eve's back. They do not want Eve to find out, so they have encrypted their messages using the Vegenère cipher. However, they have made a fatal flaw by choosing an English word as their keyword and only sending messages consisting of English words. Can you help Eve decipher what they are saying?

Input Specification

The standard input contains 10 datasets. Each dataset begins with an integer N (1 \le N \le 10^5), the number of words in the English dictionary that Alice and Bob are using. N lines follow, each containing a word in the English language. The total size of the dictionary will be at most 10^6 characters.

The next line contains the encrypted message, which will be at most 10^5 characters in length.

All strings in the input will consist of upper-case English characters.

For 30% of the cases, N \le 10 and the encrypted string contains at most two words.

For 60% of the cases, N \le 100.

Output Specification

For each dataset, output the first ten characters of the decrypted message and the sum of the squared lengths of the words in the message. If there are multiple solutions, output the one that comes first alphabetically. If there are multiple interpretations of a message, output the one that minimizes the sum of squared lengths of the words in the message.

Sample Input (Two Datasets Shown)

3
CODE
HELLO
WORLD
KTPQRLSWOS
5
EVE
IS
VERY
COOL
SILLY
HKTUVKTDBHXXON

Sample Output

HELLOWORLD 50
EVEISVERYS 54

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


Comments

There are no comments at the moment.