PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: Utkarsh Gupta
Tester: Hriday
Editorialist: Nishank Suresh
DIFFICULTY:
1069
PREREQUISITES:
Basic math
PROBLEM:
You are given A, B, and X. In one move, you can increase either A or B by X and reduce the other by X. Is it possible to make A equal to B?
EXPLANATION:
It is possible to make A and B equal if and only if 2X divides A-B.
Proof
Note that making any move does not change the value of (A-B) modulo 2X, since:
- (A+X) - (B-X) \equiv A-B + 2X \equiv A-B \pmod {2X}
- (A-X) - (B+X) \equiv A-B - 2X \equiv A-B \pmod {2X}
If A = B eventually, then of course A-B must be 0 modulo 2X, i.e, 2X divides A-B.
Also, if 2X divides A-B, then A and B can be made equal as follows:
- If A = B, nothing needs to be done
- If A \gt B, add X to B and subtract X from A
- If A \lt B, add X to A and subtract X from B
In either case, A and B are brought closer together by 2X. Since their difference is a multiple of 2X, eventually they will become equal.
TIME COMPLEXITY
\mathcal{O}(1) per test case.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
a, b, x = map(int, input().split())
print('Yes' if (a-b)%(2*x) == 0 else 'No')