المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۸

روی یک خط ۱۳۹۲ درخت قرار گرفته‌اند که فاصله‌ی هر دو درخت متوالی از هم ۱۰۰ واحد است. ارتفاع درخت‌ها یک عدد صحیح از ۱ تا ۱۳۹۲ است و ارتفاع هیچ دو درختی برابر نیست. ما می‌توانیم در هر گام یکی از درخت‌ها را انتخاب کرده، آن را ببریم. هر درخت پس از بریده شدن به سمت راست می‌افتد و در صورتی که به درخت‌های دیگری برخورد کند آن‌ها را نیز خواهد انداخت.

دو درخت در صورتی برخورد می‌کنند که ارتفاع درخت افتاده بیش‌تر یا مساوی فاصله‌ی دو درخت باشد. با توجه به این که اطلاعی درباره‌ی ترتیب قرار گرفتن درخت‌ها نداریم، حداقل باید چند درخت را قطع کنیم تا تمامی درخت‌ها بیافتند؟

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

پاسخ

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

در صورتی که درخت‌ها به ترتیب ارتفاع قرار گرفته باشند حداقل ۱۰۰ درخت باید قطع شوند. در حالت کلی نیز با تقسیم کردن خط به بازه‌هایی که ارتفاع درخت‌ها حداقل ۱۰۰ است می‌توان با قطع اولین درخت در هر بازه آن‌ها را انداخت. پس ۱۰۰ مرحله کافی است.


ابزار صفحه