Dolenjec

Osnovne informacije

Omejitve
  • Čas: 2 s
  • Spomin: 128 MB
Avtor:
  • Vid Kocijan
  • UPM 2018

Pošlji rešitev



Tvoji rezultati.
Nisi poslal še nobene rešitve.
Več »

Navodila za navadne smrtnike

Dolenjec Polde je ujel zlato ribico, ki uresničuje želje. Vedno si je želel, da bi večno hodil po gostilnah. Prijazna zlata ribica mu je željo tudi uresničila. Na tej točki pa se je Polde zamislil nad tem, kar je storil. Sedaj je nesmrten, preostanek večnosti pa bo hodil od ene gostilne do druge. V nobeni se ne bo mogel ustaviti. Lahko bo le vzel pijačo in šel dalje. Poldetova vas ima n stavb, označenih s števili od 1 do n, ki jih povezuje m enosmernih cest. V vasi je d gostiln, ki se nahajajo v stavbah z oznakami f_1, \ldots, f_d. Denimo, da Polde svojo pot začne pri stavbi q_0. Ali lahko vekomaj obiskuje gostilne, če hodi le po cestah? Bolj formalno, Poldetova pot po cestah mora biti neskončna in mora vsebovati neskončno obiskov ene ali več gostiln. Ni pomembno, katere gostilne obiskuje ali koliko drugih stavb obišče vmes.

Navodila za teoretične računalnikarje

Dan je nedeterminističen Büchijev avtomat A=(Q=\{1,\ldots,n\},\Sigma=\{0\},\Delta,I=\{q_0\},F). Ali velja L(A)\neq \emptyset?

V prvi vrstici so podana števila n=|Q|, m=|\Delta|, d=|F| in q_0. V drugi vrstici sledijo elementi f_1, \ldots, f_d \in F, ločeni s presledki. Nato sledi m vrstic z naštetimi elementi relacije \Delta \subseteq Q \times Q. Program naj izpiše DA, če L(A)\neq \emptyset, in NE sicer.

Vhodni podatki

V prvi vrstici se nahajajo s presledkom ločena števila n, m, d in q_0.

V drugi vrstici sledi d s presledki ločenih števil f_1, \ldots, f_d, tj. seznam gostiln.

Nato sledi m vrstic. V vsaki sta podani (ne nujno različni) števili b_i in c_i. Od stavbe b_i do stavbe c_i vodi enosmerna cesta.

Omejitve vhodnih podatkov

  • 1 \leq n,m,d \leq 10^5

Izhodni podatki

Izpišite DA, če lahko Polde večno obiskuje gostilne, sicer pa izpišite NE.

Primeri

Vhod

3 2 1 1
3
1 2
2 3

Izhod

NE

Vhod

4 5 3 1
3 4 1
1 2
2 3
3 2
2 4
4 2

Izhod

DA

Vhod

3 3 1 1
3
1 2
2 3
3 3

Izhod

DA

Komentar

Pri prvem primeru Polde pride do gostilne v stavbi 3, vendar od tam svoje poti ne more nadaljevati po cesti.

Pri drugem primeru lahko Polde pride do gostilne v stavbi 3 in preostanek večnosti hodi od gostilne v stavbi 3 do gostilne v stavbi 4 in nazaj.

Pri tretjem primeru lahko Polde hodi po poti iz gostilne v stavbi 3 nazaj v isto gostilno.

Tip: Log in to
  • submit and test your solution
  • post or read questions and answers about this task