Module: روش اسکن لاین


Problem

1 /4


حداقل پوشش

Theory Click to read/hide

Problem

مجموعه مشخصی از پاره‌ها با مختصات عدد صحیح انتهایی \([L_i, R_i]\) روی یک خط داده می‌شود. از میان مجموعه داده شده، زیرمجموعه ای از بخش ها را انتخاب کنید که به طور کامل بخش \([0, M]\)، (M — عدد طبیعی) حاوی کوچکترین تعداد بخش است.
 
ورودی
خط اول حاوی ثابت M است (\(1<=M<=5000\)). هر خط بعدی شامل یک جفت اعداد Li و Ri است (\(|L_i|,|R_i| < 50000\))، که مختصات انتهای چپ و راست بخش ها را مشخص می کند. لیست با یک جفت صفر به پایان می رسد. تعداد کل بخش ها از 100000 تجاوز نمی کند.
 
خروجی
در خط اول فایل خروجی حداقل تعداد بخش های مورد نیاز برای پوشش بخش \([0; M]\) را چاپ کنید. در مرحله بعد، فهرستی از زیرمجموعه پوشش دهنده را که به ترتیب صعودی بر اساس مختصات انتهای سمت چپ بخش ها مرتب شده اند، تهیه کنید. لیست بخش ها با همان فرمت ورودی خروجی می شود. دو صفر انتهایی لازم نیست. اگر بخش \([0; M]\) مجموعه اصلی بخش‌ها باشد \([L_i, R_i] \)< /span> ممکن نیست، یک عبارت “بدون راه حل” باید خروجی شود.

 

نمونه‌ها
<سر> <بدن>
# ورودی خروجی
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!