المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱۰

$n$ گوی خمیری در یک ردیف قرار گرفته‌اند. می‌دانیم وزن گوی $i$ام از سمت چپ $w_i$ و فاصله آن از سمت چپ‌ترین گوی $x_i$ می‌باشد ($w_i$ و $x_i$ اعداد حقیقی هستند). در ابتدای کار هر یک از گوی‌ها با سرعت ثابت $1$ شروع به حرکت می‌کند. هر گوی یا به سمت راست حرکت می کند یا به سمت چپ. اگر دو گوی در یک لحظه با هم برخورد کنند (در یک مختصات قرار گیرند) گوی کوچک‌تر در گوی بزرگ‌تر ادغام می‌شود و گوی جدید که وزنش به اندازه مجموع دو گوی قبلی است در جهت گوی بزرگ‌تر به حرکت خود ادامه می‌دهد. با دانستن وضعیت گوی‌ها به ترتیب از سمت چپ‌ترین گوی الگوریتمی از $Ο(n)$ ارائه دهید که مشخص کند در نهایت چه گوی‌هایی باقی می‌ماند و در کدام جهت حرکت می کنند.


ابزار صفحه