Gnirut#6924
Son zamanlarda ACM arxivlərində maraqlı sənədlər tapılmışdır. Bu sənədlər, 1943-cü ildə İngiltərənin Bletchley Parkında keçirilmiş ACM ICPC müsabiqəsinin orijinal versiyasının hesabatını əhatə edir.
Bu orijinal müsabiqədə iştirakçılar tərəfindən təqdim edilən proqramlar, çoxunuzun 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 doğru 0-dan 10^3-1-ə qədər nömrələnmişdir. 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ırlardan ibarət olan bir sətirlə başlanır, burada n girişin ədədi dəyəridir və icradan sonra lentin tərkibi 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şı 0 mövqeyindədir və vəziyyətlər də 0-dan başlayaraq nömrələnmişdir, 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şı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şın hansı istiqamətə hərəkət etməli olduğunu müəyyən edir. Heç bir qayda tətbiq olunmadıqda, maşın dayanır.
Təəssüf ki, arxivlərdə yalnız müsabiqə hakiminin qərarları tapılmışdır, təqdim edilən Turing maşınlarının və ya istifadə olunan test halları haqqında heç bir iz yoxdur. Qeyd etmək lazımdır ki, bu orijinal müsabiqədə, indiki müsabiqədən fərqli olaraq, hər bir test halı üçün fərqli bir qərar var idi, ümumi bir qərar yox idi.
Bu kəşf məşhur macəraçı Zaphod Beeblebrox-un diqqətini çəkmişdir, o, bu qərarları yaradan maşınların və giriş/çıxış "fayllarının" nümunələrini qurmaq üçün bir layihə başlatmaq niyyətindədir. Onu belə bir müəssisənin mənasızlığını başa salmaq üçün bütün səyləriniz uğursuzluqla nəticələnmişdir, həm də sizdən bu cür nümunələr yaradan bir proqram yazmağa məcbur edilmisiniz. Proqramınız iştirakçılar tərəfindən təqdim edilən Turing maşınlarından biri haqqında bir sıra qərarları qəbul etməli və aldığınız qərarların olduğu Turing maşınının spesifikasiyalarını və bir sıra test halları qaytarmalıdır.
Biz maşının çıxışının MLE (yaddaş limiti aşılmış) olacağını hesab edirik, əgər maşın yuxarıda göstərilən lent diapazonunun xaricindəki hər hansı bir hüceyrəyə daxil olmağa cəhd edərsə; TLE (vaxt limiti aşılmış) əgər maşın dayanmaq və ya MLE səhvinə səbəb olmadan ən azı 10^4 iterasiya işləyərsə; WA (səhv cavab) əgər maşın dayanarsa, lakin səhv nəticə qaytararsa və AC (qəbul edilmiş) əgər maşın dayanarsa və gözlənilən nəticəni qaytararsa.
Giriş, müəyyən sayda (ən çox 30) qərar seriyasından ibarətdir. Hər birinin ilk sətiri 1 ≤ N ≤ 100, haldakı qərarların sayını ehtiva edir. Sonrakı N sətir TLE, MLE, WA və AC sözlərindən birini ehtiva edir.
Girişin sonu N = 0 olan bir hal ilə işarələnir, bu hal işlənməməlidir.
Proqramınız üçün verilmiş bir test halı üçün çıxışınız aşağıdakı formata uyğun olmalıdır:
Birinci sətir 1 ≤ M ≤ 1000, maşın üçün qaydaların sayı və N, Turing Maşını üçün test halların sayını ehtiva edir.
Sonra M sətir gəlir, hər biri q_prev c_prev q_next c_next mov formatında bir qayda ehtiva edir. q_prev qayda tətbiq edilməzdən əvvəl maşının vəziyyətidir, c_prev qayda tətbiq edilməzdən əvvəl cari mövqe p-də lentin məzmunudur (ya 0, ya da 1), q_next qayda tətbiq edildikdən sonra maşının vəziyyətidir, c_next qayda tətbiq edildikdən sonra mövqe p-nin məzmunudur və mov qayda tətbiq edildikdən sonra lent başının bir addım hərəkət etdiyi istiqamətdir ("L" əgər sola hərəkət edirsə və "R" əgər sağa hərəkət edirsə). Vəziyyətlər 0 və 1000 arasında tam ədədlər olmalıdır. Turing maşını deterministik olmalıdır, yəni hər hansı bir cütlük (q_prev, c_prev) üçün ən çox bir keçid olmalıdır və çıxışınızda təkrarlanmamalıdır. Bundan sonra N sətir gəlir, hər biri iki boşluqla ayrılmış ədəd, X və Y, 1 ≤ X, Y ≤ 1000. X proqramın giriş dəyəridir və Y gözlənilən çıxış dəyəridir.
Qeyd: Bu tövsiyə olunan sintaksis olsa da, yeni sətir və boşluq simvollarının digər kombinasiyaları da qəbul edilə bilər.
Nümunə 1