Fişierul intrare/ieşire:mcript.in, mcript.outSursăConcursul National Urmasii lui Moisil 2012, Clasa a 9-a
AutorRobert PetrovAdăugată deandrici_cezarAndrici Cezar andrici_cezar
Timp execuţie pe test1 secLimită de memorie66048 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Mcript

Pe planeta Marte, transferul de informaţii în armata marţiană se făcea necriptat. Atacul cibernetic venit de pe Pământ i-a determinat să implementeze un sistem de criptare a informaţiilor. Alfabetul marţian este numeric şi conţine N simboluri, cifre de la 1 la N. În dicţionarul marţian sunt M cuvinte distincte. Marţienii au creat codul de criptare ca o succesiune c1c2...cN de simboluri distincte din alfabet cu semnificaţia: simbolul c1 este codificat prin 1, simbolul c2 este codificat prin 2 ş.a.m.d. Un cuvânt se criptează înlocuind simbolurile din care este format cu cele corespunzătoare codului de criptare. De exemplu, pentru 3 simboluri şi codul de criptare 312, cuvântul 133211 va fi criptat ca 211322. Pământenii au interceptat un mesaj format din K linii, pe fiecare linie aflându-se un număr dat de cuvinte criptate. În războiul cibernetic dintre Pământ şi Marte, pământenii au aflat codul de criptare şi dicţionarul.

Cerinţă

Ai fost desemnat informaticianul cel mai inteligent de pe Pământ şi trebuie să implementezi un algoritm care să verifice dacă propoziţiile din care este format mesajul sunt valide sau au fost alterate în drumul dintre Marte şi Pământ. O propoziţie este validă dacă toate cuvintele care o alcătuiesc apar, după decriptare, în dicţionarul marţian.

Date de intrare

Fişierul text mcript.in conţine pe prima linie numărul N de simboluri din alfabetul marţian, pe a doua linie, şirul cifrelor (fără spaţii separatoare) ce reprezintă codificarea acestora. Pe a treia linie se află numărul M de cuvinte din dicţionar, urmat de cele M cuvinte, separate prin câte un spaţiu. Pe linia următoare se află numărul K de propoziţii ale mesajului criptat interceptat apoi, pe K linii succesive, numărul de cuvinte din propoziţia curentă, urmat de cuvintele ce o formează, separate prin câte un spaţiu

Date de ieşire

În fişierul text mcript.out se vor scrie K numere binare, câte unul pe o linie, corespunzător celor K propoziţii din
mesajul criptat astfel: 1 pentru o propoziţie validă şi 0 altfel

Restricţii

  • 1 ≤ N ≤ 9
  • 1 ≤ M ≤ 1 000 000
  • un cuvânt marţian este format din maxim 9 simboluri nu neapărat distincte
  • cuvintele din mesaj folosesc doar simboluri din alfabetul marţian
  • numărul total de cuvinte din mesaj nu va depăşi 800.000
  • propoziţie are cel puţin un cuvânt

Exemplu

mcript.inmcript.out
3
132
4 213 32 31 12
3
3 312 23 21
4 13 312 13 213
1 13
1
0
1

Explicaţie

1 (312 -> 213, 23 -> 32, 21 -> 31)
0 (213 -> 312, 312-cuvânt inexistent în dicţionar)
1 (13 -> 12)

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content