PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
Given N, M, K, find the minimum difference between K and some perimeter of a rectangle with integer sides; whose length is in [1, N] and width is in [1, M].
EXPLANATION:
The limits are small enough for a solution in \mathcal{O}(N\cdot M) to work: try every pair of length and width, compute the perimeter, and take its difference with K.
It’s also possible to solve the problem in constant time by analyzing the setup a bit.
The maximum possible perimeter is 2\cdot (N + M).
If this value is \leq K, then the best difference we can get is simply K - 2\cdot (N + M).
Otherwise, observe that any even number between 4 and 2\cdot (N + M) can be obtained as the perimeter: this can be done by starting with l = w = 1, and then repeatedly increasing the length or width by 1 (as long as they don’t cross N and M, respectively) - which increases the perimeter by exactly 2.
This will give us every even number between 4 and 2\cdot (N + M).
So,
- If K \gt 2\cdot (N + M), the answer is K - 2\cdot (N + M).
- If 1 \leq K \leq 3, the answer is 4 - K, since the smallest perimeter obtainable is 4.
- If 4 \leq K \leq 2\cdot (N + M), the answer is (K\bmod 2) - that is, 0 if K is even and 1 if K is odd.
This is because only the even numbers in that range can be reached; so any odd number will have a difference of 1.
TIME COMPLEXITY:
\mathcal{O}(1) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n, m, k = map(int, input().split())
if k >= 2 * (n + m): print(k - 2*(n+m))
elif k <= 4: print(4 - k)
else: print(k%2)