Special Robot的程序的编写思路

Problem Description
Bob invented a special kind of robot controlled by a remote controller. The interesting thing is that the robot can only move in a 2-dimentional plane which is vertical to the ground. Now we assume the vertical plane can be shown in Figure 1.

Now Bob wants to conduct a performance for his robot. The situation can be described as follows: n balloons stay still on the ground; all of these balloons have an initial position whose Y-coordinates are 0.
Each balloon will move up at certain time. The initial position of the robot is at (0, 0) and if the robot is at position (x, y) at time t, then it can only move to position (x, y-1) or position (x+1, y+1) in a unit time (the robot con not stay still at a position). Its task is to collect as more balloons as possible when it gets to the destination (K,0).

When the robot is moving on the plane, balloons are continuously rising on its path from the ground. Each balloon can reach a unit height in a unit time.
When the robot meets a balloon, it collects the balloon. The situation can be described as the following three examples which are shown in Figure 2:

Example 1: At time t, the robot is at position (x, y), and a balloon is at position (x, y-2). The robot moves down and the balloon moves up; then at time t+1, the robot and the balloon meet at position (x, y-1), so the balloon can be collected by the robot ( which is shown in Figure 2(a)).

Example 2: At time t, there is a balloon at position (x, y-1) and the robot stands at position (x, y). Because the balloon always moves up and the robot can move down, so the robot can collect this balloon because they will meet at some point between position (x, y-1) and (x, y) during their movement (which is shown in Figure 2(b)).

Example 3: At time t, a balloon is at position (x+1, y) and the robot is at position (x, y). Because the robot can arrive at position (x+1, y+1) while the balloon can move up to the same position, the robot could collect the balloon at time t+1 (which is shown in Figure 2(c)).

Maybe it is too easy a problem to control one robot, so Bob intends to control two robots simultaneously.
You need to help him to calculate the maximum balloons these two robots can collect when they get to the destination.

It is possible that the two robots get to the same position at the same time. Note that one balloon could not be collected by two robots and the balloons staying on the ground could not be collected either.

Robot should not move to the underground (y < 0).

Input
The input contains several cases. For each case, the first line gives the value of n (0 ≤ n ≤ 10,000) and K (1 ≤ K ≤ 100) followed by n lines in which each contains two integers x (1 ≤ x ≤ K) and t (0 ≤ t ≤ 1000).

The first integer indicates the position of a balloon and the other indicates the beginning time for it to rise. In the value of n and K, n is the number of balloons and K is the x-coordinate of the destination. The input is ended by two zeros.

Output
For each case, output the maximum balloons the two robots can collect.

Sample Input
3 2
1 1
1 1
1 2
7 4
2 0
2 3
3 4
3 0
3 2
4 0
1 1
0 0

Sample Output
2
6

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问

相似问题

1
运动规划的伪代码程序看不懂程序的逻辑
1
robot framework如何通过配置导入不同的Resources?
0
一个机器人在棋盘上的运动路线的问题,如何利用C语言的程序技术实现?
0
机器人的比赛的一个算法问题,用到排列数,怎么用C语言的程序的编写来实现的
0
输出序列开头的元素的做法,利用C语言的程序的射击的语言的方式
0
robot framework因存在滚动栏导致元素不可见
0
一个寻宝图寻找问题的算法模拟的实现,怎么采用C语言程序编写的思维用程序解决的
0
机器人的角度旋转和移动的问题,怎么采用的C语言的程序代码编写的技术的方式实现呢?
0
机器人四个方向的移动,求遍历算法的问题怎么用C语言程序编写的思想实现的
1
Matlab里面装入robotics toolbox之后为什么在命令行界面输入程序还是显示error using==>link.link?
0
在无限的二维网格上控制机器人的命令的算法,用C语言的程序设计的思想和原理如何来实现的
1
求教如何用C语言改编这个任务分配问题的代码?
0
Caves方块的计算搜索,用C语言程序实现的过程
0
机器人编程算法在C语言的实践、运用怎么编写?
0
机器人行走的距离计算问题,怎么采用C语言实现的
1
Robot Studio使用 PC sdk 实现局域网与另外一台电脑中的虚拟控制器通讯
0
C语言的程序题目,Ghosts In The Robots
0
Crashing Robots怎么实现的
1
运行此代码一直报错OSError: [WinError -2147221003] 找不到应用程序: 'QR.png' 求大佬帮忙看下