المپدیا

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

ابزار کاربر

ابزار سایت


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

ﺷﻨﮕﻮل، ﺑﻠﻮک‌ها و ﻣﻬﻨﺪﺳﯽ ﻣﻌﻤﺎری!

ﺷﻨﮕﻮل رشته‌ی ‎$S^x$ را برابر رشته‌ی حاصل از ‎$x$‎ بار پشت سر هم قرار دادن متوالی ‎$S$‎ تعریف می‌کند. برای مثال ‎$(abc)^3=abcabcabc$‎.

ﺷﻨﮕﻮل دوست دارد در آینده اگر در زمینه‌ی برنامه‌نویسی به جایی نرسید، مهندس معمار بشود‎!‎ از همین رو، او یک عدد را ‎«بلوکی»‎ می‌نامد اگر نمایش مبنای دوی آن را بتوان به حداقل یک حالت به‌صورت ‎$B^k$‎ نوشت که ‎$B$‎ یک رشته‌ی باینری معتبر (چپ‌ترین بیتش یک است) بوده و ‎$k\ge 2$‎ باشد. برای مثال عدد ‎۱۷۰‎ که نمایش مبنای دوی آن ‎$10101010$‎ است یک عدد بلوکی است چون این رشته را می‌توان به‌صورت ‎$(10)^4$‎ نوشت. اما اعداد ‎۱۳‎ و ‎۴۴‎ بلوکی‌ نیستند.

در نهایت کار و به‌عنوان آخرین تعریف، ‎ﺷﻨﮕﻮل مجموعه‌ی ‎$P_n$‎ را برابر مجموعه‌ی تمام اعداد بلوکی کوچک‌تر از ‎$2^n$‎ می‌گیرد. برای مثال ‎$P_4=\{3,7,10,15\}$‎ است.

‎الف): باقی‌مانده‌ی تقسیم حاصل‌ضرب تمام اعضای ‎$P_8$‎ بر ‎$\Delta$‎ چند است؟

‎ب): اگر تعداد اعضای ‎$P_{24}$‎ را ‎$Q$‎ بگیریم؛ باقی‌مانده‌ی تقسیم ‎${Q}^{\Delta}$‎ بر ‎$\Delta$‎ چند است؟

‎ج): اگر تعداد اعضای ‎$P_{48}$‎ را ‎$R$‎ بگیریم؛ باقی‌مانده‌ی تقسیم ‎${R}^{\Delta}$‎ بر ‎$\Delta$‎ چند است؟


ابزار صفحه