infoarena informatica de performanta

Bad macro "include(page="template/taskheader" task_id="nfa") == - am schimbat restrictiile trb refacute testele. #inlucru 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. h2. 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. h2. 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. h2. 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 h2. 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 | 1 0 1 0 0 1 0 | h3. Explicaţie !problema/nfa?lfa.png 50*100! 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). == include(page="template/taskfooter" task_id="nfa")"