- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
گلابی کوچولو در حمام نشسته و با تیله‌های ته شامپوهای تیله‌ای گلرنگ بازی می‌کند. در لحظات مختلف، گلی کوچولو وارد حمام می‌شود و به گلابی کوچولو یک شامپو می‌دهد که مدت زمان مصرف آن $x_i$ دقیقه است و در دقیقه‌ی $t_i$ تحویل داده می‌شود.
گلابی می‌خواهد هرچه سریع‌تر هر شامپو را تمام کند و به تیله‌های آخرش برسد. بنابراین، در شروع هر دقیقه، از بین شامپوهایی که در دسترس دارد، آن را انتخاب می‌کند که زودتر از بقیه تمام می‌شود. اگر چند شامپو با این خاصیت وجود داشته باشد، شامپویی را انتخاب می‌کند که زودتر وارد حموم شده است.
در این مسئله، به شما زمان‌های $t_i$ و مدت زمان مصرف‌های $x_i$ به ترتیب داده می‌شود. از شما خواسته شده است که برنامه‌ای بنویسید که در هر لحظه مشخص کند گلابی در حال مصرف کدام شامپو است، اگر او از روشی که گفته شد برای انتخاب شامپوها استفاده کند.
ورودی
در خط اول ورودی، عدد صحیح و مثبت $n$ داده می‌شود که تعداد شامپوها را نشان می‌دهد. $$1 \leq n \leq 100$$
در $n$ خط بعدی، هر خط شامل دو عدد $t_i$ و $x_i$ است که به ترتیب زمان تحویل و زمان مصرف شامپوی $i$ام را نشان می‌دهند. تضمین می‌شود که در تست‌های داده شده شرایط زیر برقرار باشد.
$$1 \leq x_i \leq 100$$
$$0 = t_1 < t_2 < \dots < t_n \leq 100$$
خروجی
در هر لحظه که به گلابی کوچولو شامپو داده می‌شود، باید مشخص کنید که از بین شامپوهای در دسترس، کدام یک را در حال مصرف است.
مثال‌ها
ورودی نمونه ۱
2
0 10
4 7
خروجی نمونه ۱
1
1
در این نمونه، در لحظه ۰ گلابی شامپوی اول را دریافت می‌کند که ۱۰ دقیقه زمان مصرف دارد. از آن‌جایی که گلابی در ابتدا تنها این شامپو را دارد، بلافاصله شروع به استفاده از آن می‌کند. سپس در لحظه ۴ گلابی شامپوی دوم را دریافت می‌کند که زمان مصرف آن ۷ دقیقه است. با اینکه شامپوی دوم تازه وارد شده است، گلابی همچنان در حال استفاده از شامپوی اول است چون ۶ دقیقه تا پایان آن باقی مانده است. بنابراین، در هر دو لحظه، گلابی همچنان در حال مصرف شامپوی شماره ۱ است.
ورودی نمونه ۲
3
0 10
10 20
31 40
خروجی نمونه ۲
1
2
3
در این نمونه، در لحظه ۰ گلابی شامپوی اول را دریافت می‌کند که ۱۰ دقیقه مصرف دارد و شروع به استفاده از آن می‌کند. در لحظه ۱۰ گلابی شامپوی دوم را دریافت می‌کند که زمان مصرف آن ۲۰ دقیقه است. از آن‌جایی که شامپوی اول تا زمان ۱۰ تمام می‌شود، گلابی از شامپوی دوم استفاده می‌کند. در لحظه ۳۱، گلابی شامپوی سوم را دریافت می‌کند که ۴۰ دقیقه زمان مصرف دارد. از آن‌جایی که شامپوی دوم تا زمان ۳۱ تمام می‌شود، گلابی از شامپوی سوم استفاده می‌کند.
ورودی نمونه ۳
3
0 10
1 9
19 100
خروجی نمونه ۳
1
1
3
در این نمونه، در لحظه ۰ گلابی شامپوی اول را دریافت می‌کند که ۱۰ دقیقه مصرف دارد و شروع به استفاده از آن می‌کند. در لحظه ۱ گلابی شامپوی دوم را دریافت می‌کند که زمان مصرف آن ۹ دقیقه است. از آن‌جایی که شامپوی اول هم ۹ دقیقه‌ی دیگر تمام می‌شود، گلابی از شامپوی اول استفاده می‌کند. در لحظه ۱۹، گلابی شامپوی سوم را دریافت می‌کند که ۱۰۰ دقیقه زمان مصرف دارد. از آن‌جایی که شامپوی اول و دوم تا زمان ۱۹ تمام می‌شود، گلابی از شامپوی سوم استفاده می‌کند.
ورودی نمونه ۴
3
0 10
1 9
18 100
خروجی نمونه ۴
1
1
2
در این نمونه، در لحظه ۰ گلابی شامپوی اول را دریافت می‌کند که ۱۰ دقیقه مصرف دارد و شروع به استفاده از آن می‌کند. در لحظه ۱ گلابی شامپوی دوم را دریافت می‌کند که زمان مصرف آن ۹ دقیقه است. از آن‌جایی که شامپوی اول ۹ دقیقه‌ی دیگر تمام می‌شود، گلابی از شامپوی اول استفاده می‌کند. در لحظه ۱۹، گلابی شامپوی سوم را دریافت می‌کند که ۱۰۰ دقیقه زمان مصرف دارد. از آن‌جایی که شامپوی اول و دوم تا زمان ۱۹ تمام می‌شود، در لحظه‌ی ۱۸ گلابی از شامپوی دوم استفاده می‌کند.
ارسال پاسخ برای این سؤال