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\)), 세그먼트의 왼쪽 및 오른쪽 끝 좌표를 지정합니다. 목록은 한 쌍의 0으로 끝납니다. 총 세그먼트 수는 100,000개를 초과하지 않습니다.
 
출력
출력 파일의 첫 번째 줄에 세그먼트 \([0; M]\)를 포함하는 데 필요한 최소 세그먼트 수를 인쇄합니다. 다음으로 세그먼트의 왼쪽 끝 좌표를 기준으로 오름차순으로 정렬된 커버링 하위 집합의 목록을 출력합니다. 세그먼트 목록은 입력과 동일한 형식으로 출력됩니다. 후행 2개의 0은 필요하지 않습니다. 세그먼트 \([0; M]\)가 원래 세그먼트 세트인 경우 \([L_i, R_i] \)< /span>이 불가능하면 "솔루션 없음"이라는 단일 문구가 출력되어야 합니다.

 

예
<헤드> <일># <몸>

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!

입력 출력
1 <사업부>1 <사업부>-1 0 <사업부>-5 -3
2 5
<사업부>0 0 		해결책 없음
2 <사업부>1 <사업부>-1 0 <사업부>0 1 <사업부>0 0 1
0 1