Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | marvel.in, marvel.out | Sursă | Algoritmiada 2016 - Runda 4 - Seniors |
| Autor | Eugenie Daniel Posdarascu | Adăugată de |  Mihai Calancea •klamathix |
| Timp execuţie pe test | 0.375 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Marvel
Toata lumea stie ca Marvel este cel mai mare univers de super-eroi. In timp ce facea niste kebab, Deadpool a inceput sa se joace un nou joc pe telefon. Jocul are N misiuni numerotate de la 0 la N - 1 si incepe de la misiunea 0. De fiecare data cand termini o misiune, este posibil sa deblochezi alte misiuni sau sa te opresti. Putem reprezenta jocul drept un graf aciclic cu N noduri, muchia de la a la b reprezentand faptul ca misiunea b este deblocata in momentul in care misiunea a este terminata. Un story-line este o insiruire de misiuni (altfel spus, un lant in graf care porneste din nodul 0). La finalul fiecarei misuni, jucatorul trebuie sa se bata cu un inamic. Pentru fiecare misiune se cunoaste indicele acestui inamic (un numar natural de la 1 la K).
Deadpool are o lista cu P prieteni. El doreste sa parcurga un story-line astfel incat acea lista de prieteni sa apara ca subsir in secventa inamicilor cu care se confrunta. Lista poate sa contina acelasi prieten de mai multe ori (Deadpool se distreaza cateodata prea bine cu prietenii lui). Voi trebuie sa spuneti pentru cate din cele N misiuni, exista un astfel de story-line care se termina in nodul respectiv.
Date de intrare
Fişierul de intrare marvel.in va contine pe prima linie 4 numere N, M, K, si P reprezentand numarul de noduri, numarul de muchii, numarul de inamici si numarul de prieteni din lista lui Deadpool. Pe urmatoarele M linii se afla cate 2 numere naturale a si b reprezentand faptul ca misiunea b este deblocata in momentul in care misiunea a este terminata.
Date de ieşire
Fişierul de ieşire marvel.out va contine un singur numar natural reprezentand numarul de noduri din cele N pentru care exista un story-line cu proprietatea ceruta.
Restricţii
- 1 ≤ N ≤ ???
- 1 ≤ M ≤ ???
- 1 ≤ P ≤ ???
- 1 ≤ K ≤ ???
Exemplu
| marvel.in | marvel.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
