المپدیا

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

ابزار کاربر

ابزار سایت


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

نقاشی دیواری

هوشنگ مدیر زیباسازی شهر است. شهردار او را مسئول نقاشی طولانی‌ترین دیوار شهر کرده است. هوشنگ از $n$ نقاش برای انجام پروژه دعوت کرده است. او که از المپیاد کامپیوتری‌‌های قدیمی است، دیوار را که $w$ متر طول دارد، به صورت بازه‌ی $[0,w]$ می‌بیند و هم‌چنین تصمیم گرفته است که هر نقاش، در نقاشی یک قسمت پیوسته از دیوار (یک زیربازه از $[0,w]$) کمک کند. به طور دقیق‌تر، نقاش‌ $i$ ام وظیفه‌ی کمک در نقاشی بازه‌ی $[l_i,r_i]$ ($0\leq l_i < r_i \leq w$) از دیوار را بر عهده دارد. برای مدیریت بهتر، هوشنگ شرایط زیر را در اختصاص‌دهی بازه‌ به نقاش‌ها اعمال کرده است:

  • بازه‌ی هر نقاش، حداکثر با بازه‌ی $k$ نقاش دیگر اشتراک ناتهی دارد.
  • به ازای تمامی $i$ و $j$‌ هایی که ($1\leq i,j\leq n, i\neq j$)، شرایط زیر برقرار هستند:
  1. $l_i \neq l_j$
  2. $r_i \neq r_j$
  3. $l_i \neq r_j$

اگر تعداد روش‌های ممکن از اختصاص‌دهی بازه به نقاش‌ها که در شرایط بالا صدق می‌کنند، برابر با $X$ باشد، به سوالات زیر پاسخ دهید.

$1$- الف ($8$ نمره) : اگر $w=100, n=10, k=1$ باشند، باقی‌مانده‌ی $X$ بر $\Delta$ چند است؟

$1$- ب ($13$ نمره) : اگر $w=400, n=50, k=2$ باشند، باقی‌مانده‌ی $X$ بر $\Delta$ چند است؟

$1$- ج ($14$ نمره) : اگر $w=1000, n=100, k=3$ باشند، باقی‌مانده‌ی $X$ بر $\Delta$ چند است؟


ابزار صفحه