المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره‌ی انتخاب تیم:دوره‌ی ۱۳:سوال ۲

تابع بله

برای رشته‌ی دودویی $a_1a_2...a_n$ (که در آن $a_i$، ۰ یا ۱ است) تابع $f$ را به این صورت تعریف می‌کنیم: $f(a_1a_2...a_n)=b_1b_2...b_{n-1}$، که در آن $b_i=a_i xor a_{i+1}$. پس $f^m$ یک رشته‌ی $n$ بیتی، یک رشته‌ی $n-m$ بیتی تولید می‌کند. یک آدم علاف از ما خواست برنامه‌ای بنویسیم که با دریافت رشته‌ی $n$ بیتی $S$ و مقدار $m$، $f^m(S)$ را حساب کند. ما هم دیدیم زورمان فقط به شما می‌رسد. مسئله را دادیم برای امتحان شما. ان‌شاا… که به گندگی خودتان ببخشید.

ورودی

در سطر اول فایل ورودی به ترتیب اعداد $n$ و $m$ آمده‌اند و در سطر دوم آن $\lceil \frac{n}{4} \rceil$ رقم در مبنای ۱۶ داده شده‌اند که رقم $i$ ام آن نشان‌دهنده‌ی مقدار دودویی $(a_{4i+1}a_{4i+2}a_{4i+3}a_{4i+4})_2$ در مبنای ۱۶ است. آخرین رقم در ورودی شامل $3-(n mod 4)$ بیت بی معنی‌ است که با صفر کردن بیت‌های با ارزش کم‌تر آن (در مبنای ۲) مشخص شده‌اند. ( $1\leq m < n \leq 10^7$)

خروجی

فایل خروجی باید شامل دقیقا $\lceil \frac{n-m}{4} \rceil$ رقم مبنای ۱۶ به همان فرمت ورودی باشد که نشان‌دهنده‌ی $f^m$ رشته‌ی ورودی است. $3-(n-m)mod 4$ بیت بی‌معنی رقم آخر را مثل ورودی برابر صفر قرار دهید.

ورودي و خروجي نمونه

ورودي نمونه خروجي نمونه
26 9
723b5d8
dbab0

توضیح نمونه: $f^9(01110010001110110101110110)=11011011101010110$


ابزار صفحه