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$.


  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


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


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.

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

They'll meet if and only if

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


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


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$.


Your Answer

