2011年8月1日 星期一

11385 - Da Vinci Code


本題會給你一些費氏數列(Fibonacci series)的前幾項,及一個加密後的密文,請你利用本題提供的方法進行解密。直接以一個例子解釋。每組資料會有兩列,第一列為解密的鑰匙,是由費氏數列的某些項所組成的數個整數,第二列為欲解密的密文。例如:
     13 2 89 377 8 3 233 34 144 21 1
     OH, LAME SAINT!
解密後為:
     THE MONA LISA

費氏數列的特性為可利用前兩項的和來得到第三項,得到數列 1, 2, 3, 5, 8, 13, 21...

解密的原則為先把解密的鑰匙中,每一項的值找出該值在費氏數列中是第幾項,例如13是費氏數列的第六項,2為第二項,89為第十項,以此類推。第一個數值13為費氏數列的第六項,就把第一個大寫字母O搬到位置六的地方,第二個數值2為費氏數列的第二項,就把第二個大寫字母H搬到位置二的地方,以此類推得到THE MONA LISA。請注意只有大寫字母才需要解碼,請忽略其他字元。

在費氏數列中未出現的項,請將其對應的位置上填上空白字元,例如上例中缺少費氏數列的第四、第九項(5, 55),所以在對應的位置上是空白字元。但空白字元只限於出現在字串中。


Input
輸入資料的第一列為整數T,表示測試資料的組數,接下來每組測試資料有三列,第一列為整數N,表示第二列有N個取自於費氏數列的整數,每個整數將以空白字元隔開。第三列為欲解密的字串。

Output
請輸出每組測試資料解密後的字串。注意其僅包含大寫字元。

Constraints
  • 輸入的費氏數列,其值必小於2^32。
  • 輸入字串長度最多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

原文出處

沒有留言:

張貼留言