یک ماشین در اختیار داریم که دارای دو حافظه است. در هر لحظه می‌توانیم یک عدد را در انتهای یکی از حافظه‌ها قرار دهیم یا عدد انتهایی یک حافظه را برداریم. برای این کار ماشین از دستورهای زیر استفاده می‌کند:

• $i,x,j$ Push: عدد $x$ را در انتهای حافظه‌ی $i$‌ ام قرار می‌دهد $(1\leq i \leq 2)$ و $j$ امین دستور بعدی را اجرا می‌کند که در آن $j$ یک عدد صحیح می‌باشد (توجه کنید که اگر $j<0$، $|j|$ دستور به عقب برمی‌گردد).
• $i$ Pop: عدد انتهایی حافظه‌ی $i$ ام را برداشته و اگر این عدد $j$ باشد، $(j+1)$ امین دستور بعدی را اجرا می‌کند.
• $j$ Jump: $j$ امین دستور بعدی را اجرا می‌کند که در آن $j$ یک عدد صحیح می‌باشد (توجه کنید که اگر $j<0$، $|j|$ دستور به عقب برمی‌گردد).

یک برنامه عبارت است از دنباله‌ای متناهی از دستورهای بالا. اجرای یک برنامه از دستور اول آن شروع می‌شود و شرط خاتمه آن است که روی حافظه‌ای که خالی است عمل Pop انجام شود یا آن‌که یکی از دستورها بخواهند دستوری را اجرا کنند که موجود نباشد (قبل از اولین دستور یا بعد از آخرین دستور باشد).

$(a$ فرض کنید در هر حافظه یک عدد ۲ سپس یک عدد ۰ و پس از آن یک عدد طبیعی با ارقام ۰ و ۱ وجود دارد که رقم با ارزش کم‌تر در انتهای حافظه است و تعداد ارقام درون دو حافظه برابر است. برنامه‌ای بنویسید که پس از اجرای آن حافظه‌ی ۱ حاوی یک عدد ۲ و سپس یک عدد طبیعی با ارقام ۰ و ۱ باشد که این عدد جمع دو عدد بالا (قبل از اجرای برنامه) در مبنای ۲ است (محتوای حافظه‌ی ۲ اهمیتی ندارد). در دستور Push تنها مجازید از $x=0...2$ استفاده کنید و طول برنامه‌ی شما نباید از ۴۰ دستور بیش‌تر شود.

$(b$ فرض کنید در حافظه‌ی اول یک عدد ۴ و سپس یک عدد طبیعی با ارقام ۰ و ۱ وجود دارد و حافظه‌ی ۲ خالی است. برنامه‌ای بنویسید که پس از اجرای آن حافظه‌ی ۱ حاوی یک عدد ۴ و سپس یک عدد طبیعی با ارقام ۰ و ۱ باشد که این عدد طبیعی معکوس عدد بالا (قبل از اجرای برنامه) است و حافظه‌ی ۲ خالی باشد. در دستور Push تنها مجازید از $x=0...4$ استفاده کنید و طول برنامه‌ی شما نباید از ۷۰ دستور بیش‌تر شود.

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