Digi Comp II#7854
Digi Comp II - bu, topların yuxarıdan daxil olduğu və keçidlər vasitəsilə dibə doğru yol tapdığı bir maşındır. Top hər dəfə bir keçidə düşəndə, keçidin vəziyyətindən asılı olaraq ya sola, ya da sağa yönəlir və bu vəziyyət dəyişir. Abstrakt olaraq, maşını çıxış dərəcəsi 2 olan zirvələrlə təmsil olunan istiqamətli qraf kimi modelləşdirmək olar, son zirvə çıxış dərəcəsi 0 olan bir zirvədir. Keçid zirvələrindən biri başlanğıc zirvədir və onun giriş dərəcəsi 0-dır. Hər bir zirvə - keçid daxili vəziyyətə (L / R) malikdir. Top başlanğıc zirvədə başlayır və son zirvəyə qədər bir yol izləyir, burada hər bir keçid zirvəsində top, keçid zirvəsinin daxili vəziyyətinə əsasən sol və ya sağ çıxış kənarını seçir. Top keçəndən sonra zirvənin daxili vəziyyəti dəyişir. Top həmişə aşağı enir və buna görə də dövrəyə düşə bilməz.
Bu maşını qrafın strukturunu, hər bir keçid zirvəsinin başlanğıc vəziyyətlərini və ona buraxılan topların sayını göstərərək "proqramlaşdırmaq" olar. Hesablamaların nəticəsi keçidlərin hesablamaların sonunda vəziyyətidir. Maraqlıdır ki, toplama, vurma, bölmə və hətta sabit evlilik problemi kimi olduqca mürəkkəb alqoritmləri proqramlaşdırmaq mümkündür. Lakin bu vəzifə Turing hesablanabilən deyil.
Aşağıdakılardan ibarətdir:
bir sıra n (0 ≤ n ≤ 10^18) və m (1 ≤ m ≤ 500000) - qrafda topların və keçidlərin sayını ehtiva edir;
m keçidləri 1-dən m-ə qədər sırayla təsvir edən sətirlər. Hər bir sətir bir simvol c (L və ya R) və iki tam ədəd L və R (0 ≤ L, R ≤ m) ehtiva edir, keçidin başlanğıc vəziyyətini (c) və sol (L) və sağ (R) çıxış kənarlarının apardığı zirvələrin nömrələrini təsvir edir. L və R eyni ola bilər.
0 nömrəli zirvə son zirvədir, 1 nömrəli zirvə isə başlanğıc zirvədir. Qrafda dövrələr yoxdur, yəni top bir zirvədən keçdikdən sonra artıq ona qayıtmayacaq.
Keçidlərin son vəziyyətini təsvir edən m simvoldan ibarət bir sıra çıxarın ('L' və 'R' ardıcıllığında 1-dən m-ə qədər).
Nümunə 1