المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۲۰

یک رشته به طول ۱۳ حرف، متشکل از حروف w و b درنظر بگیرید. عمل به روز رسانی رشته بر حسب عدد $i$ ($۱ \le i \le ۱۳$) را به این ترتیب تعریف می‌کنیم: از حرف $i$ام از سمت چپ شروع به کار می‌کنیم. آن حرف را تغییر می‌دهیم ( یعنی w را به b و b را به w تغییر می‌دهیم). در صورتی که با این تغییر حرف $i$ام از b به w تبدیل شود به سراغ حرف بعدی یعنی حرف سمت راستیش (درصورت وجود) رفته و همین کار را انجام می‌دهیم.

به عنوان مثال رشته‌ی bwbbbbwwbbwww بعد از انجام عمل به روز رسانی روی حرف چهارم به رشته‌ی bwbwwwbwbbwww تبدیل می‌شود. فرض کنید روی رشته‌ی wwwwwwwwwwwww عملیات زیر را به ترتیب انجام می‌دهیم:

1) یک بار عمل به روز رسانی روی حرف دوم.

2) یک بار عمل به روز رسانی روی حرف پنجم.

3) هشت بار عمل به روز رسانی روی حرف یکم.

4) بیست بار عمل به روز رسانی روی حرف ششم.

شما باید مشخص کنید که در نهایت تعداد b ها در رشته‌ی حاصل از مراحل بالا چند تاست.

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

پاسخ

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

هر $w$ را با صفر و هر $b$ را با یک متناظر می کنیم تا به یک رشته‌ی باینری برسیم با این تفاوت که در این رشته کم‌ارزش‌ترین رقم، رقم سمت چپ است.

هر عمل به روزرسانی روی حرف $i$ام رشته مشابه اضافه کردن عدد$2^{i-1}$به عدد باینری آن است.

پس با انجام عملیات گفته شده در سوال به عدد 666 می‌رسیم که تعداد ارقام یک باینری آن 5 تاست.


ابزار صفحه