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 , the number of words in the English dictionary that Alice and Bob are using. lines follow, each containing a word in the English language. The total size of the dictionary will be at most characters.
The next line contains the encrypted message, which will be at most characters in length.
All strings in the input will consist of upper-case English characters.
For 30% of the cases, and the encrypted string contains at most two words.
For 60% of the cases, .
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