Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2007-04-23 22:20:48.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:logic.in, logic.outSursăONI 2006, clasa 10
AutorAdrian Nita, Maria NitaAdăugată demarcelcodreaCodrea Marcel marcelcodrea
Timp execuţie pe test0.05 secLimită de memorie7168 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Logic

Mircea cel Tanar trebuie sa imbunatateasca permanent performantele calculatoarelor pe care le are in gestiune. Se intampla cateodata, ca unele componente noi pe care le foloseste sa nu fie compatibile cu vechile calculatoare. Din acest motiv functionarea calculatoarelor "imbunatatite" poate sa nu fie corecta. Pentru a verifica corectitudinea functionarii acestor calculatoare, Mircea isi propune sa le testeze cu ajutorul unui program care verifica echivalenta unor expresii logice.
Scrieti un program care determina daca doua expresii logice sunt echivalente sau nu.
Fiecare expresie este formata din:

  • variabile, cele 26 de litere mici ale alfabetului englez, de la "a"-"z";
  • operatori binari |, &, ^ ( SAU, SI respectiv SAU EXCLUSIV);
  • operatorul unar ~ ( NEGATIE );
  • paranteze rotunde.

Expresiile vor fi evaluate respectand regulile de prioritati ale operatorilor si parantezelor pentru evaluarea expresiilor logice in care intervin ca operanzi bitii 0 si 1. Prioritatile in ordine descrescatoare sunt: parantezele rotunde " (", " )", operatorul unar " ~", operatorii binari in ordine descrescatoare " &", " ^", " |".
Doua expresii sunt echivalente daca:

Doua expresii sunt echivalente daca:

  • contin acelasi set de variabile indiferent de numarul de aparitii a variabilei in expresie;
  • pentru orice set de date de intrare pentru variabile (valori 0, 1) rezultatul obtinut este acelasi.

Date de intrare

Fisierul de intrare logic.in contine pe primul rand un numar natural n, ce reprezinta numarul testelor ce se vor evalua. Fiecare test reprezinta evaluarea a doua expresii. Pe urmatoarele 2*n linii sunt siruri de caractere ce constituie expresiile. Acestea sunt scrise pe cate o linie fiecare.

Date de iesire

Fisierul de iesire logic.out va contine n linii, pe fiecare linie k fiind mesajul "egale" sau "diferite" in functie de rezultatul evaluarii expresiilor de pe liniile 2*k si respectiv 2*k+1 din fisierul de intrare.

Restrictii si precizari

  • 1 ≤ n ≤ 50
  • n reprezinta numarul de perechi de expresii ce trebuie evaluate.
  • O expresie contine cel mult 100 de operatii si maxim 10 variabile.
  • O expresie poate avea cel mult 255 caractere. Spatiul nu este separator in interiorul unei expresii.
  • Numele unei variabile este un singur caracter, litera mica a alfabetului englez.
  • Expresiile date sunt corecte.

Exemplu

logic.inlogic.outExplicatie
4
a&(c|~c)
a
~(a|b|c|d)
~a~b&~c&~d
z&b
a&b
a|b
(a|~a)&(a|~a)&(a|~a)&(a|b)
diferite
egale
diferite
egale
Pentru ultimul set de expresii tabelul este:
a b ~a a|~a (a|~a)&(a|~a)&(a|~a) a|b E
0 0  1  1  1  0  0
0 1  1  1  1  1  1
1 0  0  1  1  1  1
1 1  0  1  1  1  1
unde E=(a|~a)&(a|~a)&(a|~a)&(a|b)
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?