Langton'un Qarışqası
Langton qarışqası, riyaziyyatçı Christopher Langtonun adını daşıyan, sadə qaydalarla işləyən, lakin maraqlı davranışlar sərgiləyən bir hüceyrə avtomatıdır. Bu avtomatın davranışları bəzi riyaziyyatçılar tərəfindən araşdırma mövzusu olaraq qəbul edilir. Qarışqalar və Langtonun hüceyrə avtomatı arasındakı əlaqə, avtomatın vəziyyətini "qarışqa" kimi təsəvvür etməyimizdən və avtomatın dinamikasını qarışqanın xüsusi bir dünyada hərəkət etməsi ilə müqayisə etməyimizdən irəli gəlir.
Qarışqanın dünyası, təyyarədəki kvadratların (və ya hüceyrələrin) mavi və ya qırmızı rəngdə olduğu bir n x n ölçülü təyyarədir. n rəqəmi dünyanın ölçüsünü göstərir. Bir hüceyrə (i, j) cütü ilə təmsil olunur, burada (1 ≤ i, j ≤ n). Qarışqa aşağıdakı qaydalara əsasən hərəkət edir:
Əgər mavi hüceyrədədirsə, hüceyrənin rəngini dəyişir, sola dönür
və qarşısındakı növbəti hüceyrəyə doğru irəliləyir;
Əgər qırmızı hüceyrədədirsə, hüceyrənin rəngini dəyişir, sağa dönür
və qarşısındakı növbəti hüceyrəyə doğru irəliləyir; və
Əgər hərəkət edə bilmirsə (çünki qarışqa dünyadan çıxa bilmir), o zaman qarışqa ölür.
Məsələn, qarışqanın şərqə baxdığı halda qırmızı hüceyrədə olduğunu fərz edək. Əgər onun dərhal cənubunda hüceyrə yoxdursa, qarışqa ölür. Əks halda, əgər onun dərhal cənubunda hüceyrə varsa, qarışqa bu hüceyrəyə bir addım ataraq cənuba baxaraq çatır və mənbə hüceyrəsinin rəngi mavi olur. Sonra qarışqa başqa bir addım atmağa çalışacaq və s.
Sizin vəzifəniz, (i) dünyanın konfiqurasiyası və (ii) qarışqanın ilkin mövqeyi verildikdə, qarışqanın dünyanın (n, n) hüceyrəsinə gedə biləcəyini müəyyən etməkdir. Qarışqanın ilkin istiqamətinin şimal olduğunu fərz etməlisiniz.
Giriş verilənləri
n x n dünyasının konfiqurasiyası n^2 bit istifadə edərək ikili notasiya ilə təbii ədəd kimi kodlaşdırıla bilər. Aşağıdakı konvensiyaları qəbul edirik: 0 = mavi, 1 = qırmızı və konfiqurasiyanın ikili təsviri dünyanın hüceyrələrini soldan sağa və aşağıdan yuxarıya doğru müəyyən edir (ən əhəmiyyətli bitdən ən az əhəmiyyətli bitə qədər olan bitləri nəzərə alaraq). Məsələn, 0100 (4 onluq notasiya ilə) ikili ədədi aşağıdakı konfiqurasiyaya malik 2 x 2 dünyasını təmsil edir:
Uyğun olaraq, 011010100 (212 onluq notasiya ilə) ikili ədədi aşağıdakı konfiqurasiyaya malik 3 x 3 dünyasını təmsil edir:
Problem girişi bir neçə test halından ibarətdir. Hər bir hal, boşluqlarla ayrılmış dörd təbii ədəd, n, c, x, y olan bir sətirdən ibarətdir və bunlar aşağıdakı kimi şərh edilməlidir:
n (1 ≤ n ≤ 16): dünyanın ölçüsü;
c (0 ≤ c < 2^(n^2)): yuxarıda izah edildiyi kimi dünyanın ilkin konfiqurasiyasını təsvir edən n^2-bit ikili ədədin onluq təsviri;
(x, y): qarışqanın dünyadakı ilkin mövqeyinin koordinatları (1 ≤ x, y ≤ n), burada (n, n) mövqeyi c-nin ən az əhəmiyyətli bitinə uyğundur.
Girişin sonu n = c = x = y = 0 olan bir sətirlə göstərilir.
Çıxış verilənləri
Hər bir test halı üçün həlliniz aşağıdakıları çıxarmalıdır:
"Bəli" əgər qarışqa ilkin mövqedən (n, n) hüceyrəsinə çatırsa;
"Kaputt!" əgər qarışqa (n, n) hüceyrəsinə çatmadan ölürsə.
Hər bir test halı üçün qarışqanın məhdud sayda addımdan sonra (n, n) hüceyrəsinə çatdığı və ya çatmadan öldüyü təmin edilir.