Laiko ribojimas: 1s
Atminties ribojimas: 32MB
Duomenų failas: kvkripto.in
Rezultatų failas: kvkripto.out
Kvadratinis kodas
Linas ir Martynas yra labai gerai draugai. Būdami gerais draugais, jie dažnai susirašinėja laiškais. Siekdami, kad jų pokalbio niekas nenugirstų, jie sumanė visus laiškus užkoduoti. Laiško dekodavimas vyksta labai paprastu būdu:
- Iš matematikos sąsiuvinio iškerpamas kvadratas , turintis mažesnių kvadratėlių (tokį patį kvadratą turi ir kodavęs žmogus);
- Šiame kvadrate iškerpamos skylutės;
- Šis kvadratas padedamas ant užkoduotos žinutės;
- Per skylutes matomos raidės užrašomos prie dekoduoto teksto (skylučių turinys skaitomas nuo viršau į apačią iš kairės į dešinę);
- Kvadratas pasukamas laipsniu kampu pagal laikrodžio rodyklę;
- Skaitymo procesas kartojamas dar kartus;
- Iš galutinio rezultato pašalinami visi pertekliniai tarpai.
Tad, pavyzdžiui, jeigu užkoduotas tekstas atrodo taip (taškais žymimi tarpai):
o.do
.ng.
grmn
o.i.
O iškirptasis kvadratas yra (* žymi skylutes):
.*..
*.*.
....
*...
Taip priklausomai nuo pradinės kvadrato padėties galima dekoduoti keturis skirtingus tekstus:
- od morning go
- orning good m
- ng good morni
- good morning
Iš šių tekstų dekoduotojas išsirenka tą, kuris yra labiausiai panašus į įskaitoma tekstą, t.y. "good morning". Įskaitomu tekstu laikomas tas, kurio visi žodžiai yra žinomi Linui ir Martynui. Esant keliems geriems tekstams, iš jų geriausiu išrenkamas tas, kuris yra leksikografiškai mažesnis. Šis lyginimas vyksta imant dviejų žinučių žodžius lygiagrečiai ir ieškant pirmos žodžių poros, kurios elementai skirtingi. Šių skirtingų žodžių leksikografinė tvarka nurodys pačių žinučių tvarką.
Neseniai Linas gavo nauja žinutę iš Martyno ir nori ją kiek įmanoma greičiau dekoduoti. Kadangi jis nenori perrinkinėti visų variantų, jis kreipėsi į jus pagalbos :)
Pradiniai duomenys
Pirmoje pradinių duomenų eilutėje bus nurodytas skaičius (), nurodantis testų kiekį. Kiekvieną testą sudarys skaičius (). Kitose eilutėse bus pateikti du kvadratai, sudaryti iš eilučių ir simbolių. Pirmasis kvadratas bus kodas, o antrasis . Galiausiai testas bus pabaigtas skaičiumi (), po kurio bus nurodyti visi Linui ir Martynui žinomi žodžiai (kiekvienas žodis bus nurodytas atskiroje eilutėje ir nei vieno žodžio ilgis neviršys ).
Rezultatai
Kiekvienam testui reikės išvesti po eilutę pavidalo "Case #t: r", kur yra testo numeris (nuo iki ), o atkoduotas pranešimas (arba simbolį "-", jei pranešimo atkoduoti neįmanoma).
Pavyzdžiai
Pradiniai duomenys | Rezultatai |
---|---|
1 4 o.do .ng. grmn o.i. .*.. *.*. .... *... 2 good morning |
Case #1: good morning |