شکلات
«پدرخوانده» در یکی از خانههای یک مکعب $1000\times 1000\times 1000$ یک شکلات قایم کرده است و «هپید» میخواهد هر چه زودتر این شکلات را پیدا کند. هر خانه از این مکعب به صورت یک ۳ تایی $(x,y,z)$ (مختصات آن خانه) نمایش داده میشود. منظور از یک مکعبمستطیل با رأس $(x,y,z)$، تمام خانههای با مختصات $(a,b,c)$ هستند که $a \leq x , b \leq y , c \leq z$ .
هپید برای اطلاع پیدا کردن از جای شکلات، میتواند بعضی وقتها به ملاقات پدرخوانده برود. هر بار که هپید پدر خوانده را ملاقات میکند، میتواند از او ۳ سوال بپرسد. بعد از اینکه هپید هر سه سوال را پرسید، پدر خوانده به سه سوالی که هپید پرسیده است جواب خواهد داد.
سوالهایی که هپید میتواند بپرسد به شکل «آیا شکلات در مکعبمستطیل با راس $(x,y,z)$ قرار دارد؟» میباشند. پدرخوانده خیلی آدم مهمیاست و سرش خیلی شلوغ است، به همین خاطر هپید حداکثر $10$ بار میتواند به ملاقات پدرخوانده برود.
- به هپید کمک کنید تا شکلات را پیدا کند.
- ثابت کنید هیچ الگوریتمی وجود ندارد که با کمتر از $10$ بار ملاقات پدرخوانده، بتواند همیشه جای شکلاتِ مخفی شده را پیدا کند.