Lista de probleme 241

Cercetătorii ce lucrează la programul SETI au recepţionat două transmisii de date foarte ciudate, date care ar putea veni din partea unor civilizaţii extraterestre. Primul set de date este format din 10 caractere distincte, date în ordinea lor lexicografică, ce formează alfabetul extraterestru. A doua transmisie conţine cuvinte din exact 4 caractere.
Cercetătorii trebuie să ordoneze lexicografic cuvintele primite în a doua transmisie (conform alfabetului extraterestru).

Scrieţi un program care să citească lungimea unei linii şi textul dat şi care să alinieze textul la stânga şi la dreapta.

Definim un limbaj de programare, cu instrucțiuni de atribuire și de decizie. Cunoscând valorile inițiale ale tuturor variabilelor(de la a la z), să se determine valorile tuturor variabilelor după execuția unei secvențe de program.

După multe năzbâtii făcute împreună, Alex şi Cipri nu mai au voie să se întâlnească. Alex – strategul echipei – a plănuit o nouă poznă şi a decis să-i transmită prietenului său planul de luptă, constând din anumite cuvinte dintr-un mesaj m[0]. Pentru a nu fi descoperiți, i-a trimis ulterior mai multe mesaje m[1], m[2], … lui Cipri, acesta trebuind să le descifreze folosind convenția secretă stabilită la începutul prieteniei lor și să “acționeze”. Fiecare mesaj m[i] este format din mai multe cuvinte, separate prin câte un spațiu, numerotate cu valori consecutive, începând de la 1.
Pentru a afla planul, Cipri trebuie să găsească cea mai mare valoare i ≥ 0 astfel încât mesajele m[i] și m[0] să conțină cel puțin un cuvânt identic având același număr de ordine în ambele mesaje. Din m[0] se păstrează toate cuvintele care se găsesc și în mesajul m[i] cu același număr de ordine ca în m[0].
Cuvintele păstrate trebuie ordonate în ordine descrescătoare lexicografică a puterii lor. Puterea cuvântului cu numărul de ordine j în m[0] este egală cu șirul ordonat descrescător al indicilor mesajelor în care apare cu același număr de ordine ca în m[0]. Astfel, un cuvânt care a apărut cu numărul de ordine 2 în mesajele m[0], m[6] și m[8] are puterea {8,6,0}. Dacă două cuvinte au aceeași putere, vor rămâne în ordinea din mesajul inițial. Lui Cipri nu i-a mai rămas decât să citească fiecare cuvânt de la dreapta la stânga şi a descifrat tot planul de luptă Cunoscând mesajele transmise de Alex, ajutaţi-l pe Cipri să descifreze planul de luptă conform convenţiei secrete.

Scrieţi un program care citeşte cheia de codificare şi un text codificat şi determină mesajul decodificat.

Olimpia D’Info a găsit o placă gravată ce conţine mai multe cuvinte scrise cu semne grafice necunoscute, fiecare cuvânt fiind format din exact 5 semne grafice. Studiind cu atenție cuvintele, a dedus că în scrierea acestora sunt utilizate 12 semne grafice distincte şi a asociat câte o literă mică din alfabetul englez fiecărui semn. După asociere, a stabilit pentru fiecare semn o complexitate, scriind literele în ordinea crescătoare a complexităților pe care le-a stabilit anterior. Olimpia consideră că această ”complexitate” este cel mai potrivit criteriu de ordonare lexicografică.

Cunoscând ordinea semnelor și cuvintele de pe placă determinaţi:
a) Numărul de cuvinte distincte existente pe placă.
b) Şirul de cuvinte ordonat lexicografic, conform criteriului formulat de Olimpia.

Se presupune că unele dintre primele instrumente de calcul au fost beţişoarele de socotit. În problema noastră vom considera un număr ca fiind o succesiune de unul sau mai multe beţişoare, un beţişor fiind reprezentat de litera I. Într-o expresie, între oricare două numere există semnul + sau semnul *.

Exemple de numere

I
III
IIIIIIIIIII

Exemple de expresii

III
II*III
I+I*III+IIIIIII

Scrieţi un program care evaluează astfel de expresii.

Pe vremea maurilor, transmiterea unor mesaje codificate între două persoane se făcea folosind un cifru numit nod. Cele două persoane alegeau în secret o poveste. Aceasta era scrisă într-o carte folosind litere mici și mari ale alfabetului englez, pe P pagini, numerotate de la 1 la P, fiecare conținând exact R rânduri, numerotate în cadrul fiecărei pagini de la 1 la R, iar fiecare rând fiind format din exact C cuvinte, numerotate în cadrul fiecărui rând de la 1 la C.

Un cuvânt al mesajului de transmis era codificat prin poziția sa în povestea aleasă de cei doi, folosind trei numere scrise cu cifre romane, ce indicau în ordine: numărul paginii, numărul rândului în cadrul paginii, respectiv al cuvântului în cadrul rândului.
Mesajul astfel codificat era scris pe trei linii. Pe prima linie erau scrise numerele paginilor, pe a doua linie numerele rândurilor, iar pe a treia linie erau scrise numerele de ordine ale cuvintelor.

Presupunem că mesajul este format din primul cuvânt de pe al cincilea rând al celei de a doua pagini și din al patrulea cuvânt de pe rândul al doilea al primei pagini. Mesajul putea fi transmis pe trei linii în modul următor:

• II I (numerele paginilor)
• V II (numerele rândurilor)
• I IV (numerele cuvintelor)

Cifrele romane sunt scrise cu majusculele M, D, C, L, X, V, I, iar valorile corespunzătoare lor sunt în ordine: 1000, 500, 100, 50, 10, 5, 1. Valoarea unui număr scris cu cifre romane se calculează parcurgând de la stânga la dreapta cifrele numărului astfel:

• cifra curentă se adună la valoarea obținută până în acel moment, dacă cifra următoare este mai mică sau egală cu ea;
• cifra curentă se scade din valoarea obținută până în acel moment, dacă cifra următoare este mai mare decât ea;
• ultima cifră se adună întotdeauna la valoarea obținută până în acel moment.

De exemplu pentru numărul MCDXLVI scris cu cifre romane, se obține valoarea 1446 în sistem zecimal, astfel: 1000-100+500-10+50+5+1, iar pentru numărul XXI scris cu cifre romane se obține valoarea 21 în sistemul zecimal astfel: 10+10+1.

Cunoscându-se textul poveștii ales de cei doi și mesajul codificat de ei scrieți un program care rezolvă următoarele două cerințe:

a) Rescrie mesajul codificat folosind scrierea cu cifre din sistemul zecimal.
b) Afișează toate cuvintele mesajului decodificat în ordinea în care acestea apar în poveste.

Se consideră alfabetul englez compus din literele mici, de la a la z.
Se numeşte cuvânt un şir finit, eventual vid, de litere din acest alfabet.
Se numeşte expresie şablon un şir de caractere din alfabet în care pot apărea și caracterele ? şi *.

Un cuvânt se potrivește cu o expresie șablon dacă se poate obține din aceasta astfel:

• caracterul ? se înlocuiește cu o singură literă din alfabet;
• caracterul * se înlocuiește cu un cuvânt oarecare, eventual vid;
• din expresia șablon se poate elimina sau nu, înainte de a efectua înlocuirea caracterelor ? și *, un singur caracter de tip literă.

Considerându-se o expresie șablon și un șir de cuvinte, să se determine, pentru fiecare cuvânt în parte, dacă se potrivește sau nu cu expresia şablon dată.

Ilinca a citit despre criptarea mesajelor, acum dorește să comunice cu prietena ei Miruna numai prin mesaje criptate folosind un sistem propriu de criptare.

Ilinca ştie că fiecare caracter se reprezintă în memoria calculatorului pe 8 biți, în care se memorează scrierea în baza 2 a codului ASCII al caracterului respectiv. Pentru a cripta caracterul, Ilinca foloseşte o matrice pătratică având 8 linii (numerotate de la 0 la 7 de sus în jos) şi 8 coloane (numerotate de la 0 la 7 de la stânga la dreapta). Pe prima linie a matricei Ilinca scrie cei 8 biţi reprezentând scrierea în baza 2 a codului ASCII al caracterului, pe poziţia 0 fiind scrisă cifra cea mai semnificativă (corespunzătoare lui 27). Pe fiecare dintre următoarele 7 linii din matrice scrie permutarea circulară cu o poziție la stânga a liniei anterioare. Ordonează lexicografic liniile matricei formate și defineşte cript-ul caracterului ca fiind succesi­unea de biți reprezentată de ultima coloană din matrice, parcursă de sus în jos, urmată de indicele liniei din matrice pe care a ajuns după ordonarea lexicografică reprezentarea în baza 2 a codului ASCII al caracterului. Dacă există linii egale în matrice, după ordonarea lexicografică acestea îşi vor păstra ordinea relativă iniţială, astfel că linia conţinând reprezentarea în baza 2 a codului ASCII al caracterului va fi prima dintre acestea.

Pentru a cripta un mesaj, Ilinca scrie în ordine cript-urile caracterelor din mesajul respectiv.

Miruna cunoaşte sistemul de criptare al Ilincăi, ca urmare ştie să decripteze mesajele primite.

Scrieți un program care să rezolve următoarele două cerinţe:
1. citește un mesaj şi afişează mesajul criptat conform sistemului Ilincăi;
2. citeşte un mesaj criptat conform sistemului Ilincăi şi determină mesajul decriptat.