المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۱۷:سوال ۳۷

سوال ۳۷

در سوال قبل، اگر به جای رنگ هر نهنگ، نام او (هم نام قاتل و هم نام مقتول) در لیست نوشته شود، چند لیست سیاه متفاوت می‌تواند وجود داشته باشد؟

  1. ۱۰۴۸۵۷۶
  2. ۱۶۷۷۷۲۱۶
  3. ۴۰۳۲۰
  4. ۲۳۰۴۰
  5. ۲۷۸۳۲۳۲

پاسخ

گزینه‌ی (۵) درست است.

فرض کنید $f(i,j)$ برابر با تعداد راه‌های نوشتن این دنباله از لحظه‌ای که دقیقآ $i$ نهنگ سفید و $j$ نهنگ سیاه باقی مانده باشد است. داریم: $f(i,j)=f(j,i)$، $f(1,i)=2\times i!$ و با حالت‌بندی روی رنگ اولین مقتول، برای هر $2\le i,j$ داریم: $f(i,j)=(f(i,j-1)+f(i-1,j))\times i \times j$ بدین ترتیب $f(2,2)=32$، $f(2,3)=264$، $f(2,4)=2496$، $f(3,3)=4752$، $f(3,4)=86976$ خواهد بود و نهایتا جواب ما یعنی $f(4,4)$ برابر با ۲۷۸۳۲۳۲ می شود.


ابزار صفحه