FrogJumps
TCO19 SRM 760 · 2019-06-11 · by teja349
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.
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.
62705787029513 75803119209837 10058974523551 -50833621516003 9148219562 4976026881 Returns: 1
-28485481343944 24032406127463 -38683814723473 80760513467903 26391175853245 11170711112067 Returns: 1
92921706117938 41922519973499 41453679550279 -24910492903878 1549833217 8680864001 Returns: 1
56167538056368 67145852902862 -9889792820035 -33952032152033 6395854090 6051007489 Returns: 1
99223879608845 13296200504108 39762202999170 -67948537683587 5145281793 1654646410 Returns: 1
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 1 2 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.
Submissions are judged against all 89 archived test cases, of which 11 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class FrogJumps with a public method int canMeet(long long x1, long long y1, long long x2, long long y2, long long k1, long long k2) · 89 test cases · 2 s / 256 MB per case