المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۴:الگوریتم ها:سوال ۴

سوال ۴

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

  1. فرض کنید هیچ دونقطه ای هم $x$ یا هم $y$ نیستند، مگراین‌که دو سر یک ضلع باشند. تعداد مستطیل‌های لازم برای پوشاندن اتاق را با فرمولی صریح بر حسب $n$ بدست آورید.
  2. الگوریتمی از $O(n^3)$ برای پیداکردن تعداد مستطیل‌های لازم ارائه دهید.
  3. حال فرض کنید ممکن است در اتاق ستون هایی به شکل مستطیل با اضلاع موازی محور $x$ و $y$ مختصات داریم، طوری که هیچ کدام از ستون ها با دیواره اتاق برخوردی ندارند.

ابزار صفحه