• محدودیت زمان: ۱ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

گلابی کوچولو در حمام نشسته و با تیله‌های ته شامپوهای تیله‌ای گلرنگ بازی می‌کند. در لحظات مختلف، گلی کوچولو وارد حمام می‌شود و به گلابی کوچولو یک شامپو می‌دهد که مدت زمان مصرف آن xix_i دقیقه است و در دقیقه‌ی tit_i تحویل داده می‌شود.

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

در این مسئله، به شما زمان‌های tit_i و مدت زمان مصرف‌های xix_i به ترتیب داده می‌شود. از شما خواسته شده است که برنامه‌ای بنویسید که در هر لحظه مشخص کند گلابی در حال مصرف کدام شامپو است، اگر او از روشی که گفته شد برای انتخاب شامپوها استفاده کند.

ورودی

در خط اول ورودی، عدد صحیح و مثبت nn داده می‌شود که تعداد شامپوها را نشان می‌دهد. 1n1001 \leq n \leq 100

در nn خط بعدی، هر خط شامل دو عدد tit_i و xix_i است که به ترتیب زمان تحویل و زمان مصرف شامپوی iiام را نشان می‌دهند. تضمین می‌شود که در تست‌های داده شده شرایط زیر برقرار باشد.

1xi1001 \leq x_i \leq 100

0=t1<t2<<tn1000 = t_1 < t_2 < \dots < t_n \leq 100

خروجی

در هر لحظه که به گلابی کوچولو شامپو داده می‌شود، باید مشخص کنید که از بین شامپوهای در دسترس، کدام یک را در حال مصرف است.

مثال‌ها

ورودی نمونه ۱

2
0 10
4 7
Plain text

خروجی نمونه ۱

1
1
Plain text

در این نمونه، در لحظه ۰ گلابی شامپوی اول را دریافت می‌کند که ۱۰ دقیقه زمان مصرف دارد. از آن‌جایی که گلابی در ابتدا تنها این شامپو را دارد، بلافاصله شروع به استفاده از آن می‌کند. سپس در لحظه ۴ گلابی شامپوی دوم را دریافت می‌کند که زمان مصرف آن ۷ دقیقه است. با اینکه شامپوی دوم تازه وارد شده است، گلابی همچنان در حال استفاده از شامپوی اول است چون ۶ دقیقه تا پایان آن باقی مانده است. بنابراین، در هر دو لحظه، گلابی همچنان در حال مصرف شامپوی شماره ۱ است.

ورودی نمونه ۲

3
0 10
10 20
31 40
Plain text

خروجی نمونه ۲

1
2
3
Plain text

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

ورودی نمونه ۳

3
0 10
1 9
19 100
Plain text

خروجی نمونه ۳

1
1
3
Plain text

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

ورودی نمونه ۴

3
0 10
1 9
18 100
Plain text

خروجی نمونه ۴

1
1
2
Plain text

در این نمونه، در لحظه ۰ گلابی شامپوی اول را دریافت می‌کند که ۱۰ دقیقه مصرف دارد و شروع به استفاده از آن می‌کند. در لحظه ۱ گلابی شامپوی دوم را دریافت می‌کند که زمان مصرف آن ۹ دقیقه است. از آن‌جایی که شامپوی اول ۹ دقیقه‌ی دیگر تمام می‌شود، گلابی از شامپوی اول استفاده می‌کند. در لحظه ۱۹، گلابی شامپوی سوم را دریافت می‌کند که ۱۰۰ دقیقه زمان مصرف دارد. از آن‌جایی که شامپوی اول و دوم تا زمان ۱۹ تمام می‌شود، در لحظه‌ی ۱۸ گلابی از شامپوی دوم استفاده می‌کند.


ارسال پاسخ برای این سؤال
فایلی انتخاب نشده است.