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

کوشان مُرد (از استرس زیاد رسیدن به ددلاین‌ها ...).

بعد از مرگ کوشان واندرلند به آرامش رسید و مردم واندرلند سعی در انجام بازی‌های مفرح کردند. یکی از این بازی‌ها بزن و بشکن است. بازی بزن و بشکن یک بازی دو نفره است که در ابتدا مجموعه‌ای شامل nn قارچ (فرض کنید nn همواره زوج است) به قد ۱ موجود است. حال نحوه‌ی بازی این‌گونه است که در هر مرحله، نفر اول دو قارچ انتخاب کرده و از بازی حذف می‌کند. سپس نفر دوم می‌تواند یکی از دو حرکت زیر را انجام دهد:‌

۱- بزن: در این حرکت نفر دوم یک قارچ به قدِ مجموع قد دو قارچ انتخاب شده به مجموعه اضافه می‌کند.
۲- بشکن: در این حرکت نفر دوم یک قارچ به قدِ اختلاف قد دو قارچ انتخاب شده به مجموعه اضافه می‌کند (دقت کنید اینجا واندرلند است و قارچ با قد صفر نیز داریم!).

و سپس این حرکات انقدر ادامه پیدا می‌کند تا یکی از دو شرط زیر برآورده شود:

۱- قد همه‌ی قارچ‌ها برابر صفر شده باشد.
۲- یک قارچ با قد بزرگتر از مجموع قد قارچ‌های دیگر وجود داشته باشد.

نفر اولی که بازی را شروع می‌کند به اندازه‌ی تعداد قارچ‌های موجود در مجموعه از نفر دوم دلار می‌گیرد. بنابراین نفر دوم می‌خواهد کمترین مقدار دلار ممکن را به نفر اول بدهد و نفر اول نیز می‌خواهد بیشترین مقدار ممکن دلار را دریافت کند.

حال سپهر و رائین می‌خواهند این بازی را qq بار با هم انجام دهند و هر بار هم سپهر بازی را شروع می‌کند. اما چون nn یکتا نیست و در شرط 2ln2r2l \le n \le 2r صدق می‌کند، سپهر و رائین هر کدام nn مدنظر خودشان را پیشنهاد می‌دهند. به عبارتی دیگر رائین می‌خواهد n1n_1ای را بدهد که کمترین میزان دلار را به سپهر بدهد و سپهر می‌خواهد n2n_2ای را بدهد که بیشترین دلار را از رائین بگیرد.

قارچ صفر

ورودی

خط اول شامل یک عدد طبیعی qq است. سپس در qq خط بعدی، در هر خط دو عدد آمده‌ است که نشان دهنده‌ی l,rl, r است.1q1051 \le q \le 10^5 1lr10181 \le l \le r \le 10^{18}

خروجی

خروجی شامل qq خط میبایست باشد که خط iiام به ترتیب شامل دو عدد که تعداد دلار داده شده در حالت شروع بازی با n1n_1 و n2n_2 قارچ است.

مثال

ورودی نمونه ۱

2
2 6
8 10
Plain text

خروجی نمونه ۱

1 2
1 2
Plain text

برای query اول در ابتدا انتخاب می‌کنیم که ۲ قارچ باشد. با این کار وقتی که بازی شروع شود با انتخاب این دو قارچ و هر عملیاتی که انجام شود، تنها یک قارچ می ماند و باید یک دلار داده شود که این مقدار کمینه است. برای حالت بیشینه باید شش قارچ انتخاب کنیم که اثبات می شود اگر هر دو طرف بهینه بازی کنند ۲ دلار باید داده شود.


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