المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۲۶:سوال ۲۳

سوال ۲۳

یک ساعت دیجیتال داریم که زمان را به صورت یک عدد دودویی با طول ثابت ۱۱ بیت نمایش می‌دهد که ۵ بیت سمت چپ آن نشان‌دهنده‌ی ساعت (بین ۰ تا ۲۳) و ۶ بیت سمت راست آن نشان‌دهنده‌ی دقیقه (بین ۰ تا ۵۹) است. به طور مثال این ساعت دیجیتال ساعت ۱۰ و ۲۱ دقیقه را به شکل ۰۱۰۱۰۰۱۰۱۰۱ نمایش می‌دهد. در طول یک شبانه‌روز، چند بار عددی که این ساعت نشان می‌دهد، آیینه‌ای می‌شود؟ به یک رشته آیینه‌ای می‌گوییم اگر با وارون خود برابر باشد. به طور مثال رشته‌ی ۰۱۰۱۰ آیینه‌ای است، ولی‌ رشته‌ی ۱۰۰۱۱ آیینه‌ای نیست.

  1. ۵۷
  2. ۶۰
  3. ۴۳
  4. ۴۵
  5. ۴۸

پاسخ

گزینه‌ی ۴ درست است.

۵ بیت متناظر با ساعت ۲۴ حالت دارند، به ازای هر کدام از آن‌‌ها برای آیینه‌ای شدن ۵ بیت سمت راست به صورت یکتا معلوم میشوند (وارون ۵ بیتِ سمت چپ)، بیتِ وسط هم ۲ حالت دارد، پس حد اکثر ۴۸ جواب ممکن برای مساله وجود دارد. حالت‌هایی‌ که اشتباه شمرده ایم عبارتند از حالت‌هایی‌ که ۶ بیت متناظر با دقیقه عددی بیش از ۵۹ را نشان دهند، یعنی‌ ۶۰، ۶۱، ۶۲ و ۶۳ را ممکن است اضافه شمرده باشیم. برای چک کردن کافیست ۵ بیت سمت راست این اعداد را وارون کنیم و اگر عددِ به دست آمده از ۲۴ کمتر بود، این رشته را نباید جزو جواب حساب کنیم. با وارون کردن ۵ بیت راسته اعداد ذکر شده، به ترتیب اعداد ۷، ۲۳، ۱۵، ۳۱ به دست میایند، پس به ازای ساعت‌های ۷، ۲۳ و ۱۵ و قرار دادن ۶ بیت چپ برابر ۶۰، ۶۱ و ۶۲، یک رشته‌ی آیینه‌ای ساختیم که هیچ‌وقت در ساعت نشان داده نمیشوند، پس جواب برابر $48 - 3 = 45$ است.


ابزار صفحه