- محدودیت زمان: ۱.۵ ثانیه
- محدودیت حافظه: ۵۱۲ مگابایت
- منبع: آزمون نهایی سوم دوره ۲۷ المپیاد کامپیوتر
شنلقرمزی یک گرافکار قوی است. او بازه به شکل دارد. حال او گرافی راسی ساختهاست که راس اُم متناظر با بازهی اُم است. او بین دو راس و یال میگذارد، اگر و فقط اگر بازهی و اشتراک داشته باشند (یعنی ). حال او از شما میخواهد تا تعداد مجموعههای غالب Dominating Set این گراف را بیابید.
مجموعهی متشکل از تعدادی از رئوس گراف، مجموعهی غالب است اگر و تنها اگر هر راس در یا عضو باشد یا یکی از همسایههایش عضو باشد.
ورودی
در خط اول ورودی عدد ، تعداد بازهها آمدهاست.
در خط بعدی و ، شروع و پایان بازهی ام آمدهاست.
خروجی
در تنها سطر خروجی باقیماندهی تعداد مجموعههای غالب بر را چاپ کنید.
زیرمسئلهها
زیرمسئله | نمره | محدودیت |
---|---|---|
۱ | ۱۲ | |
۲ | ۴۰ | |
۳ | ۴۸ | بدون محدودیت اضافی |
مثال
ورودی نمونه ۱
خروجی نمونه ۱
ورودی نمونه ۲
خروجی نمونه ۲
ارسال پاسخ برای این سؤال