JUMPAB - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

You’re at position 0 of the number line.
You must make exactly N jumps: each time, move either A or B units to the right.
Can you reach point M?

EXPLANATION:

We must make exactly N jumps, each being either A or B.
So, if x of the jumps are of A, the remaining N-x must be of B.

Let’s analyze what happens for a fixed x.
The total distance covered will equal A\cdot x + B\cdot (N-x).
We’d like this to equal M.
That tells us:

\begin{aligned} A\cdot x + B\cdot (N - x) &= M \\ A\cdot x - B\cdot x &= M - N\cdot B \\ x &= \frac{(M - N\cdot B)}{A - B} \end{aligned}

So, there is in fact a unique candidate for x if we want the total distance to equal M.
This means all we need to do is compute this value of x and check if it’s a valid one, i.e.

  1. x should be an integer.
    This means A - B should divide M - N\cdot B.
  2. x is the number of jumps of length A.
    So, 0 \leq x \leq N must hold.

If both conditions are true, the answer is "Yes", otherwise it’s "No".

TIME COMPLEXITY:

\mathcal{O}(1) per testcase.

CODE:

Editorialist's code (PyPy3) 
# xa + (n-x)b = m
# xa + nb - xb = m
# x*(b - a) = nb - m
for _ in range(int(input())):
    n, m, a, b = map(int, input().split())
    if (n*b - m) % (b - a) == 0: # integer check
        x = (n*b - m) // (b - a)
        if 0 <= x <= n: print('Yes') # bound check
        else: print('No')
    else: print('No')
3 Likes