|
I I U C O N L I N E C O N T E S T 2 0 0 8 |
|
|
Problem A: Da Vinci Code |
|
|
Input: standard input |
|
|
|
|
|
13-3-2-21-1-1-8-5 O, DRACONIAN DEVIL! OH, LAME SAINT!
The Da Vinci Code is one of the most widely read but controversial books of all time. In this book the writer Dan Brown used a very interesting encryption technique to keep a secret message. It required a great deal of intelligence to decipher the code since there was not enough information available. Here, a similar kind of problem is given with sufficient clues to solve.
In this problem, you will be given a series of numbers, taken from Fibonacci series and a cipher text. Your task is to decipher the text using the decryption technique described below.
Let’s follow an example. Any cipher text will consist of two lines. First line is the key which contains some numbers drawn from Fibonacci series. The second line is the actual cipher text.
So, given the following cipher text 13 2 89 377 8 3 233 34 144 21 1 OH, LAME SAINT! the output will be: THE MONA LISA
For this problem, assume that the first number in Fibonacci series is 1, second one is 2 and each subsequent number is found by adding previous two numbers of the series. So, the Fibonacci series is 1, 2, 3, 5, 8, 13... ...
So, how do we get the string “THE MONA LISA” from the string “OH, LAME SAINT!”? Here some numbers are drawn from Fibonacci series, given in the first line. The first one is 13 which is the sixth (6th) Fibonacci number in Fibonacci series. So the first uppercase letter in the cipher text ‘O’ goes to the sixth (6th) position in the output string. Second number in the input string is 2 which is the second Fibonacci number and thus ‘H’ goes to second position in the output string; then comes 89 which is the 10th Fibonacci number, so ‘L’ which is the third uppercase letter in the cipher goes to the 10th position in the output string. And this process continues until the cipher text ends and hence we find the string “THE MONA LISA”. Note that only uppercase letters conveys the message; other characters are simply garbage.
If a Fibonacci number is missing in the input sequence then a blank space is put at its position in the output string. As in the above example fourth and ninth Fibonacci numbers 5 and 55 are missing. So, two blank spaces are inserted in fourth and ninth positions of the output string. But there must not be any trailing spaces.
|
|
|
Input |
|
|
Input starts with a line consisting of a single number T. T test cases follow. Each test case consists of three lines. The first line contains a single positive integer N. In the second line there are N numbers drawn from the Fibonacci series. The numbers will be separated from each other using spaces. Finally, the third line contains the cipher text to be decrypted.
|
|
|
Output |
|
|
For each test case, output contains a single line containing the decrypted text. Remember that the decrypted text will contain only uppercase letters.
|
|
|
Constraints |
|
|
- Value of any input Fibonacci number is less than 231. - The length of the cipher text will be at most 100.
|
|
|
Sample Input |
Output for Sample Input |
|
2 11 13 2 89 377 8 3 233 34 144 21 1 OH, LAME SAINT! 15 34 21 13 144 1597 3 987 610 8 5 89 2 377 2584 1 O, DRACONIAN DEVIL! |
THE MONA LISA LEONARDO DA VINCI |
|
|
|
|
Problem setter: Mohammed Shamsul Alam Special thanks: Mohammed Saifur Rahim, Tanveer Ahsan |
|