Fişierul intrare/ieşire:	nfa.in, nfa.out	Sursă	Tema Unibuc
Autor	Marius Dumitran	Adăugată de	FMI No Stress 9 •fminostress9
Timp execuţie pe test	0.2 sec	Limită de memorie	32768 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

NFA

Fie un NFA (nondeterministic finite automata) format din N stari, M tranzitii si K stari finale, fiecare tranzitie presupunand o litera mica din alfabetul limbii engleze. Dandu-se Q cuvinte, afisati pentru fiecare 1 daca automatul il contine si 0, altfel.

Date de intrare

Fişierul de intrare nfa.in va contine pe prima linie 3 numere N, M si K (cu semnificatia din enunt), iar pe a 2-a linie un numar S, reprezentand starea initiala. Pe a 3-a linie se vor afla K numere reprezentand starile finale. Pe urmatoarele M linii se gasesc cate 2 numere si un caracter reprezentand tranzitia dintre 2 stari. Pe urmatoare linie se va afla un numar Q, urmatoarele Q linii vor contine cate 1 sir de caractere.

Date de ieşire

În fişierul de ieşire nfa.out se vor afla Q linii, pe fiecare dintre ele aflandu-se un numar 0 sau 1.

Restricţii

• 1 ≤ N ≤ 1.000 ; 1 ≤ M ≤ 4.000 ; 1 ≤ Q ≤ 1.000 ; lungimea cuvintelor este mai mica decat 200
• Pentru 10 puncte 1 ≤ N ≤ 10 ; 1 ≤ M ≤ 40 ; 1 ≤ Q ≤ 10 ; lungimea cuvintelor este mai mica decat 10
• Pentru alte 10 puncte 1 ≤ N ≤ 30 ; 1 ≤ M ≤ 120 ; 1 ≤ Q ≤ 50 ; lungimea cuvintelor este mai mica decat 30
• Pentru alte 30 de puncte 1 ≤ N ≤ 70 ; 1 ≤ M ≤ 400 ; 1 ≤ Q ≤ 100 ; lungimea cuvintelor este mai mica decat 50
• Pentru alte 30 de puncte 1 ≤ N ≤ 500 ; 1 ≤ M ≤ 2.000 ;
• NFA-ul dat are o singura stare initiala

Exemplu

table(example). |_. nfa.in |_. nfa.out |
| 5 5 2
3
2 5
3 1 a
1 2 b
2 1 a
3 5 a
5 4 d
7
ab
aba
abab
ad
nuchichi
a
dausu

Explicaţie

Cum se trimit solutii?