Zadanie

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 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]). 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 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.


  1. Ktorého?

  2. string v C++ je v skutočnosti vector<char> s nejakými dodatočnými funkciami.

Vo všeobecných šifrách potrebujeme na dešifrovanie poznať šifrovací algoritmus a kľúč na dešifrovanie. Šifrovací algoritmus už poznáme – je popísaný v zadaní. Pravdepodobne nebude problém celý proces obrátiť a dešifrovať text. Avšak na to potrebujeme kľúč – v našom prípade číslo udávajúce posun v abecede. Tento kľúč zatiaľ nepoznáme, preto ho musíme zistiť z jednotlivých správ.

Na začiatok, keď nevieme prísť na nejaký prefíkaný spôsob, ako odhaliť kľúč, môžeme skúšať všetky možné kľúče, kým použitie jedného nevráti zmysluplný dešifrovaný text. V našom jednoduchom príklade spoznáme “zmysluplný” text tak, že na jeho začiatku sa nachádza V MENE KSP. Môžeme teda v cykle postupne prechádzať všetky možné posuny. Pre každý posun “zmenšíme” každé písmeno o 1, a v prípade, že by sme sa mali dostať pod A, tak pokračujeme od Z. Po takomto pokuse o dešifrovanie overíme, či text začína v V MENE KSP.

Predošlé riešenie má časovú zložitosť \(O(n \cdot k)\), kde \(n\) je maximálna dĺžka textu a \(k\) je počet možných kľúčov. V našom prípade riešenie nie je až také zlé, keďže texty sú pomerne krátke a písmen v abecede je len 26.

Keby však správa mohla pozostávať zo všetkých ASCII znakov, alebo nebodaj z UTF-8 znakov a bola by veľká niekoľko gigabajtov, bol by to už trochu problém. Existuje však aj rýchlejšie a jednoduchšie riešenie.

Vieme, že prvý znak textu (označme ho \(e\)) musel vzniknúť zašifrovaním V (lebo to je prvé písmeno V MENE KSP). Kľúč môžeme jednoducho vypočítať ako hodnotu \(e-V\).

V niektorých programovacích jazykoch ako napríklad C++ môžeme pracovať so znakmi priamo ako s číslami, napríklad 'D'-'A' bude číslo \(3\). V iných jazykoch musíme najprv konvertovať znaky na čísla. ord('D')-ord('A') bude mať hodnotu \(3\).

Tiež ak nám vadí, keď vyjde záporná hodnota (\(F-V\) je \(-16\)), môžeme k tomuto číslu pričítať hodnotu \(26\).

Akonáhle vypočítame \(k\), stačí dešifrovať text podobne ako v predošlom riešení, a keďže už vieme správny kľúč, stačí odčítavať od každého znaku iba raz. Takto dostaneme časovú zložitosť \(O(n)\). Pamäťovú zložitosť vieme mať dokonca \(O(1)\), keby sme vstup načítavali postupne znak po znaku a rovno vypisovali výsledok, ale pre jednoduchosť budeme načítavať celý riadok do pamäte naraz.

#include <iostream>
#include <string>
using namespace std;

int main(){
	int n; //počet riadkov vstupu
	int k; //kľúč
	string s; //string do ktorého budem načítavať
	cin >> n;
	/* Ako si niekto všimol, kombinovaním cin a getline vznikajú problémy.
	 * Nasledujúci getline načítava ešte z prvého riadku vstupu. */
	getline(cin,s);
	for (int riadok = 0; riadok < n; riadok++){
		getline(cin,s); //Načítam celý jeden riadok vstupu.
		k = (s[0] - 'V' + 26)%26; //Spočítam kľúč podľa prvého znaku stringu (pôvodne 'V').
		for (int i = 0; i < s.size(); i++){
			if (s[i] == ' ') continue; //Medzery nedešifrujem.
			s[i] = (s[i] - 'A' - k + 26)%26 + 'A'; //Dešifrujem každé písmeno.
			//+'A' a -'A' používam na prevod medzi ASCII a hodnotou znaku od 0 po 25
		}
		cout << s << endl; //Dešifrovaný text vypíšem.
	}
}
t = int(input())
for i in range(t):
    line = input()
    kluc = (ord(line[0])-ord('V')) % 26
    line = [x if x == ' ' else chr((ord(x)-ord('A')-kluc) % 26 + ord('A')) for x in line]
    print(''.join(line))

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.