PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: Sai Panda
Testers: Hriday, Utkarsh Gupta
Editorialist: Nishank Suresh
DIFFICULTY:
1242
PREREQUISITES:
None
PROBLEM:
A normal year contains N days, while a “Mob” year contains N+M days. Every K-th year is a “Mob” year.
Given X, does the (X-1)-th day fall in a “Mob” year?
EXPLANATION:
Let’s look at a consecutive set of K years, starting from the first.
Years 1, 2, \ldots, K-1 are not “Mob” years, while year K is.
In terms of days, this means the first (K-1)\times N days aren’t in a “Mob” year, while days (K-1)\times N + 1 to K \times N + M are in one.
Notice that this already gives us the answer for when 1 \leq X \leq K\times N + M.
What happens when X \gt K\times N + M?
Well, by symmetry we can just ignore the first K\times N + M days!
That is, the answer for X is the same as the answer for X - (K\times N + M).
So, we keep subtracting K\times N + M from X till we reach a point where 1 \leq X \leq K\times N + M, then use the condition we derived above to answer for this X.
However, this is too slow: for example, if K = N = M = 1, then we’d be subtracting 2 from X at each step, which is way too little when X is large.
Instead, notice that the operation we are performing is exactly the modulo operation!
That is, we are essentially computing X\pmod{K\times N + M}.
So, simply compute this quantity, for example using the %
operator in most languages.
Notice that we want the result to be between 1 and K\times N + M, so if the result is zero then set it to K\times N + M.
Finally, use the condition derived above to answer the query. This gives us a solution in \mathcal{O}(1) per test case.
TIME COMPLEXITY
\mathcal{O}(1) per test case.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
n, m, k, x = map(int, input().split())
x -= 1
print('No' if k > 1 and x % (k*n + m) < (k-1)*n else 'Yes')