C2 - Logická funkcia

Časový limit: 2s, Pamäťový limit: 64MiB

Programovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3.4, Python 3.11

Počet bodov: 1

[ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ]

V mestečku Algebrovo sa začína rozmáhať kriminalita - všade pobehujú obory integrity, číselné rady a plno škaredých funkcií, ktoré každému znepríjemnňujú život. Najnovšie sa začal rozmáhať gang logických funkcií. Superhrdina Booleanman sa rozhodol, že s nimi zatočí. Na to by však potreboval vedieť, ako sa tieto funkcie správajú pre nejaké dané hodnoty premenných.

Úloha

Logická funkcia sa skladá z premenných označených malými písmenami anglickej abecedy a znakov &, |, !, ( a ).
Korektné logické funkcie sú definované nasledovne:

Premenná je korektná logická funkcia.
Ak X a Y sú korektné logické funkcie, tak aj (X), !X, X&Y, X|Y sú korektné logické funkcie.

Logická funkcia má hodnotu 0 alebo 1. Znak & znamená logický súčin (and), | je logický súčet (or), ! je logická negácia (not). Poradie vyhodnocovania je nasledovné:

Zátvorky sa vyhodnocujú samostatne.
Najvyššiu prioritu má negácia.
Po negácii sa vyhodnocuje &.
Na záver sa vyhodnotí |.

Napríklad logický výraz 1&!(!0|0&1) sa vyhodnotí nasledovne:

Najskôr musíme vyhodnotiť zátvorku.
V nej najprv vyhodnotíme negáciu (!0=1) a dostaneme 1|0&1.
Následne vyhodnotíme 0&1=0 a získame 1|0.
V zátvorke získame 1|0=1.
Dostávame výraz 1&!1, z ktorého vyhodnotením negácie (!1=0) dostaneme 1&0.
Výsledok vyhodnotenia výrazu je teda 1&0=0.

Vašou úlohou bude vyhodnotiť logickú funkciu o niekoľkých premenných pre ich rôzne zadané hodnoty.

Vstup

V prvom riadku sú čísla N a M, počet premenných funkcie a počet rôznych kombinácií ich hodnôt.
Na druhom riadku je zadaná logická funkcia dĺžky L, pričom môžete predpokladať, že premenné sú označené prvými N malými písmenami anglickej abecedy.
V nasledujúcich M riadkoch je zadaný reťazec dĺžky N zložený z núl a jednotiek. i-tá premenná nadobúda hodnotu i-tého znaku tohto reťazca.

1 ≤ M ≤ 50

Výstup

Pre každý z M popisov premenných vypíšte jeden znak - hodnotu funkcie pre dané hodnoty premenných. Ak sa jej hodnota nedá jednoznačne určiť, vypíšte ?.

C1

1 ≤ N ≤ 8, 1 ≤ L ≤ 100

Funkcia neobsahuje zátvorky.

C2

1 ≤ N ≤ 26, 1 ≤ L ≤ 4000

Príklad 1

Vstup:

2 3
!!!!a&!!b|b|a&!!!!!a
10
11
01

Výstup:

0
1
1

Príklad 2

Vstup:

3 3
!(a&b&!c|(c&!b))
111
010
001

Výstup:

1
1
0

Príklad 3

Vstup:

1 2
a|!a
1
0

Výstup:

1
1

10 Finále 1