Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱۳

روی یک دستگاه n عدد کلید و یک نمایشگر قرار دارد. در ابتدا هرکدام از کلیدها یا روشن است یا خاموش و نمایشگر همیشه تعداد کلیدهای روشن را نشان می‌دهد. ما از وضعیت روشن یا خاموش بودن کلیدها اطلاع نداریم و در هر مرحله تنها می‌توانیم یک کلید دلخواه را تغییر وضعیت دهیم. حداکثر در طی چند مرحله می‌توانیم تمام کلیدها را روشن کنیم؟

  1. n۱
  2. n
  3. ۲n۱
  4. ۲n
  5. ۲n+۱

پاسخ

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

اگر با فشردن یک کلید عدد نمایشگر زیاد شد، یعنی لامپ آن خاموش بوده و حالا روشن است و نیازی به فشردن دوباره‌ی آن کلید نیست و اگر عدد کم شد باید یک بار دیگر آن را فشار دهیم. بنابراین اگر x چراغ خاموش داشته باشیم، به ازای هرکدام یک بار باید کلیدی را فشار دهیم. هم‌چنین 2(nx) بار باید کلید لامپ‌ها را فشار دهیم. تعداد کل حرکات2(nx)+x=2nxبار است.

اگر x=0 باشد همه‌ی لامپ‌ها روشن‌ هستند و نیازی به هیچ تغییر وضعیتی نیست. پس حداکثر تعداد مرحله‌ها، به ازای x=1 به‌دست می‌آید و 2n1 است.


ابزار صفحه