المپدیا

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

ابزار کاربر

ابزار سایت


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

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

ببعی $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$$

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

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

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


ابزار صفحه