المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۹

در مسئله‌ی قبل، فرض کنید تعداد درخت‌ها ۵۰ و ارتفاع هر درخت یک عدد صحیح غیرتکراری از ۱ تا ۵۰ است. همچنین فاصله‌ی بین تمامی درخت‌ها عدد صحیح x است. در ضمن ترتیب چیدن درخت‌ها نیز در اختیار ما است. می‌خواهیم x را طوری تعیین کنیم که بتوان با یک برش تمامی درخت‌ها را انداخت. مقدار x حداکثر چند است؟

  1. ۱۶
  2. ۱۷
  3. ۱۸
  4. ۱۹
  5. ۲۰

پاسخ

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

افتادن هر درخت معادل با افتادن چند درخت دیگر خواهد بود در صورتی که ارتفاع آن از x بیش‌تر باشد. در نتیجه باید تعداد این چنین درخت‌هایی با ضریب انداختنشان (یک درخت می‌تواند چند درخت را بیاندازد) بیش‌تر از ۴۹ شود که به ازای x = ۱۷ چنین اتفاقی می‌افتد.


ابزار صفحه