Fişierul intrare/ieşire:nfa.in, nfa.outSursăTema Unibuc
AutorMarius DumitranAdăugată defminostress9FMI No Stress 9 •fminostress9
Timp execuţie pe test0.2 secLimită de memorie32768 kbytes
Scorul tăuN/ADificultateN/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).
  • 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 urmatoarea linie se va afla un numar Q, urmat de Q linii, fiecare cu cate un 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, a i-a valoare reprezentand acceptarea al celui de-al i-lea sir.

Restricţii

  • 1 ≤ N ≤ 300
  • 1 ≤ M ≤ 1.200
  • 1 ≤ Q ≤ 50
  • Lungimea cuvintelor este mai mica decat 150.
  • Pentru 20 de puncte 1 ≤ N ≤ 10 ; 1 ≤ M ≤ 40 ; 1 ≤ Q ≤ 5 ; lungimea cuvintelor este mai mica decat 20.
  • Pentru alte 30 de puncte 1 ≤ N ≤ 50 ; 1 ≤ M ≤ 200 ; lungimea cuvintelor este mai mica decat 100.
  • Pentru alte 30 de puncte 1 ≤ N ≤ 100 ; 1 ≤ M ≤ 400
  • NFA-ul dat are o singura stare initiala.

Exemplu

nfa.innfa.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
1
0
1
0
0
1
0

Explicaţie

Informal, trebuie sa gasiti o parcurgere in graful dat plecand de la sursa si ajungand la un nod stare finala; in parcurgere literele de pe muchii trebuie sa respecte cuvantul (a i-a muchie sa aiba pe ea a i-a litera din cuvant).

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?