المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی دوم:دوره ی ۱۹:سوال ۳

الماس نسبتاً درخشان

علی‌بابا در غار $n$ الماس درخشان پیدا کرده است و می‌خواهد یکی از آن‌ها را انتخاب کند و با خود ببرد. او انسان قانعی است و اصراری ندارد که حتماً درخشان‌ترین الماس را انتخاب کند. بلکه فقط می‌خواهد الماسی که با خود می‌برد٬ یکی از ۱۰ الماس برتر باشد ($n$ از ۱۰ بزرگ‌تر است).

برای ارزیابی درخشش الماس‌ها٬ یک آینه‌ی سخن‌گو وجود دارد که علی‌بابا می‌تواند دو الماس را در برابر آن قرار دهد و آینه به او می‌گوید که کدام‌یک از این دو درخشان‌تر است. با توجه به این‌که دزدان هر لحظه ممکن است سر برسند٬ وی باید با کم‌ترین سوال از آینه٬ الماسی را انتخاب کند. او با حداقل چند سوال می‌تواند این کار را انجام دهد؟


ابزار صفحه