در بعضی از خانه‌های یک مکعب $n\times n\times n$ تعدادی شکلات قرار دارد و احمد و پارسا می‌خواهند یک بازی انجام دهند. در این بازی ابتدا پارسا کل مکعب را در اختیار دارد. در هر مرحله از بازی اگر یک مکعب $k\times k \times k$ باقی‌مانده باشد نفری که نوبتش هست می‌تواند یکی از مکعب‌های $⌈k/2⌉\times ⌈k/2⌉\times ⌈k/2⌉$ درون آن را انتخاب کند و بازی را به نفر بعدی واگذارد و نفر بعدی با آن مکعب بازی را ادامه می‌دهد. درصورتی که به یک نفر مکعبی برسد که درون آن شکلات وجود نداشته باشد آن فرد بازنده است و نفر قبلی او برنده می‌شود و در صورتی که به یک نفر مکعب $1 \times 1 \times 1$ برسد که درونش شکلات است، آن فرد برنده است. برای یک مکعب که وضعیت خانه‌های آن را می‌دانیم الگوریتمی با مرتبه زمانی $Ο(n^6)$ و حافظه $Ο(n^3)$ ارائه دهید که مشخص کند در صورتی که پارسا و احمد هر دو به بهترین شکل بازی کنند چه کسی برنده است.

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