المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی سوم:دوره ی ۲۹:سوال ۴

اتاق فرار

پیمان و کیوان به همراه دوستانشان به یک اتاق فرار رفته‌اند و در آخرین مرحله باید رمز قفل نهایی را بیابند. پیمان در یکی از مراحل قبلی دو کاغذ پیدا کرده است که دنباله‌های زیر را نمایش می‌دهند.

$$ \begin{cases} b_1 = 123, b_2 = 456 \\ b_i = (2 \times b_{i - 1} + 5 \times b_{i - 2})mod \Delta \space \space \forall i > 2 \end{cases} $$ $$ \begin{cases} a_1 = 987, a_2 = 654 \\ a_i = (a_{i - 1} + 3 \times a_{i - 2}) mod \Delta \space \space \forall i > 2 \end{cases} $$

همچنین روی برگه‌ی کنار قفل نوشته شده است:

«دنباله‌ی $a$ را تا جمله‌ی $n$ و دنباله‌ی $b$ را تا جمله‌ی $m$ حساب کن. پاسخ در جدول $n \times m$ مانند $M$ است که $M_{i,j} = a_i \oplus b_j$ است. اگر به ازای هر زیر مستطیل این جدول حاصل عملگر $or$ بیتی اعداد آن زیر مستطیل را حساب کنی، مجموع این اعداد به ازای همه‌ی زیرمستطیل‌های $M$ رمز را به تو نشان می‌دهد.»

منظور از $M_{i,j}$ خانه‌ی سطر $i$ و ستون $j$ جدول $M$ و $\oplus$ عملگر $xor$ بیتی (یای انحصاری) است. یک زیر مستطیل از $M$ را می‌توان به صورت $(i_1, i_2, j_1, j_2)$ نشان داد که شامل خانه‌هایی مانند $(x, y)$ است که $$ 1 \leq i_1 \leq x \leq i_2 \leq n \space \& \space 1 \leq j_1 \leq y \leq j_2 \leq m$$

باشد. با پاسخ به سوالات زیر به کیوان، پیمان و دوستانشان کمک کنید تا رمز قفل را کشف کنند و از اتاق فرار خارج شوند.

فرض کنید رمز قفل به ازای مقادیر $n$ و $m$ را با $f(n, m)$ نشان می‌دهیم.

تمام پاسخ‌های ارائه شده در این سوال با فرض $\Delta = 229939$ محاسبه شده‌اند.

$4$- الف ($11$ نمره) : باقی‌مانده‌ی $f(1, 10^5)$ بر $\Delta$ چند است؟

پاسخ

87220

$4$- ب ($11$ نمره) : باقی‌مانده‌ی $f(1000, 1000)$ بر $\Delta$ چند است؟

پاسخ

31714

$4$- ج ($11$ نمره) : باقی‌مانده‌ی $f(10^5, 10^5)$ بر $\Delta$ چند است؟

پاسخ

153342


ابزار صفحه