Problem F
Over the Hill, Part 2

Bob Roberts is part of a crack espionage team working for the CIA (Chocolate Institute of Alabama) and he is working on decrypting the encoded messages of their arch rivals at the NSA (Nougat Society of Arkansas). Fortunately, the NSA’s espionage staff is not nearly as crack as Bob’s as they are using the Hill encryption scheme (described in the previous problem) which is susceptible to a known-plaintext attack. Bob has intercepted a plaintext/ciphertext pair and has knowledge of the size of the encryption matrix used by his not-so-sweet enemies. Given these Bob knows that there is a way to determine the encryption matrix, but no one on his staff is exactly sure how (hmmm $\ldots $ not quite as crack as they thought). Bob’s come to you to solve this problem for them. One complication is that there might not be enough data to uniquely determine the NSA’s encryption matrix, and the data they intercepted might have been corrupted leading to no solution to the problem.


Input begins with a line containing a positive integer $n \leq 10$ indicating the size of the matrix and the vectors to use in the encryption. After this are two lines: the first of these contains the plaintext and the second the ciphertext. Both of these lines will consist of $1$ to $2\, 000$ characters in the set A, $\ldots $, Z,0, $\ldots $, 9 and the space character. The lengths of both strings are identical and are multiples of $n$. Both of these strings may include trailing blanks.


Output one of three possible answers. If the input does not admit any possible encryption matrix output No solution. Otherwise if the input does not uniquely determine the encryption matrix output Too many solutions. Otherwise output the encryption matrix, one row per line with a single space between values on a line.

Sample Input 1 Sample Output 1
30 1 9
4 23 7
5 9 13
Sample Input 2 Sample Output 2
Too many solutions
Sample Input 3 Sample Output 3
No solution

Please log in to submit a solution to this problem

Log in