PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
There are two boxes, having X and Y stones, respectively.
You want the absolute difference between the number of stones in the boxes to equal K.
In one move, you can transfer a single stone from one box to another.
Find the minimum possible number of moves needed to achieve your goal, or decide that it’s impossible no matter what.
EXPLANATION:
Let d = |X-Y| be the difference between the stone counts. We want to make this equal K.
Note that in one move, we either increase X by 1 and decrease Y by 1, or vice versa.
This means d will change by either +2 or -2.
In particular, the parity of d won’t change: i.e. if it’s initially even it cannot become odd and vice versa.
So, if d and K don’t have the same parity, it’s impossible to achieve our goal.
Now, suppose d and K have the same parity.
We saw d can change by two at a time. So, the number of changes needed equals \frac{|d-K|}{2}.
However, there is one edge case: the total number of stones doesn’t change, and we can’t have negative stones; so the maximum allowed difference is X+Y (when one of the boxes is empty).
So, if K \gt X+Y it’s again impossible to achieve our goal; otherwise the answer is \frac{|d-K|}{2}.
TIME COMPLEXITY:
\mathcal{O}(1) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
x, y, k = map(int, input().split())
dif = abs(x-y)
if (dif - k) % 2 == 0 and k <= x+y:
print(abs(dif - k) // 2)
else:
print(-1)