萨鲁曼的大军
测试数据来自 system/1794
作业已超过截止时间,您无法递交本题目。
时间限制:1秒 内存限制:256M
【题目描述】
萨鲁曼的大军正行进在一条笔直的道路上,由于是在夜晚行军,路上的石头严重地影响了行军速度。于是萨鲁曼决定预先在道路上安装一些路灯,以便士兵们能清楚地看到所有石头。
萨鲁曼给出 块石头的位置 ,现在需要在这些位置中选择若干个位置设置路灯。每盏路灯的照亮范围为 ,即若你在 处设置了一盏路灯,则在 的范围内都会被照亮。
现在请你计算最少设置多少盏路灯,就能把所有石头照亮。
【输入格式】
含多组测试数据,每组数据占两行:第一行为 和 ,第二行包含 个整数,表示 。输入以两个 -1 结束。
【输出格式】
每组数据输出一行一个整数,表示最少的路灯数量。
【输入输出样例】
Input
Output
【数据限制】
对于 的数据,,。
【来源】
Mr.he