Module: طريقة Scanline


Problem

1 /4


الحد الأدنى من التغطية

Theory Click to read/hide

Problem

مجموعة معينة من المقاطع ذات الإحداثيات الصحيحة للنهايات \ ([L_i، R_i] \) موجودة على سطر. من بين المجموعة المحددة ، اختر مجموعة فرعية من المقاطع التي تغطي بالكامل المقطع \ ([0، M] \) ، ( M & mdash؛ العدد الطبيعي) يحتوي على أصغر عدد من المقاطع.
& nbsp؛
إدخال
يحتوي السطر الأول على الثابت M ( \ (1 & lt؛ = M & lt؛ = 5000 \) ). يحتوي كل سطر لاحق على زوج من الأرقام L i و R i ( \ (| L_i |، | R_i | & lt؛ 50000 \) ) ، الذي يحدد إحداثيات الطرفين الأيمن والأيسر للقطاعات. تنتهي القائمة بزوج من الأصفار. العدد الإجمالي للقطاعات لا يتجاوز 100000.
& nbsp؛
الإخراج
في السطر الأول من ملف الإخراج ، اطبع الحد الأدنى لعدد المقاطع المطلوبة لتغطية المقطع \ ([0؛ M] \) . بعد ذلك ، أخرج قائمة بمجموعة التغطية الفرعية ، مرتبة بترتيب تصاعدي حسب إحداثيات الأطراف اليسرى للقطاعات. يتم إخراج قائمة المقاطع بنفس التنسيق كما في الإدخال. لا يلزم استخدام الأصفار اللاحقة. إذا كان المقطع & nbsp؛ \ ([0؛ M] \) هو المجموعة الأصلية من المقاطع \ ([L_i، R_i] \) غير ممكن ، يجب إخراج عبارة واحدة & ldquo ؛ لا يوجد حل & rdquo ؛

نبسب ؛

أمثلة <الجسم>
# إدخال الإخراج
1
1
-1 0
-5 -3
2 5
0 0
لا يوجد حل
2
1
-1 0
0 1
0 0
1
0 1

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!