Puzzle Out
Time Limit : 20000/10000ms (Java/Other) Memory Limit : 65536/32768K (Java/Other)
Total Submission(s) : 0 Accepted Submission(s) : 0
A recipient of a problem draft has lost the encryption table, but he has a dictionary which includes all the possible words appearing in the problems. You are to help him set up a decryption table to enable him restore the original problem draft from the encrypted one. Given a dictionary of the original words used in the text, and the encrypted text, we want to find the right encryption table such that after decrypting the given encrypted text back to the original one, all words can be found in the dictionary.
Input
The first part of the input is a dictionary of English words common to all test
cases. The first line of the file is d (1 <= d <= 50000); the number of words
in the dictionary, followed by d lines each containing a word in the dictionary.
The words in the dictionary are sorted in alphabetical order and all are in
uppercase. Each word has at most 20 characters, but you can assume that sum
of the length of all words in the dictionary is no more than 350,000. The next
line contains a single integer t (1 <= t <= 10), the number of test cases, followed
by the input data for each test case. Each test case, which is preceded by a
single blank line, consists of multiple lines in the input file forming the
encrypted text. Each line has a string containing only uppercase letters and
blank. You may assume that no line break is occurred in the middle of a word
and there may be arbitrary number of blank characters at the end of each line.
Maximum length of input lines is 80.
Output
The output contains exactly t lines, each corresponding to a test case. Each
line should contain a single string of 26 characters which is the encryption
of the string ABCDEFGHIJKLMNOPQRSTUVWXYZ according to the encryption table used
in the test case. Letters in the output string should be in uppercase. It is
possible that some letters do not appear in the encrypted text at all. In this
case, put a * mark in place of those letters not appearing in the decrypted
version of the input text. If the test case has no solution, the output line
should contain #No solution#. If there is more than one possible encryption
table for a test case, the output line should contain #More than one solution#.
Sample Input
14
BE
CHANGE
FIRST
IN
IS
MUST
SAMPLE
SEE
THE
THIS
TO
WISH
WORLD
YOU
4
GSRH RH GSV URIHG HZNKOV
IZM BMVU SP UGP
RGTANP IZM KFVG UZ VPP
FA UGP KZWCQ
XYZ ABCDEFG
XZY ABD
Sample Output
Z***VU*SR**ON**K*IHG******
TSRQP*NGF**CBAZ**WVUM*K*I*
#No solution#
#More than one solution#