求助!赏一关
  • 板块学术版
  • 楼主yu_666
  • 当前回复4
  • 已保存回复4
  • 发布时间2023/7/10 13:01
  • 上次更新2023/11/3 10:47:02
查看原帖
求助!赏一关
317399
yu_666楼主2023/7/10 13:01

Description 占星教为了在各门派之争中立于不败之地,下设许多“堂”来研究各种新奇的战术,本 周,他们的课题就是:如何将一排排满的Spider Mine(蜘蛛雷)封锁一个路口。

由于SC 中不同的蜘蛛雷所控制的范围不同,为了简化问题,我们将告诉你现在有多少 个可选位置来埋雷,以及每个位置上雷的控制范围。我们希望知道这些雷是否可以封锁路口, 以及如果可以最少取出其中的多少颗就可以封锁路口了。(当然要假设别人没有反隐的东东 咯~~)。

Format
Input
输入数据共N+1 行

第1 行为两个正整数N,M,分别表示有多少颗可选的雷,以及路口的长度(表示[1,M]的闭区间)

第 2-n+1 行每行两个正整数,表示每个蜘蛛雷可控制的范围。

Output
输出数据共一行

如果蜘蛛雷可以控制整个路口,那么输出最少需要的雷数。

如果不能控制,那么输出“Impossible”。

Samples
输入数据 1
3 10
1 5 3 6 6 10
输出数据 1
2
输入数据 2
3 10
1 2 3 6 8 10
输出数据 2
Impossible
Limitation
对于 30%的数据,1<=N<=100,1<=M<=300;

对于 70%的数据,1<=N<=10000,1<=M<=3000000;

对于 100%的数据,1<=N<=1000000,1<=M<=232-1;

2023/7/10 13:01
加载中...