A Da Vinci-kód

A Da Vinci-kód egyike minden idők legtöbbet olvasott és egyben legvitatottabb könyveinek. Ebben a könyvben az író, Dan Brown egy nagyon érdekes módszert használt egy üzenet titkosításához. Nagyon okosnak kellett lenni a kód visszafejtéséhez, mert nem állt rendelkezésre elegendő információ. Itt egy hasonló feladatot fogsz kapni, de elegendő segítséggel a megoldáshoz.

Ebben a feladatban a Fibonacci-sorozatból származó számok egy sorozata és a titkosított szöveg lesz megadva. A feladatod, hogy visszafejtsd a szöveget az alább ismertetett módszerrel.

Nézzünk meg egy példát! Minden titkosított üzenet két sorból fog állni. Az első a kulcs, amely a Fibonacci-sorozat bizonyos elemeit tartalmazza. A második sor maga a titkosított szöveg.

Tehát ha a titkosított üzenet

13 2 89 377 8 3 233 34 144 21 1
OH, LAME SAINT!

akkor az eredmény

THE MONA LISA

Ennek a feladatnak az erejéig feltételezzük, hogy a Fibonacci-sorozat első eleme az 1, a második a 2, és minden rákövetkező számot az előző kettő összeadásával kapunk meg. Tehát a Fibonacci-sorozat: 1, 2, 3, 5, 8, 13, …

Hogyan is kapjuk meg a „THE MONA LISA” sztringet az „OH, LAME SAINT!”-ből? Az első sor a Fibonacci-sorozatból vett elemeket tartalmaz. Az első a 13, amely a 6. szám a Fibonacci-sorozatban. Tehát a titkosított szövegben szereplő első nagybetű, az „O” az eredmény sztring 6. helyére kerül. A második szám a 2, amely a Fibonacci-sorozat második tagja, ezért a „H” az eredmény sztring második helyére kerül. Utána jön a 89, ami a 10. Fibonacci-szám, tehát az „L”, ami a 3. nagybetű a titkosított szövegben, az eredmény 10. karaktere lesz. Ez a folyamat folytatódik, amíg a titkosított szöveg véget nem ér, és így kapjuk meg a „THE MONA LISA” sztringet. Fontos, hogy csak a nagybetűk hordozzák az üzenetet, a többit egyszerűen figyelmen kívül kell hagyni.

Ha egy Fibonacci-szám hiányzik a megadott sorozatból, akkor a helyére egy szóközt kell tenni az eredmény sztringben. A fenti példában a 4. és a 9. Fibonacci-szám, az 5 és az 55 hiányzik. Tehát szóköz került elhelyezésre az eredmény sztring 4. és 9. pozíciójába. De a sztring végén nem szerepelhet szóköz karakter.

A bemenet specifikációja

A bemenet egy T egész számot tartalmazó sorral kezdődik. Ezután T teszteset következik. Minden teszteset három sorból áll. Az első sor egy N pozitív egész számot tartalmaz. A második sorban N darab szám van a Fibonacci-sorozatból. A számokat szóközök választják el egymástól. Végül a harmadik sor tartalmazza a visszafejtendő titkosított szöveget. A bemeneten előforduló összes Fibonacci-szám kisebb, mint 2³¹. A titkosított szöveg hossza legfeljebb 100 karakter.

A kimenet specifikációja

Minden tesztesetre egyetlen sort kell a kimenetre írni: a visszafejtett szöveget. Ne feledjük, hogy a visszafejtett szöveg csak nagybetűket és szóközöket tartalmaz!

Példa bemenet

1. 2
2. 11
3. 13 2 89 377 8 3 233 34 144 21 1
4. OH, LAME SAINT!
5. 15
6. 34 21 13 144 1597 3 987 610 8 5 89 2 377 2584 1
7. O, DRACONIAN DEVIL!

letöltés szöveges állományként

A példa bemenethez tartozó kimenet

1. THE MONA LISA
2. LEONARDO DA VINCI

letöltés szöveges állományként