سوال ۸
روی یک خط ۱۳۹۲ درخت قرار گرفته‌اند که فاصله‌ی هر دو درخت متوالی از هم ۱۰۰ واحد است. ارتفاع درخت‌ها یک عدد صحیح از ۱ تا ۱۳۹۲ است و ارتفاع هیچ دو درختی برابر نیست. ما می‌توانیم در هر گام یکی از درخت‌ها را انتخاب کرده، آن را ببریم. هر درخت پس از بریده شدن به سمت راست می‌افتد و در صورتی که به درخت‌های دیگری برخورد کند آن‌ها را نیز خواهد انداخت.
دو درخت در صورتی برخورد می‌کنند که ارتفاع درخت افتاده بیش‌تر یا مساوی فاصله‌ی دو درخت باشد. با توجه به این که اطلاعی درباره‌ی ترتیب قرار گرفتن درخت‌ها نداریم، حداقل باید چند درخت را قطع کنیم تا تمامی درخت‌ها بیافتند؟
- ۳۷
- ۵۰
- ۱۰۰
- ۶۹۲
- ۱۲۹۲
راهنمایی
درخت‌هایی را که هیچ‌گاه افتادنشان باعث افتادن درخت‌های جلوترشان نمی‌شود، بیابید. مثالی بسازید که در آن نیاز است به ازای هر کدام از این درخت‌ها، یک درخت جدید بریده شود.
راهنمایی
اگر تا درخت $i$ام افتاده باشد، در چه صورتی نیاز است درخت $i+1$ام بریده شود؟ در این صورت، طول درخت $i$ام حداکثر چند است؟
پاسخ
گزینه‌ی ۳ درست است.
در صورتی که درخت‌ها به ترتیب ارتفاع قرار گرفته باشند حداقل ۱۰۰ درخت باید قطع شوند. در حالت کلی نیز با تقسیم کردن خط به بازه‌هایی که ارتفاع درخت‌ها حداقل ۱۰۰ است می‌توان با قطع اولین درخت در هر بازه آن‌ها را انداخت. پس ۱۰۰ مرحله کافی است.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
