المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۸:الگوریتم ها:سوال ۴

شکلات

‎«پدرخوانده» در یکی از خانه‌های یک مکعب ‎$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$‎ بار می‌تواند به ملاقات پدرخوانده برود.

  1. به هپید کمک کنید تا شکلات را پیدا کند.
  2. ثابت کنید هیچ الگوریتمی وجود ندارد که با کم‌تر از ‎$10$‎ بار ملاقات پدرخوانده، بتواند همیشه جای شکلاتِ مخفی شده را پیدا کند.

ابزار صفحه