[UVA] 11335 - Discrete Pursuit
C: Discrete Pursuit
| C: Discrete Pursuit |
Robocops Inc. is a toy manufacturer company that develops a robot game in which a cop tries to catch a thief in a field that is simulated with a rectangular grid whose coordinates are denoted by pairs of integers. The resulting pursuit occurs in a discrete time scale: time is modeled with non-negative integers 0, 1, 2,... .
An object on the grid has a speed that determines how the object moves during the simulation. A speed is modeled with a pair of integers. The first one is the horizontal speed and the second one is the vertical speed. Additionally, horizontal and vertical speeds may vary in one unit (each one) to simulate slowing or accelerating.
More exactly: if at time k
the object is at location (x, y)
with speed (u, v)
, then, at time k + 1
, the object may appear at location
(x', y') = (x + u + 
, y + v + 
)
, for some
, 
{-1, 0, 1}
. The speed at time k + 1
is
(x' - x, y' - y)
. For an object that moves with constant speed the values
and
are always 0
.
At time 0 , the cop is located at the origin of the grid, and the thief is at coordinates (a, 0) . The thief is moving with a constant speed; on the other hand, the cop starts still, but may vary his speed according to the given rules. Clearly, the cop catches the thief at time k if at this time the positions of both coincide.
Your task is to develop a program to control the cop in order to catch the thief in an efficient way. Your algorithm should determine the minimum time in which the cop may catch the thief.
Input
The problem input consists of several cases, each one defined by a line
with three integer values, separated by blanks, that stand for the
initial position a
of the thief in the X
-axis (
0
a1000
), the horizontal speed u
(
0u10
) and the vertical speed v
(
0v10
) at which he moves. The end of the input corresponds to the end of the input file.
Output
Output texts for each input case preserve the order in the input file.
For an input case, the output should be an integer that is the minimum time at which the cop may catch the thief.
Sample Input
1 1 1 3 1 0
Sample Output
2 3
警察從靜止速度開始加速追人，而歹徒則是以恆定速度移動。
因此考慮一下，兩個方位可以分開討論。
警察一直以加速度 1 增加即可，超過歹徒時，再考慮哪個時間點不用加速。
因此就可以知道時間花費，分開討論後取最大值。
#include <stdio.h>
#include <algorithm>
using namespace std;
int main() {
int a, u, v;
while(scanf("%d %d %d", &a, &u, &v) == 3) {
if(a == 0) {
puts("0");
continue;
}
long long x = a, y = v, cx = 0, cy = 1;
long long tu = 1, tv = 1;
int ret, xtime = 0, ytime = 1;
//x
while(cx < x) {
xtime++;
x += u, cx += xtime;
}
//y
while(cy < y) {
ytime++;
y += v, cy += ytime;
}
ret = max(xtime, ytime);
printf("%d\n", ret);
}
return 0;
}