P4637 [SHOI2011] 扫雷机器人

扫雷是陆军战场上一项重要的而危险的任务。为此， AL 军工厂专门研制了一种扫雷机器人。这种机器人是专门针对直线形雷阵设计的。所谓直线形雷阵，就是所有的地雷都埋在同一条直线上。例如图中黑点表示的雷阵就是直线形雷阵。  AL 军工厂生产的扫雷机器人的排雷方法只有一种，那就是安全引爆。每次，机器人在所有探测到的地雷中选择一颗引爆。被引爆的地雷会接连引爆不超过他的爆炸威力范围的其它地雷，这些被间接引爆的地雷还能引起进一步的连锁爆炸。例如图中，用一个圆的半径表示地雷的爆炸威力。如果引爆 $2$ 号雷， $1$ 、 $2$ 号雷都会爆炸；如果引爆 $3$ 号雷， $4$ 颗地雷全都会爆炸；而如果引爆 $4$ 号雷，那就只有它一颗爆炸。 虽然是机器人，但引爆也是危险的。所以，扫雷机器人的订购人希望机器人能在实战中采取引爆次数尽可能少的炸毁所有地雷的排雷方案。于是 AL 军工厂想就此方面对机器人进行测试。为了评估机器人的表现， AL 军工厂打算事先计算出：在一个直线形雷阵（即输入的雷阵）中，如果随机进行引爆，完成排雷工作所需要引爆次数的期望；并将这个值与机器人的实际排雷方案相比较，来评估他的表现。 所谓“随机进行引爆”是指，每次在所有没有被引爆的地雷中等概率的随机选择一个进行引爆。当这一次引爆引发的连环爆炸结束后，如果还有地雷没有被引爆，则重复上面的操作，直到所有地雷都被引爆为止。

无

无

**提示** 本题的试题目录下有 $10$ 个额外的输入样例文件 ``robot20111.in~robot201110.in`` ，以及它们对应的输出样例文件 ``robot20111.out~robot201110.out`` 。这些数据符合本题中关于数据规模的全部约定，但它们不是最终的测试数据。 **[下载地址](https://pan.baidu.com/s/1Q5X52FMH38UYvmrEsVsEkA)**，密码：ypbv。 **评分方式** 在每个测试点，如果您的输出是 $YourAns$ ，而标准答案是 $StdAns$ ，那么： - 当 $ |YourAns-StdAns| \le 0.0001$ 时，该测试点得 $10$ 分。 - 当 $0.01 \ge |YourAns-StdAns| > 0.0001$ 时，该测试点得 $6$ 分。 - 当 $0.5 \ge |YourAns-StdAns| > 0.01$ 时，该测试点得 $2$ 分。 - 否则得 $0$ 分。 **数据范围** 测试点 $1$：$n \le 20$。 测试点 $2$：$n \le 200$ ，且任意方案都保证引爆次数不超过 $20$。 测试点 $3$：$n \le 200$。 测试点 $4 \sim 5$：$n \le 4000$ ，且任意方案都保证引爆次数不超过 $20$。 测试点 $6 \sim 10$：$n \le 4000$。