FrogJumps | Topcoder Archive

Problem Statement

There are two frogs sitting on a two-dimensional plane. One frog starts at the coordinates (x1, y1), the other starts at coordinates (x2, y2).

Whenever the first frog jumps, it jumps in such a way that each of its coordinates either remains unchanged or it changes by exactly k1. For example, if the first frog has k1 = 4 and sits at (0, 0), it has nine options how to jump. It can jump to any of these coordinates: (-4, -4), (-4, 0), (-4, 4), (0, -4), (0, 0), (0, 4), (4, -4), (4, 0), or (4, 4).

The second frog moves in the same way, but each of its jumps can change each of its coordinates by k2.

If the frogs can eventually meet at the same coordinates, return 1. Otherwise, return 0.

Definition

Class:: FrogJumps
Method:: canMeet
Parameters:: long, long, long, long, long, long
Returns:: int
Method signature:: int canMeet(long x1, long y1, long x2, long y2, long k1, long k2)
(be sure your method is public)

Notes

Each frog may make arbitrarily many jumps, including zero.
The frogs may make their jumps in any order they want.
The frogs may meet anywhere on the plane, including points with coordinates that are not between -10^18 and 10^18.

Constraints

Each of x1, y1, x2, and y2 will be between -10^18 and 10^18, inclusive.
Each of k1 and k2 will be between 1 and 10^18, inclusive.

Examples

```
10
```
```
10
```
```
18
```
```
13
```
```
3
```
```
4
```
```
Returns: 1
```
These two frogs can meet. For example, they can do it as follows: The first frog jumps from (10, 10) to (10, 13). The second frog jumps from (18, 13) to (14, 13). The second frog jumps from (14, 13) to (10, 13) and the two frogs meet.
```
10
```
```
10
```
```
21
```
```
17
```
```
3
```
```
4
```
```
Returns: 1
```
These two frogs can meet as well. Here's one reasonably short solution: The second frog jumps from (21, 17) to (21, 13). The second frog jumps from (21, 13) to (17, 13). The first frog jumps from (10, 10) to (13, 13). The second frog jumps from (17, 13) to (13, 13) and the two frogs meet.
```
10
```
```
10
```
```
21
```
```
13
```
```
10
```
```
10
```
```
Returns: 0
```
Whatever these two frogs do, they will never meet.

987654321987654321

987654321987654321

-123456789123456789

-987654321987654321

Returns: 1

Sometimes meeting may require a lot of jumps.

```
4
```
```
7
```
```
4
```
```
7
```
```
4
```
```
7
```
```
Returns: 1
```
No need to jump, these frogs are already in the same location.

10000000000000

100000000000000

1000000000000000

10000000000000000

100000000000000000

1000000000000000000

Returns: 0

Watch out for integer overflow.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.