Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | Invalid task id .in, Invalid task id .out | Sursă | Invalid task id |
| Autor | Invalid task id | Adăugată de | Invalid task id |
| Timp execuţie pe test | Invalid task id sec | Limită de memorie | Invalid task id kbytes |
| Scorul tău | Invalid task id | Dificultate | Invalid task id |
Vezi solutiile trimise am schimbat restrictiile trb refacute testele. #inlucru | Statistici am schimbat restrictiile trb refacute testele. #inlucru
Invalid task id
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 ≤ 300 ; 1 ≤ M ≤ 1.200 ; 1 ≤ Q ≤ 50 ; lungimea cuvintelor este mai mica decat 100
- Pentru 10 puncte 1 ≤ N ≤ 10 ; 1 ≤ M ≤ 40 ; 1 ≤ Q ≤ 5 ; lungimea cuvintelor este mai mica decat 20
- Pentru alte 10 puncte 1 ≤ N ≤ 30 ; 1 ≤ M ≤ 120 ; 1 ≤ Q ≤ 20 ; lungimea cuvintelor este mai mica decat 60
- Pentru alte 30 de puncte 1 ≤ N ≤ 70 ; 1 ≤ M ≤ 300 ;
- Pentru alte 30 de puncte 1 ≤ N ≤ 100 ; 1 ≤ M ≤ 400 ;
- NFA-ul dat are o singura stare initiala
Exemplu
| 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 | 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).
