المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی سوم:دوره ی ۲۸:سوال ۵

کاغذ رنگی

باشگاه دانش‌پژوهان جوان، به تازگی یک سکوی ویژه برای اهدای مدال‌ها در انتهای دوره‌ی تابستان ساخته است. باشگاه تلاش بسیاری برای فاش نشدن جزییات ظاهری سکو تا پایان دوره‌ی تابستان امسال، انجام داده است. با این وجود، مشخص شده است که سکو از چندین بلوک تشکیل شده است که از چپ به راست در کنار یک‌دیگر چیده شده‌اند که می‌توان به آن‌ها به شکل مستطیل‌هایی به طول واحد نگاه کرد که اضلاع آن‌ها موازی است و در راستای طولشان کنار یک‌دیگر قرار گرفته‌اند.

مشخص شده است که اگر سکو از $n$ بلوک ساخته شده باشد، ارتفاع بلوک‌ها جایگشتی از اعداد $1$ تا $n$ است اما هیچ اطلاعاتی درباره‌ی ترتیب آن‌ها منتشر نشده است. علاوه بر این تعداد بلوک‌ها (مقدار $n$) نیز نامشخص است.

باشگاه قصد دارد این سکو را با کاغذ رنگی تزیین کند اما برای سادگی در انجام تعمیرات، محدودیت‌هایی برای این‌کار در نظر گرفته است:

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

باشگاه همچنین قصد دارد محدودیتی برای طول کاغذ رنگی‌ها در نظر بگیرد اما هنوز مقدار آن را مشخص نکرده است.

باشگاه می‌خواهد فرآیند تزیینات با کم‌ترین تعداد کاغذ رنگی انجام شود اما از آن‌جا که نمی‌خواهد اطلاعاتی راجع به سکو فاش کند، تصمیم گرفته است مسئولیت را به باهوش‌ترین فرد واگذار کند. فرض کنید سکو $n$ بلوک داشته باشد. به ازای هر یک از $n!$ حالت چینش بلوک‌ها، کم‌ترین تعداد کاغذ رنگی برای تزیین سکو مطابق شرایط گفته شده و حداکثر طول کاغذ رنگی $k$ را محاسبه می‌کنیم و اعداد حاصل را با هم جمع می‌زنیم. عدد حاصل را با $f(n, k)$ نشان می‌دهیم. برای مثال $f(2, 2) = 4$. باشگاه از داوطلبان خواسته است تا مقادیر این تابع را برای ورودی‌های مختلف محاسبه کنند.

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

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

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

پاسخ

168275

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

پاسخ

95571

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

پاسخ

158786


ابزار صفحه