المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۷:برنامه نویسی:سوال ۵

سوال ۵

یکی از روش‌های نمایش اعداد روش ‎ گاما کد است. در این روش عدد صحیح ‎$x$‎ که ‎$0<x$‎ است، به صورت زیر نشان داده می‌شود.

اگر ‎$2^k \leq x < 2^{k+1}$‎، نمایش مبنای دوی ‎$x$‎ به صورت مقابل است: ‎$a_0a_1\ldots a_{k-1}a_k$‎. در این صورت گاما کد ‎$x$‎ به این صورت خواهد شد: ‎$\overbrace{11\ldots 1}0a_1a_2\ldots a_k$ (که تعداد ‎۱‎ ها ‎$k$‎ تاست).

به این ترتیب مثلا گاما کد ‎۱۳‎ برابر ‎$۱۱۰۱۰۱$‎ خواهد شد. هم‌چنین کد گامای عدد ‎۱‎ برابر ‎۰‎ خواهد شد. به این ترتیب طول گاما کد عدد ‎$x$‎ برابر ‎$2\times\lfloor\log{x}\rfloor+1$‎ خواهد شد (‎این موضوع از مزایای گاما کد است).

شما بایستی برنامه‌ای بنویسید که تعدادی عدد که گاما کد آن‌ها در ورودی استاندارد داده شده را بخواند و آن‌ها را در مبنای ۱۰‎ در خروجی استاندارد بنویسد. (اعداد را در خروجی با فاصله از هم جدا کنید).

بعنوان مثال اگر ورودی رشته‌ی مقابل باشد: ‎$۱۱۱۰۰۰۱۰۱۱۰۱۱۱۱۰۰۰$‎، خروجی برابر ‎$۴ \ ۷ \ ۱ \ ۹$‎ خواهد بود.


ابزار صفحه