المپدیا

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

ابزار کاربر

ابزار سایت


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

دوشیدن شیر

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

ورودی

در ورودی استاندارد ابتدا $M$ تعداد ورودی‌ها و به ازای هر ورودی ابتدا $n$ تعداد گاو‌ها $(n\leq 5000)$ و سپس در $n$ خط بعد در خط $i$ ام دو عدد به نشانه‌ی زمان شروع و پایان دوشیدن گاو $i$ ام آمده است.

خروجی

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

ورودي و خروجي نمونه

ورودي نمونه خروجي نمونه
2
3
3 6
4 10
12 15
2
1 5
6 8
7 2
4 1

ابزار صفحه