Turing#6923
Bəzi maraqlı sənədlər yaxınlarda ACM arxivlərində tapılıb. Bu sənədlər, İngiltərənin Bletchley Parkında 1943-cü ildə keçirilmiş ACM ICPC yarışmasının orijinal versiyasının hesabını ehtiva edir.
Bu orijinal müsabiqədə iştirakçılar tərəfindən təqdim olunan proqramlar, əksəriyyətinizin tanış olduğu deterministik Turing Maşınının sadələşdirilmiş versiyasında icra olunurdu. Bu versiyada lent sonsuz deyil. Əksinə, lent hüceyrələri soldan sağa 0-dan 10^3-1-ə qədər nömrələnir. Həmçinin, istifadə olunan əlifba unar əlifbadır, yəni proqramın icrasından əvvəl lent n ədəd birlərdən ibarət olan və ardınca sıfırlar gələn bir sətirlə başlanır. Burada n girişin ədədi dəyəridir və icradan sonra lentin məzmunu m ədəd birlərdən ibarət olmalıdır, burada m müvafiq çıxışın ədədi dəyəridir. Başlanğıcda, lent başlığı 0 mövqeyindədir və vəziyyətlər də 0-dan başlayaraq nömrələnir, bu başlanğıc vəziyyəti hesab olunur. Maşınlar adi qaydada işləyir: hər bir maşın vəziyyəti q və hər bir bit c (0 və ya 1) üçün, lent başlığının mövqeyindəki simvol c və cari vəziyyət q olduqda növbəti vəziyyətin nə olacağını müəyyən edən ən çox bir qayda var; qayda həmçinin cari mövqedə yazılacaq simvolu və başlığın hansı istiqamətə hərəkət edəcəyini də müəyyən edir. Heç bir qayda tətbiq olunmadıqda, maşın dayanır.
Sizin vəzifəniz iştirakçılar tərəfindən təqdim olunan Turing maşınlarından birini, həmçinin istifadə olunan test halları (giriş və çıxış cütləri) qəbul edən və hər bir hal üçün maşının nəticələri haqqında qərar verən bir proqram yazmaq olacaq. Qeyd edək ki, bu orijinal müsabiqədə, mövcud olanın əksinə, hər bir test halı üçün fərqli bir qərar var idi, ümumi bir qərar əvəzinə.
Giriş, Turing Maşınının və müvafiq test halların spesifikasiyalarından (ən çox 30) ibarətdir.
Hər bir test halının strukturu aşağıdakı kimidir:
Birinci sətir maşın üçün qaydaların sayı 1 ≤ N ≤ 1000 və Turing Maşını üçün test halların sayı 1 ≤ M ≤ 100 ehtiva edir.
N sətir izləyir, hər biri bir qayda ehtiva edir, format q_prev c_prev q_next c_next mov. q_prev qayda tətbiq olunmadan əvvəl maşının vəziyyətidir, c_prev qayda tətbiq olunmadan əvvəl cari mövqe p-də lentin məzmunudur (ya 0, ya da 1), q_next qayda tətbiq olunduqdan sonra maşının vəziyyətidir, c_next qayda tətbiq olunduqdan sonra mövqe p-nin məzmunudur və mov qayda tətbiq olunduqdan sonra lent başlığının bir addım hərəkət etdiyi istiqamətdir ("L" sola hərəkət edərsə və "R" sağa hərəkət edərsə). Vəziyyətlər 0 ilə 1000 arasında tam ədədlər olmalıdır. Turing maşını deterministik olmalıdır; yəni hər hansı bir cüt (q_prev, c_prev) üçün ən çox bir keçid olmalıdır və çıxışınızda təkrarlanmamalıdır.
Bundan sonra, M sətir izləyir, hər biri iki boşluqla ayrılmış ədəd ehtiva edir, X və Y, 1 ≤ X, Y ≤ 1000. X proqramın giriş dəyəridir və Y gözlənilən çıxış dəyəridir.
Girişin sonu N = 0 və M = 0 olan bir hal ilə işarələnir.
Çıxışınız maşın yuxarıda göstərilən lent diapazonundan kənar hər hansı bir hüceyrəyə daxil olmağa cəhd edərsə MLE olmalıdır; əgər maşın dayanmayaraq və ya MLE xətası yaratmadan ən azı 10^4 iterasiya işləyərsə TLE olmalıdır; əgər maşın dayanarsa, lakin səhv nəticə qaytararsa WA olmalıdır və əgər maşın dayanarsa və gözlənilən nəticəni qaytararsa AC olmalıdır.
Hər bir hal üçün çıxış fərqli bir sətirdə olmalıdır.
Nümunə 1