Inspectoratul Şcolar Judeţean Cluj

Olimpiada de Informatică – etapa locală 27 februarie 2017

Clasa a X-a

Problema 1 - criptare 100 puncte

Cifrul Vigenere este o modalitate de criptare a unui text format doar din litere. În prealabil se

elimină orice caracter care nu este literă. Pentru a cripta se foloseşte o cheie care este un cuvânt. Cheia se

aplică în ordine, prima literă din cheie la prima literă a textului, a doua literă din cheie la a doua literă a

textului şi aşa mai departe până la sfârşitul cheii. Cheia se aplică din nou, câtă vreme fiecare literă a cheii

are o litera corespondentă în text. Literele rămase rămân necriptate.

Criptarea efectivă a unei litere din text se face astfel:

- se determină poziţia în alfabet a literei din cheie;

- litera din text se deplasează în alfabet cu numărul de poziţii egal cu poziţia literei din cheie.

Pentru a fi siguri ca orice literă se transformă tot într-o literă, în situaţia în care adunând distanţa

depăşim litera ’z’, vom continua să numărăm, revenind la litera ’a’.

Exemplu: Pentru cheia „dadi” şi textul de cifrat: „daca vantul nu sufla, vasleste!”, textul din

care au fost eliminate orice caractere care nu sunt litere mici este „dacavantulnusuflavasleste” şi

criptarea se face astfel:

Explicaţii: Prezenţa în cheie a literei ’a’ provoacă o deplasare cu o poziţie, litera ’b’ provoacă o

deplasare cu două poziţii şi aşa mai departe. Litera ’d’ (prima din cheia „dadi”) este a 4-a literă din

alfabet şi provoacă o deplasare cu 4 poziţii a literei corespunzatoare ca poziţie. Astfel, ’d’ deplasat cu 4

poziţii devine ’h’.

În funcţie de o valoare numerică citită care poate fi 1 sau 2, rezolvăm una din următoarele cerinţe:

1. Se citeşte un cuvânt, cheia şi un text oarecare. Să se afişeze textul codificat după regula descrisă

mai sus.

2. Se citesc două texte. Primul este textul care a fost criptat însă, de data aceasta, format doar din

litere mici iar al doilea este textul codificat după metoda Vigenere descrisă anterior. Cele două texte au

aceeaşi lungime. Să se determine cheia care a realizat încriptarea. În cazul în care al doilea text nu

reprezintă o criptare corectă pentru primul text, se va afişa 0.

Date de intrare

Fişierul de intrare criptare.in conţine pe prima linie un număr natural, a cărui valoare poate

fi doar 1 sau 2, reprezentând cerinţa.

Pe urmatoarele două linii ale fişierului se află un cuvânt şi un text în cazul cerinţei 1 şi două texte

în cazul cerinţei 2.

Date de ieşire

Fişierul de ieşire criptare.out va conţine o singură linie pe care va fi scris textul codificat în

cazul cerinţei 1, cheia de criptare sau 0 în cazul cerinţei 2.

Restricţii şi precizări

1 < lungime cheie < 100

lungime cheie ≤ lungime text < 1000

Atât literele cifrului cât şi textul dat sunt scrise doar cu minuscule (litere mici).

Se consideră alfabetul în forma codificată de tabela ASCII.

Cheia căutată la punctul 2, este cel mai scurt cuvânt care îndeplineşte condiţia dată. Dacă nu se

repetă de minim 2 ori se va afişa 0.

Pentru rezolvarea primei cerinţe se acordă 45 de puncte, iar pentru rezolvarea celei de-a doua, 45

de puncte.

Se acordă 10 puncte din oficiu!

Exemple

criptare.in criptare.out

1

primavara

aer

qwanfnbws

Explicaţie Din aer obţinem distanţele 1, 5 şi 18. „p”+1 devine „q”, „r”+5 devine „w”, „i”+18 devine

„a”. În mod similar mav devine nfn iar ara devine bws. În acest caz nu rămân caractere necriptate.

criptare.in criptare.out

2

primavara

qwanfjbws

0

Explicaţie Litera j din qwanfjbws este greşită, motiv pentru care nu găsim nici o cheie care să se

repete de minim 2 ori şi să codifice primavara în quanfjbws.

criptare.in criptare.out

1

un intelectual rezolva problemele. un geniu le evita.

einstein

zwwgnjushcitfwnntujtjwxpqnaxfjdblnbboqnsvita

criptare.in criptare.out

2

unintelectualrezolvaproblemeleungeniuleevita

zwwgnjushcitfwnntujtjwxpqnaxfjdblnbboqnsvita

einstein

criptare.in criptare.out

1

abababababa

abab

bdbdbdbdaba

criptare.in criptare.out

2

abababab

bdbdbdbd

ab

Explicaţie Deşi abab îndeplineşte condiţia cerută, ab este tot o soluţie însă mai scurtă.

criptare.in criptare.out

1

carte

aaa

dbste

Explicaţie Dacă cheia este mai scurtă sau egală ca lungime decât textul, se face criptarea.

criptare.in criptare.out

2

carte

dbste

0

Explicaţie Cheia nu se repetă de minim 2 ori aşa că rezultatul este 0.

Timp maxim de execuţie/test: 0.5 secunde.

Total memorie disponibilă: 2 MB din care 1 MB pentru stivă.

Dimensiunea maximă a sursei: 5 KB.