Double Trouble
Time limit1sMemory limit128 MB
Given an encrypted ciphertext formed by shifting letters and reversing blocks of size m, find the shift s and block size m that make a given crib appear.
- Level
Medium4 of 10
- Topics
- String, Brute force, Implementation, Simulation
- Solved
- No attempts yet
Problem
Alice and her sister Irene frequently send each other e-mails. Wary of interception and wishing to keep their correspondence private, they encrypt each message in two steps. First they remove every non-alphabetic character and convert all letters to upper case (call the result the modified plaintext); then they:
- replace each letter by the letter positions later in the alphabet () — call this a shift by . The alphabet wraps around, so for example when ,
YbecomesAandZbecomesB. - divide the result of step 1 into groups of letters () and reverse the letters within each group. If the total length is not divisible by , only the last letters () are reversed.
For example, let and . If the plaintext is Meet me in St. Louis, Louis., then after removing non-alphabetic characters and converting to upper case the modified plaintext is:
MEETMEINSTLOUISLOUIS
Shifting each letter by 2 gives the intermediate result:
OGGVOGKPUVNQWKUNQWKU
Finally, reversing every group of 6 letters gives (the last two letters form the final group):
GOVGGOQNVUPKWQNUKWUK
By convention the result is written in groups of 5 letters, so the ciphertext is:
GOVGG OQNVU PKWQN UKWUK
Once a ciphertext is intercepted it is not very hard to recover and , and it is even easier if you know a crib — a word that appears in the modified plaintext. In the example above, LOUIS is a crib. Your task is to find and given a ciphertext and a crib.
Input
The input consists of several problem instances. The first line contains a positive integer giving the number of instances.
Each instance spans several lines. Its first line contains the integer (), equal to the number of characters in the ciphertext. The following lines contain the ciphertext, all upper case, in groups of 5 letters separated by a single space (the last group may contain fewer than 5 letters). There are 10 groups per line, except possibly for the last line of ciphertext. The line following the last line of ciphertext contains the crib: a single word of between 4 and 10 upper-case characters, inclusive.
Output
Output the two integers and on a single line, separated by one space, giving the encryption key that produces the crib, where is the shift and is the reversed-group size. If there is more than one solution, output the one with the smallest ; if several share the smallest , output the one with the smallest . If no such and exist, output Crib is not encrypted.