#arc106c. [arc106_c]Solutions
[arc106_c]Solutions
问题陈述
当满足 并且 时,两个区间 \[L_1:R_1\] 和 \[L_2:R_2\] 被称为 相交。
考虑以下问题 :
输入: 个区间 \[L_1: R_1\], \cdots, \[L_N:R_N\] 两两不同。 输出:最多可以选择的区间数量,使得它们之间没有相交。
高桥实现了一个程序,其工作原理如下:
按照 的递增顺序对给定的区间进行排序,结果为 $\[L_{p_1}:R_{p_1}\], \[L_{p_2}:R_{p_2}\], \cdots , \[L_{p_N}:R_{p_N}\]$。 对于每个 ,执行以下操作: 如果 \[L_{p_i}:R_{p_i}\] 没有与迄今选择的任何区间相交,则选择它。 打印选择的区间数量。
另一方面,青木实现了一个程序,其工作原理如下:
按照 的递增顺序对给定的区间进行排序,结果为 $\[L_{p_1}:R_{p_1}\], \[L_{p_2}:R_{p_2}\], \cdots , \[L_{p_N}:R_{p_N}\]$。 对于每个 ,执行以下操作: 如果 \[L_{p_i}:R_{p_i}\] 没有与迄今选择的任何区间相交,则选择它。 打印选择的区间数量。
给定整数 和 。构造一个问题 的输入,包含 个区间,满足以下条件:
约束条件
- 输入中的所有值都是整数。
输入
输入数据以以下格式从标准输入给出:
输出
如果没有满足条件的 个区间集合,则打印 -1
。
否则,按照以下方式打印 行:
这里,\[L_1:R_1\], \cdots, \[L_N:R_N\] 必须满足以下条件:
- ()
- ()
- 都是整数
如果有多个答案,任何一个都可接受。
请确保在输出末尾打印一个换行符。
示例输入 1
5 1
示例输出 1
1 10
8 12
13 20
11 14
2 4
我们将这五个区间分别称为 Segment , Segment , , Segment 。
高桥的程序的工作过程如下:
按照 Segment , Segment , Segment , Segment , Segment 的顺序重新排列区间。 选择 Segment 。 跳过 Segment (因为它与 Segment 相交)。 选择 Segment 。 跳过 Segment (因为它与 Segment 相交)。 选择 Segment 。
因此,高桥的程序将打印 。
青木的程序的工作过程如下:
按照 Segment , Segment , Segment , Segment , Segment 的顺序重新排列区间。 选择 Segment 。 跳过 Segment (因为它与 Segment 相交)。 跳过 Segment (因为它与 Segment 相交)。 选择 Segment 。 跳过 Segment (因为它与 Segment 相交)。
因此,青木的程序将打印 。
在这里,我们有 (与 相等),因此这五个区间满足条件。
示例输入 2
10 -10
示例输出 2
-1