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\))、セグメントの左端と右端の座標を指定します。リストはゼロのペアで終わります。セグメントの総数は 100,000 を超えません。
 
出力
出力ファイルの最初の行に、セグメント \([0; M]\) をカバーするために必要なセグメントの最小数を出力します。次に、セグメントの左端の座標によって昇順にソートされた、カバーするサブセットのリストを出力します。セグメントのリストは、入力と同じ形式で出力されます。末尾の 2 つのゼロは必要ありません。セグメント\([0; M]\) が元のセグメントのセットである場合、\([L_i, R_i] \)< /span> は不可能です。単一のフレーズ「No solution」が出力されるはずです。

 

例
<頭> <本体>

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