المپدیا

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

ابزار کاربر

ابزار سایت


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

گاوی و به‌هم ریختن توپ‌ها!

ببعی $n$ توپ با شماره ۱ تا $n$ دارد. ببعی که بسیار مرتب و منظم است، همه ی این توپ ها را به ترتیب پشت سرهم قرار داده. در یک روز گرم آفتابی، گاوی تصمیم گرفت تا ترتیب توپهای ببعی را به هم ریزد. گاوی برای به هم ریختن ترتیب توپها، روش زیر را انتخاب کرد:

فرض کنید مقسوم علیه‌‌‌‌های عدد $n$ به ترتیب برابر با $d_۱ \lt d_۲ \lt ...\lt d_k$ باشند. در این صورت گاوی به ازای هر عدد $۱ \le i \le k $ حرکت زیر را انجام می دهد:

ابتدا گاوی توپ ها را به ترتیب به دسته های $d_i$ تایی تقسیم می کند. سپس ترتیب توپ های درون هر دسته را برعکس می کند. به عنوان مثال اگر ببعی ۶ توپ داشته باشد، گاوی توپ ها را به این شکل به هم می ریزد:

$$\underline۱, \underline۲, \underline۳, \underline۴, \underline۵, \underline۶ \rightarrow \underline{۱, ۲}, \underline{۳, ۴}, \underline {۵, ۶} \rightarrow \underline{۲, ۱, ۴}, \underline{۳, ۶, ۵} \rightarrow \underline{۴, ۱, ۲, ۵, ۶, ۳} \rightarrow ۳, ۶, ۵, ۲, ۱, ۴ $$

ببعی بعد از این که توپ ها رادید، تصمیم گرفت مقدار عدد زیر را حساب کند:

فرض کنید شماره ی نوشته شده بر روی توپ $i$-ام (از سمت چپ) ، برابر با $a_i$ باشد. در این صورت عدد مورد نظر ببعی برابر خواهد بود با: $$M = \sum_{i=۱}^n i* a_i$$

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

$3$- الف (۱۱ نمره) : اگر $n$ برابر با ۷۲ باشد، در این صورت باقیمانده ی تقسیم $M$ بر $\Delta$ چقدر است؟

پاسخ

18111

$3$- ب (۱۱ نمره) : اگر $n$ برابر با۱۰۰۸۰ باشد، در این صورت باقیمانده ی تقسیم $M$ بر $\Delta$ چقدر است؟

پاسخ

15632

$3$- ج (۱۲ نمره) : اگر $p$ برابر با ۱۳۰۹۹ و $n$ برابر با $p^P $ باشد، در این صورت باقیمانده ی تقسیم $M$ بر $\Delta$ چقدر است؟

پاسخ

17586


ابزار صفحه