1
$\begingroup$

There are two kangaroos on an x-axis ready to jump in the positive direction (i.e, toward positive infinity). The first kangaroo starts at location $x_1$ and moves at a rate of $v_1$ meters per jump. The second kangaroo starts at location $x_2$ and moves at a rate of $v_2$ meters per jump. Given the starting locations and movement rates for each kangaroo, can you determine if they'll ever land at the same location at the same time?

Input Format

A single line of four space-separated integers denoting the respective values of $x_1$, $v_1$, $x_2$, and $v_2$.

Constraints

  1. $0 \le x_1 < x_2$
  2. $1 \le v_1$
  3. $1 \le v_2$

Output Format

Print YES if they can land on the same location at the same time; otherwise, print NO.

Note: The two kangaroos must land at the same location after making the same number of jumps.


Sample Input 0

0 3 4 2

Sample Output 0

YES

Explanation 0

The two kangaroos jump through the following sequence of locations:

  1. 0 3 6 9 12
  2. 4 6 8 10 12

Thus, the kangaroos meet after 4 jumps and we print YES.


Sample Input 1

0 2 5 3

Sample Output 1

NO

Explanation 1

The second kangaroo has a starting location that is ahead (further to the right) of the first kangaroo's starting location (i.e., $x_2 > x_1$). Because the second kangaroo moves at a faster rate (meaning $v_2 > v_1$) and is already ahead of the first kangaroo, the first kangaroo will never be able to catch up. Thus, we print NO.


Note: I searched for the answer and got this puzzle here but without answer :( so had to ask.

$\endgroup$
  • $\begingroup$ What is the source of this puzzle? $\endgroup$ – Dr Xorile Dec 13 '18 at 15:09
6
$\begingroup$

They'll meet if and only if

$v_1 > v_2$ (so that kangaroo 1 catches up)

and

$v_1 - v_2 | x_2 - x_1$, here | means 'is a divisor of'.

Why?

After $n \in \Bbb{N}$ jumps, kangaroo 1 will be at position $x_1 + n v_1$ and kangaroo 2 at $x_2 + n v_2$. Now, if $$x_1 + n v_1 = x_2 + n v_2$$ $$n v_1 - n v_2 = x_2 - x_1$$ $$n (v_1 - v_2) = x_2 - x_1$$ $$n = \frac{x_2 - x_1}{v_1 - v_2}$$ This fraction is an integer if and only if $v_1 - v_2$ divides $x_2 - x_1$.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.