روبات برق‌کار

$n$تا کلید با شماره‌های ۱ تا $n$ در یک ردیف از راست به چپ قرار دارند که تعدادی از آن‌ها خراب و بقیه سالم‌اند. همه‌ی کلیدها به برق متصل‌اند و هر کلید دو حالت «بالا» و «پایین» دارد. هر کلید یک سیم خروجی دارد. اگر کلید سالم باشد سیم خروجی آن فقط وقتی که کلید «بالا» باشد برق دارد. سیم خروجی کلید‌های خراب همیشه برق دارد. برای یافتن کلیدهای خراب از یک روبات استفاده می‌کنیم. به این روبات فهرستی از دستورات داده شده است و او باید دستورها را از ابتدا تا انتها به ترتیب اجرا کند. دستورها فقط یکی از گونه‌های زیرند:

• حالت کلید مقابل خود را بررسی کن٬
• حالت کلید مقابل را عوض کن٬
• به کلید بعدی یا قبلی برو٬
• بررسی کن که آیا خروجی کلید مقابل برق دارد یا خیر٬
• توقف کن و کلیدهای خراب را گزارش بده.

روبات در ابتدا کار خود را از کلید شماره‌ی ۱ آغاز می‌کند. ولی متاسفانه روبات ما یک اشکال فنی دارد: اگر پس از بررسی کلید مقابلش٬ خروجی آن به برق وصل باشد٬ روبات به طور خودکار کارش را مجدداً از کلید شماره‌ی ۱ آغاز می‌کند و اجرای همان دستورات داده شده را از دستور اول از سر می‌گیرد.

فرض کنید که همه‌ی کلیدها در ابتدا «بالا» هستند. شما باید دنباله‌ای از دستورات را ارایه دهید تا اگر روبات آن‌ها را دنبال کند٬ پس از توقف همه‌ی کلیدهای خراب را به درستی گزارش دهد.

• سوال بعد
• سوال قبل