سعید دارای ماشین عجیبی است که دارای ‎۱۰۰۰‎ خانه حافظه می‌باشد. به هر خانه حافظه یک ‎بیت‎ گفته می‌شود و بیت ‎i$‎$ام را با ‎$M[i]$‎ نشان می‌دهیم. هر بیت حافظه یکی از دو مقدار ۰ و ۱ را در خود ذخیره می‌کند.

متاسفانه مقادیر ذخیره شده در حافظه ماشین قابل رویت نیست. تنها می‌دانیم اعداد ذخیره شده در بیت‌های ‎۸۰۱‎ تا ۹۰۰ برابر ‎۰‎ و اعداد ذخیره شده در بیت‌های ‎۹۰۱‎ تا ۱۰۰۰‎ برابر ‎۱ هستند.

این ماشین عجیب تنها توانایی اجرای دستورات زیر را دارد:

• $ M[i]= M[i_1 ]∧ M[i_2 ]⋯∧ M[i_k]‎ $: با اجرای این دستور در صورتی که اعداد ذخیره شده در بیت‌های ‎$i_1$‎ام، ‎$i_2$‎ام و ‎⋯‎ و ‎$i_k$‎ام برابر ‎۱‎ باشند مقدار ‎$M[i]‎$ یک و در غیر این صورت صفر خواهد شد.

• $M[i]= M[i_1 ]∨ M[i_2 ]⋯∨ M[i_k]‎$ : با اجرای این دستور در صورتی که اعداد ذخیره شده در بیت‌های ‎$i_1$‎ام، ‎$i_2$‎ام و ‎⋯‎ و $‎i_k$‎ام برابر ‎۰‎ باشند مقدار ‎$M[i]$‎ صفر و در غیر این صورت یک خواهد شد.

• $M[i]= M[i_1 ]⊕ M[i_2 ]⋯⊕ M[i_k]$: با اجرای این دستور در صورتی که تعداد یک‌های ذخیره شده در بیت‌های $‎i_1‎$ام، ‎$i_2$‎ام و ‎⋯‎ و ‎$i_k$‎ام فرد باشد مقدار‎$M[i]$‎ یک و در غیر این صورت صفر خواهد شد.

در واقع این سه دستور به ترتیب ‎or٬and‎‎ و ‎xor‎‎ منطقی می‌باشند. بدیهی است که بلافاصله بعد از این که سعید به دستگاه دستور می‌دهد، دستگاه دستور را اجرا می‌کند. توجه کنید اندیس‌های ‎$i$‎,$‎i_1$,⋯‎,‎$i_k$‎ حداقل ۱ و حداکثر ۱۰۰۰ می‌باشند و $k$ نیز حداقل ۱ و حداکثر ۱۰۰۰ می‌باشد.

در کنار دستورات فوق، این ماشین عجیب به سوال زیر هم پاسخ می‌دهد.

• آیا هنوز اعداد ذخیره شده در بیت‌های ‎۸۰۱‎ام تا ۹۰۰ام برابر با ۰ و اعداد ذخیره شده در بیت‌های ‎۹۰۱‎ام تا ۱۰۰۰‎ام برابر با ‎۱ است؟

جواب ماشین به این سوال بله یا خیر خواهد بود.

سعید می ‌خواهد در مورد عدد $‎x = ۸ \times M[۱]‎ + ‎۴ \times M[۲]‎ + ۲ \times M[۳]‎ + ‎M[۴]‎$ اطلاعاتی کسب کند. او دوست دارد این اطلاعات را با اجرای کمترین تعداد دستور و تنها یک بار سوال پرسیدن کسب کند. به او کمک کنید تا اطلاعات زیر را بدست اورد.

توجه: در هر قسمت‌ ابتدا دستورات خود را نوشته و سپس آن را در چند سطر توضیح دهید. در هر قسمت باید از کمترین تعداد دستور ممکن استفاده کنید، اما نیازی به اثبات کمینه بودن تعداد دستورات نیست . دقت کنید در هر قسمت فقط یک‌بار می‌توانید سوال بپرسید.

الف) آیا $‎x$ بزرگتر از ‎۵‎ است؟

ب) آیا $x‎$ توانی از ‎۲‎ است؟ (دقت کنید که ‎۱‎ توانی از ۲‎ است).

پ) آیا $x‎$ بر ۳‎ بخش‌پذیر است؟