2. Zabezpečenie

V centrále Kryptografickej Spravodajskej Pobočky berú bezpečnosť veľmi vážne. Nedávno zistili, že niektoré semináre (napríklad Korešpondenčný Seminár z Programovania) nezabezpečujú svoju komunikáciu dostatočne. Preto navrhujú použiť nový Kryptografický Šifrovací Protokol. Je založený na technológii, ktorú používali už v starovekom Ríme.

Text sa zašifruje tak, že každé písmeno textu sa nahradí písmenom, ktoré je v abecede o \(k\) pozícií ďalej. Napríklad, ak by sme mali \(k=3\), tak všetky A sa nahradia písmenom D, B sa nahradí E, C sa nahradí F… No a v prípade, že by sme potrebovali použiť písmeno, ktoré sa nachádza v abecede za písmenom Z, pokračujeme opäť od začiatku abecedy. Písmeno X sa preto pri posunutí \(k=3\) nahradí za A, Y za B a Z za C. Medzery medzi slovami zostávajú nezmenené.

No a keďže toto šifrovanie bolo dobré pre Rímske impérium, musí byť dobré aj pre KSP. Avšak doba o pár (tísíc) rokov pokročila, preto skôr než KSP začne používať KŠP odporúčané KSP, musí byť jeho bezpečnosť otestovaná. Práve spúšťame najväčšie testovanie KŠP v histórií KSP¹. A na to potrebujeme práve teba.

Úloha

Tvojou úlohou je napísať program, ktorý bude dešifrovať text zašifrovaný pomocou KŠP.

Formát vstupu

V prvom riadku vstupu je celé číslo \(n\), pričom platí \(1\leq n \leq 20\,000\). Nasleduje \(n\) riadkov, každý obsahuje text pozostávajúci z veľkých písmen anglickej abecedy a medzier, ktorý je určený na dešifrovanie. Dĺžka riadku nepresiahne \(100\) znakov. Je známe, že každý text, pred tým ako bol zašifrovaný, začínal V MENE KSP.

Formát výstupu

Pre každý riadok textu na vstupe vypíšte do samostatného riadku dešifrovaný text (taktiež tvorený veľkými písmenami anglickej abecedy a medzerami).

Príklad

Input:

3
W NFOF LTQ WTFUDJ NVTJB OPTJU SVAPWF TVLOF
V MENE KSP NEZABUDAJTE POUZIVAT SIFROVANIE
L CUDU AIF FHEWHQCELQDYU ZU IKFUH

Output:

V MENE KSP VSETCI MUSIA NOSIT RUZOVE SUKNE
V MENE KSP NEZABUDAJTE POUZIVAT SIFROVANIE
V MENE KSP PROGRAMOVANIE JE SUPER

V prvom riadku je posun \(k=1\), v druhom sa text vôbec nedešifroval, teda \(k=0\) a v treťom je \(k=16\).

Nápoveda

V prípade, že nevieš, ako spracovávať text, nasledujúce odstavce sú určené práve pre teba.

V programovacích jazykoch máme okrem číselných premenných typu int, integer aj premenné na ukladanie znakov, ktoré zvyknú byť označované char. Premenná typu char má v podstate uložené číslo od \(0\) po \(256\) v Pascale (od \(-128\) po \(127\) v C++), pričom každému číslu zodpovedá nejaký znak: napríklad kde napríklad číslu \(65\) zodpovedá písmeno 'A', číslu \(66\) zodpovedá písmeno 'B' atď. – pozri si ASCII tabuľku na odkaze www.asciitable.com.

Nápoveda – PASCAL

Na načítanie jedného znaku zo vstupu do premennej typu char môžeme použiť funkciu read(c). Pole znakov dĺžky 255 (var s : array[0..255] of char) sa nazýva string (na nultej pozícii uložená je dĺžka stringu, s[1] je prvý znak, s[n] je \(n\)-tý znak). Na načítanie celého riadku do premennej s typu string sa používa readln(s). Dĺžku tohto stringu zistíme príkazom length(s). Znaky konca riadku sa nenačítajú. ASCII hodnotu daného znaku (jeho číselný kód) vieme zistiť pomocou ord(c). Ak chceme získať znak z jeho kódu (opačný smer ako ord) použijeme chr(cislo_znaku). Napríklad writeln(ord('A')) vypíše 65. Ak by sme napísali writeln(chr(ord('A'))), tak program vypíše A, pretože chr zoberie hodnotu znaku A vrátenú ord a vráti daný znak.

Nápoveda – C++, iostream

Premennú typu char môžeme považovať za jednobajtové číslo alebo za jeden znak. V prípade, že používame knižnicu iostream (#include <iostream>) môžeme jeden znak načítať nasledovne: cin >> c, kde c je typu char. Ak chceme znak vypísať: cout << c. Ak chceme vypísať jeho číslo: cout << int(c) – takto už program vie, že ten kus pamäte, čo považoval za char, má považovať za int. Na prácu s reťazcami znakov sa dá využiť typ string. Prístup k \(n\)-tému znaku stringu s je podobný ako v Pascale (ale nie rovnaký): s[n-1]. V C++ a podobných jazykoch sa totiž indexuje od nuly (takže prvý znak je s[0]). ²

Keď chceme číslo vypísať ako znak, môžeme to spraviť nejako takto: cout << char(66); vypíše B, keďže práve B má hodnotu 66. Funkcia s.size() vráti dĺžku s. Vtipnou záležitosťou sú “biele znaky” (whitespace characters) – to sú tie, ktoré nevidíme (medzera, tabulátor, enter). cin >> s štandardne načíta text iba po prvý biely znak. Na načítanie celého riadku do stringu s môžeme použiť getline(cin,s).

V C++ vieme s char pracovať aj ako s číslom, napríklad 'B'+1 je 'C'.

Nápoveda – C++, cstdio

Ukážeme si jednoduchý program, ktorý najprv načíta jedno číslo, potom načítava znaky až po koniec riadku (znak '\n') a tento riadok vypíše. Následne načíta dve slová (slová sú oddelené bielymi znakmi) a vypíše ich na samostatné riadky.

#include <cstdio>
int main(){
    int cislo;
    char znak;
    char slovo[256];
    scanf("%d", &cislo);
    while(scanf("%c", &znak)>0 && znak!='\n') printf("%c", znak);
    printf("\n");
    scanf("%s", slovo);
    printf("%s\n", slovo);
    scanf("%s", slovo);
    printf("%s\n", slovo);
}

Odporúčame spustiť si tento program na ukážkovom vstupe zo zadania.