Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Jei norite pateikti savo sprendimą - prisijunkite.

Baigtinis automatas

Baigtinis automatas (angl. finite state machine) - tai ypatingas orientuotas grafas, leidžiantis modeliuoti tam tikras būsenas ir jų kitimą, priklausomai nuo to, kokie duomenys "leidžiami" per automatą.

Šiame uždavinyje nagrinėsime ypatingą baigtinio automato atvejį, kuriame kiekviena viršūnė turi po lygiai dvi išeinančias briaunas, pažymėtas simboliais '0' ir '1'. Tokio baigtinio automato pradinius duomenis sudaro simbolių eilutė, sudaryta iš nulių ir vienetų. Šią simbolių eilutę "perleidus" per automatą, galutinė jo būsena ir yra ieškomas atsakymas.

Duomenų "leidimas" per automatą veikia taip:

  1. Pradedame "pradinėje" viršūnėje (ji būna iš anksto nustatyta)
  2. Tikriname pirmąjį pradinių duomenų simbolį - pagal jo reikšmę pasirenkame briauną, kuria eisime iš dabartinės viršūnės
  3. Kartojame tą patį procesą su antru, trečiu ir visais kitais pradinių duomenų simboliais tol, kol pasieksime duomenų pabaigą

Žemiau pateiktas baigtinio automato pavyzdys:

Pavyzdys

Šiame automate pradinė viršūnė yra 0 (paryškinta). Tarkime, kad pradiniai duomenys yra simbolių eilutė "100101". Panagrinėkime, kaip kinta automato būsena "leidžiant" per jį tokius duomenis:

  1. Pradinė būsena yra 0
  2. Pirmasis duomenų simbolis yra '1', tad būsena pasikeičia į 1 (nes briauna su simboliu '1' veda į viršūnę 1)
  3. Antrasis duomenų simbolis yra '0', tad būsena pasikeičia į 2
  4. Trečiasis duomenų simbolis yra '0', tad būsena pasikeičia į 4
  5. Ketvirtasis duomenų simbolis yra '1', tad būsena išlieka nepakitusi (nes briauna su simboliu '1' veda į tą pačią viršūnę, kurioje prasideda)
  6. Penktasis duomenų simbolis yra '0', tad būsena pasikeičia į 3
  7. Šeštasis duomenų simbolis yra '1', tad būsena pasikeičia į 2
  8. Pasiekėme duomenų pabaigą, tad darbą baigiame

Jūsų užduotis - parašyti programą, kuri per duota baigtinį automatą "perleistų" pateiktus duomenis ir atsakytų, kokioje būsenoje automatas baigia darbą.

Pradiniai duomenys

Pirmoje eilutėje pateiktas vienas sveikasis skaičius n - baigtinio automato būsenų (viršūnių) skaičius (1\\leqn\\leq10^5).

Toliau pateikta n eilučių. i-ojoje iš jų pateikti du tarpais atskirti skaičiai u_{i,0} ir u_{i,1}, reiškiantys, kad grafe yra briauna, einanti iš viršūnės i į viršūnę u_{i,0} ir pažymėta simboliu '0', bei briauna, einanti iš viršūnės i į viršūnę u_{i,1} ir pažymėta simboliu '1'.

Paskutinėje eilutėje pateikta simbolių eilutė s, žyminti duomenis, kuriuos reikia "perleisti" per baigtinį automatą. Simbolių eilutę sudaro nuliai ir vienetai, jos ilgis neviršija 10^5.

Viršūnės šiame uždavinyje numeruojamos nuo 0. Pradine būsena visada laikoma būsena 0.

Rezultatai

Jūsų programa turi išvesti vieną skaičių - viršūnės, kurioje baigiamas darbas, indeksą.

Pavyzdžiai

Pradiniai duomenys Rezultatai Paaiškinimas 
5
0 1
2 3
4 0
1 2
3 4
100101
 
2
 Šis pavyzdys atitinka sąlygoje nagrinėta baigtinį automatą.

Smalsiems

Įdomus faktas - sąlygoje nagrinėtas baigtinis automatas iš tikrųjų turi ir tam tikrą prasmę. Jis moka apskaičiuoti dvejetainiu pavidalu išreikšto skaičiaus dalybos iš penkių liekaną! Jei nagrinėtame pavyzdyje naudotą simbolių eilutę 100101 perskaitytume kaip dvejetainį skaičių, tai dešimtainiu pavidalu jis būtų lygus 1+4+32=37. Baigtinis automatas baigė darbą būsenoje 2, o skaičiaus 37 dalybos iš 5 liekana išties yra lygi 2! Įdomumo dėlei rekomenduojama pabandyti per automatą "perleisti" ir kitokius skaičius, kad būtų galima įsitikinti šia savybe.

Baigtiniai automatai gali būti pritaikomi ir daugybėje vietų realybėje - kompiuterinių žaidimų dirbtiniam intelektui, saldainių aparatuose, įvairiuose programiniuose procesuose ir daugelyje kitų. Daugiau su pačiais baigtiniais automatais galite susipažinti čia.