Module: phương pháp quét


Problem

1 /4


Bảo hiểm tối thiểu

Theory Click to read/hide

Problem

Một tập hợp các đoạn nhất định có tọa độ nguyên của các đầu \([L_i, R_i]\) được cho trên một dòng. Trong số tập hợp đã cho, hãy chọn một tập hợp con gồm các phân đoạn bao gồm hoàn toàn phân đoạn \([0, M]\), (M — số tự nhiên) chứa số lượng phân đoạn nhỏ nhất.
 
Đầu vào
Dòng đầu tiên chứa hằng số M (\(1<=M<=5000\)). Mỗi dòng tiếp theo chứa một cặp số Li và Ri (\(|L_i|,|R_i| < 50000\)), chỉ định tọa độ của các đầu bên trái và bên phải của các đoạn. Danh sách kết thúc với một cặp số không. Tổng số phân khúc không vượt quá 100.000.
 
Đầu ra
Trong dòng đầu tiên của tệp đầu ra, in số lượng phân đoạn tối thiểu cần thiết để bao gồm phân đoạn \([0; M]\). Tiếp theo, xuất ra danh sách tập hợp con bao phủ, được sắp xếp theo thứ tự tăng dần theo tọa độ của các đầu bên trái của các đoạn. Danh sách các phân đoạn được xuất ra ở định dạng giống như trong đầu vào. Hai số 0 ở cuối là không bắt buộc. Nếu phân đoạn \([0; M]\) là tập hợp ban đầu của các phân đoạn \([L_i, R_i] \) là không thể, một cụm từ duy nhất “Không có giải pháp” sẽ được xuất ra.

 

Ví dụ
<đầu>

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!

# Đầu vào Đầu ra
1
1
-1 0
-5 -3
2 5
0 0
 Không có giải pháp
2
1
-1 0
0 1
0 0
 1
0 1