Rendezvous
SRM 137 · 2003-03-06 · by vorthys
Problem Statement
In the game of Rendezvous, two pieces move on a two-dimensional grid. Both pieces are restricted to integer coordinates. The target piece begins at coordinates (x,y), and the seeker piece begins at coordinates (0,0). On every turn the target piece moves dx units horizontally and dy units vertically. Similarly, the seeker piece moves DX units horizontally and DY units vertically on every turn. For example, at the end of the first turn, the target piece is at coordinates (x+dx,y+dy) and the seeker piece is at coordinates (0+DX,0+DY). The values of dx, dy, DX, and DY are limited to integers between -1000 and 1000, inclusive.
You control the movement of the seeker piece. In other words, you choose the values of DX and DY. Your goal is to make the seeker piece rendezvous with the target piece in the minimum number of turns. A rendezvous occurs when both pieces end a turn at the same coordinates.
Create a class Rendezvous with a method interceptVector
that takes
Notes
- Given the input constraints, if the seeker cannot catch the target within 10000 turns, it will never catch the target.
Constraints
- x and y are between -10000 and 10000, inclusive, but are not both 0.
- dx and dy are between -1000 and 1000, inclusive.
500
300
55
33
Returns: { 555, 333 }
Pieces meet at the end of the first turn.
500
300
600
700
Returns: { 850, 850 }
Pieces meet at the end of the second turn.
1
1
1000
1000
Returns: { }
The seeker piece can never catch the target piece.
9519
-1002
857
-534
Returns: { 914, -540 }
-1024
333
15
-186
Returns: { }
Submissions are judged against all 37 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class Rendezvous with a public method vector<int> interceptVector(int x, int y, int dx, int dy) · 37 test cases · 2 s / 256 MB per case