المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی دوم:دوره ی ۲۵:سوال ۱

سوال ۱

رستم ۱۳۹۴ سکه با شماره‌های ۱ تا ۱۳۹۴ بر روی میز قرار داده است. تعدای از این سکه‌ها عادی (یک رو شیر و یک رو خط) و بقیه‌ی سکه‌ها هر دو شیر هستند (این تعداد می‌تواند صفر هم باشد). سهراب می‌خواهد تعداد سکه‌های هر دو رو شیر را پیدا کند ولی چشمانش بسته است. او تنها می‌تواند در هر حرکت تعدادی از سکه‌ها را انتخاب کرده و از رستم بخواهد آن‌ها را پشت و رو کند. پس از آن رستم تعداد سکه‌های روی میز که به سمت شیر هستند را به سهراب می‌گوید.

سهراب می‌داند در ابتدای کار دقیقا ۱۰۰ سکه به سمت شیر هستند، حداقل چند حرکت لازم است تا سهراب تعداد سکه‌های دو رو شیر را بیابد؟

  1. ۱۳۹۳
  2. ۱
  3. ۱۳۹۴
  4. ۱۱
  5. ۱۰

پاسخ

گزینه (۲) درست است.

اگر در حرکت اول سهراب تمامی سکه‌ها را پشت و رو کند به هدف می‌رسیم. می‌دانیم سکه‌های دو رو شیر تنها در بین 100 سکه‌ای هستند که ابتها شیر بودند. اگر هیچ‌کدام از آنها این‌گونه نباشند جواب سهراب 1294 خواهد بود. ولی به ازای هر سکه‌ی دو رو شیر، این تعداد افزایش می‌یابد. در نتیجه اگر سهراب $x$ را اعلام کند، تعداد سکه‌های دو رو شیر برابر $x - 1294$ است.


ابزار صفحه