Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۰:الگوریتم ها:سوال ۴

سوال ۴

عدد M و تعدادی بازه داده شده است. طول هر بازه یا برابر است با a یا b. اعداد a، b و شروع بازه‌ها اعدادی طبیعی‌اند (در نتیجه پایان بازه‌ها نیز طبیعی خواهد بود). یک بازه که از x شروع می‌شود، یا به صورت [x,x+a) است یا به صورت [x,x+b). هیچ کدام از این بازه‌ها باهم تلاقی ندارند. دقت کنید که اگر یک بازه در x+a تمام شود، ممکن است بازه‌ای دیگر در x+a شروع شود. یک بازه مانند [x,x+a) را می‌توان به مکانی جدید مانند [y,y+a) منتقل کرد اگر:

  1. yعددی طبیعی باشد
  2. پایان بازه‌ی جدید (y+a) نباید از M بیش‌تر باشد.
  3. بازه‌ی [y,y+a) نباید با هیچ کدام از بازه‌های کنونی از جمله [x,x+a) تلاقی داشته باشد.

می‌خواهیم ببینیم آیا راهی وجود دارد که بازه‌ها را حرکت داد به طوری که همه‌ی بازه‌های به طول a سمت راست بازه‌های به طول b قرار گیرند. الگوریتمی چندجمله‌ای برای این کار دهید. زمان الگوریتم باید چندجمله‌ای بر حسب تعداد بازه‌ها باشد نه M.


ابزار صفحه