المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۷

درخت وراثت نموداری برای نشان دادن میزان ارثی است که به هر یک از اعضای یک خانواده طی سال‌ها رسیده است. فرض کنید تمام اموال هر فرد بین فرزندانش (در صورتی که فرزندی داشته باشد) تقسیم می‌شود. میزان ارث هر نفر عددی صحیح و نامنفی است.

به چند طریق می‌توان درخت وراثت روبه‌رو را تکمیل نمود؟

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

پاسخ

گزینه‌ی ۳ درست است.

کافی است میزان اموال افرادی را مشخص کنیم که فرزندی ندارند (برگ‌های درخت ریشه‌دار). اموال بقیه‌ی افراد به صورت یکتا مشخص می‌شود. باید زیردرخت رئوسی که مقدارشان معلوم است را به صورت جداگانه حل کنیم و برای به دست آوردن جواب نهایی جواب زیر مسئله‌ها را در هم ضرب کنیم. برای مثال برای معلوم کردن برگ‌های مربوط به رأس با عدد ۱۴ باید مقدار $14-5-4-3 = 2$ را بین دو برگ مربوطه پخش کنیم، که این کار به سه روش ممکن است. به همین ترتیب می‌توان تعداد روش‌های حل بقیه‌ی زیر درخت‌ها را پیدا کرد. جواب نهایی برابر با $21 \times 3 \times 4 \times 15 = 3780$ می‌باشد.


ابزار صفحه