PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: pols_agyi_pols
Tester: kingmessi
Editorialist: iceknight1093
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
You’re given X and Y.
Let S_{even} be the sum of all even multiples of X in the range [X, Y], and S_{odd} be the sum of all odd multiples of X in this range.
Chef will be happy only if S_{even} \ge S_{odd}.
Decide if Chef will be happy, given X and Y.
EXPLANATION:
Since X and Y are small (both being \le 100), this problem can be solved by just brute-forcing it.
That is, iterate over every integer Z in the range [X, Y]; and:
- If Z is not a multiple of X, ignore it.
- If Z is an even multiple of X, add Z to S_{even}.
- If Z is an odd multiple of X, add Z to S_{odd}.
Finally, check if S_{even} \ge S_{odd} or not.
It’s also possible to solve the problem mathematically.
The multiples of in the range [X, Y] will be
X, 2X, 3X, \ldots, kX for some integer k \ge 1.
If X is even, then all multiples of X will also be even; so S_{odd} will always equal 0.
Thus, S_{even} \ge S_{odd} will always be true.
If X is odd, then the multiples of X will alternate between odd and even.
It can then be seen that:
- If k is odd, then S_{odd} \gt S_{even}.
(Recall that k is the largest integer such that k \le Y). - If k is even, then S_{odd} \lt S_{even}.
k can be computed mathematically by taking \frac{Y}{X} and rounding it down to the nearest integer, so the problem is solved in constant time.
TIME COMPLEXITY:
\mathcal{O}(Y) or \mathcal{O}(1) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
x, y = map(int, input().split())
k = y//x
if x%2 == 0 or k%2 == 0: print('Yes')
else: print('No')