Revizia anterioară Revizia următoare
| 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 ≤ 100.000 ; 1 ≤ N ≤ 400.000
- Pentru 50 de puncte 1 ≤ N ≤ 1.000 ; 1 ≤ N ≤ 4.000
- NFA-ul dat are o singura stare initiala
Exemplu
| nfa.in | nfa.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
