- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
کوشان مُرد (از استرس زیاد رسیدن به ددلاین‌ها ...).
بعد از مرگ کوشان واندرلند به آرامش رسید و مردم واندرلند سعی در انجام بازی‌های مفرح کردند. یکی از این بازی‌ها بزن و بشکن است. بازی بزن و بشکن یک بازی دو نفره است که در ابتدا مجموعه‌ای شامل $n$ قارچ (فرض کنید $n$ همواره زوج است) به قد ۱ موجود است. حال نحوه‌ی بازی این‌گونه است که در هر مرحله، نفر اول دو قارچ انتخاب کرده و از بازی حذف می‌کند. سپس نفر دوم می‌تواند یکی از دو حرکت زیر را انجام دهد:
۱- بزن: در این حرکت نفر دوم یک قارچ به قدِ مجموع قد دو قارچ انتخاب شده به مجموعه اضافه می‌کند.
۲- بشکن: در این حرکت نفر دوم یک قارچ به قدِ اختلاف قد دو قارچ انتخاب شده به مجموعه اضافه می‌کند (دقت کنید اینجا واندرلند است و قارچ با قد صفر نیز داریم!).
و سپس این حرکات انقدر ادامه پیدا می‌کند تا یکی از دو شرط زیر برآورده شود:
۱- قد همه‌ی قارچ‌ها برابر صفر شده باشد.
۲- یک قارچ با قد بزرگتر از مجموع قد قارچ‌های دیگر وجود داشته باشد.
نفر اولی که بازی را شروع می‌کند به اندازه‌ی تعداد قارچ‌های موجود در مجموعه از نفر دوم دلار می‌گیرد. بنابراین نفر دوم می‌خواهد کمترین مقدار دلار ممکن را به نفر اول بدهد و نفر اول نیز می‌خواهد بیشترین مقدار ممکن دلار را دریافت کند.
حال سپهر و رائین می‌خواهند این بازی را $q$ بار با هم انجام دهند و هر بار هم سپهر بازی را شروع می‌کند. اما چون $n$ یکتا نیست و در شرط $2l \le n \le 2r$ صدق می‌کند، سپهر و رائین هر کدام $n$ مدنظر خودشان را پیشنهاد می‌دهند. به عبارتی دیگر رائین می‌خواهد $n_1$ای را بدهد که کمترین میزان دلار را به سپهر بدهد و سپهر می‌خواهد $n_2$ای را بدهد که بیشترین دلار را از رائین بگیرد.
 |
|---|
| قارچ صفر |
ورودی
خط اول شامل یک عدد طبیعی $q$ است. سپس در $q$ خط بعدی، در هر خط دو عدد آمده است که نشان دهنده‌ی $l, r$ است.$$1 \le q \le 10^5$$ $$1 \le l \le r \le 10^{18}$$
خروجی
خروجی شامل $q$ خط میبایست باشد که خط $i$ام به ترتیب شامل دو عدد که تعداد دلار داده شده در حالت شروع بازی با $n_1$ و $n_2$ قارچ است.
مثال
ورودی نمونه ۱
2
2 6
8 10
خروجی نمونه ۱
1 2
1 2
برای query اول در ابتدا انتخاب می‌کنیم که ۲ قارچ باشد. با این کار وقتی که بازی شروع شود با انتخاب این دو قارچ و هر عملیاتی که انجام شود، تنها یک قارچ می ماند و باید یک دلار داده شود که این مقدار کمینه است. برای حالت بیشینه باید شش قارچ انتخاب کنیم که اثبات می شود اگر هر دو طرف بهینه بازی کنند ۲ دلار باید داده شود.
ارسال پاسخ برای این سؤال