BrainFuckVM#3774
Verilmiş brainfuck proqramının bitib-bitməyəcəyini və ya sonsuz döngüyə girəcəyini müəyyən edin. Brainfuck interpretatorunda verilənlər massivinin (8-bitlik işarəsiz tam ədədlərdən ibarət) indeksi var, bu indeks "verilənlər indeksi" adlanır; verilənlər indeksinin göstərdiyi massiv girişi "cari giriş" adlanır. Brainfuck proqramı aşağıdakı səkkiz təlimatın ardıcıllığından ibarətdir:
Brainfuck proqramının interpretasiyası birinci təlimatdan başlayır və təlimat göstəricisi proqramın sonunu tərk edərsə bitir. Təlimat icra edildikdən sonra, təlimat göstəricisi sağdakı təlimata keçir (əlbəttə ki, [ və ] döngü təlimatları sıçrayışa səbəb olmadıqda).
Proqramla yanaşı, verilənlər massivinin ölçüsü də veriləcək. Verilənlər massivinin girişləri işarəsiz 8-bitlik tam ədədlər olmalıdır, adi artıqlıq və ya çatışmazlıq davranışı ilə. Proqramın əvvəlində, verilənlər massivinin girişləri və verilənlər indeksi sıfıra bərabər olmalıdır.
Verilənlər indeksinin sərhədlərindən kənara çıxması, onu digər sərhəddə verilənlər massivinə yenidən daxil etməlidir; məsələn, verilənlər indeksi sıfır olduqda onu azaltmaq, verilənlər massivinin ölçüsü minus birə bərabər etməlidir.
[ və ] təlimatları döngüləri müəyyən edir və iç-içə ola bilər. Hər verilmiş proqram yaxşı formalaşmış olacaq, yəni proqramı soldan sağa keçərkən, [ təlimatlarının sayı minus ] təlimatlarının sayı həmişə sıfırdan böyük və ya bərabər olacaq və proqramın sonunda sıfıra bərabər olacaq.
Problemin məqsədləri üçün, interpretasiya edilmiş proqramın çıxışını nəzərə almayın^1.
____________
^1 Debugging məqsədləri üçün, onu yoxlaya bilərsiniz. Nümunə girişdən üçüncü proqram "ICPC" çap edəcək; dördüncü proqram, təsadüfi bir sətir verildikdə, bir brainfuck proqramı çap edəcək ki, bu proqram icra edildikdə həmin təsadüfi sətiri çap edəcək.
Giriş, test halların sayı t (0 < t ≤ 20) olan bir sətirlə başlayır. Hər test halı üç sətirdən ibarətdir. Birinci sətir, yaddaşın ölçüsünü, proqram kodunun ölçüsünü və girişin ölçüsünü təsvir edən üç tam ədəd sm, sc, si (0 < sm ≤ 100 000; 0 < sc, si < 4 096) ehtiva edir.
İkinci sətir icra ediləcək brainfuck proqram kodunu ehtiva edir; o, sc simvoldan ibarətdir. Üçüncü sətir proqramın girişini, mətn olaraq (yalnız çap edilə bilən, boşluq olmayan simvollar) ehtiva edir. Proqram bütün mövcud girişi istehlak etdikdən sonra, giriş təlimatı cari hüceyrəni 255 olaraq təyin etməlidir.
Hər test halı üçün, bir sətir çap edin, ya "Terminates" ya da "Loops", proqramın ya məhdud sayda addımdan sonra bitib-bitmədiyini, ya da sonsuz döngüyə girib-girmədiyini göstərir. Əgər proqram döngüyə girirsə, kod massivində sonsuz döngüyə uyğun gələn iki [ və ] simvolunun indekslərini (0-əsaslı) də çap edin. Təhlükəsiz şəkildə qəbul edə bilərsiniz ki, 50 000 000 təlimatdan sonra, bir proqram ya bitib, ya da ən azı bir dəfə icra edilmiş sonsuz döngüyə düşüb. Sonsuz döngünün hər iterasiyası zamanı ən çox 50 000 000 təlimat icra edilir.
Nümunə 1