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í KSP1. 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 string
u, 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]
). 2
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 string
u 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.
Odovzdávanie
Na odovzdávanie sa musíš prihlásiť
Otázky a diskusia
Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.