PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
There are N students in a school. X of them want to go on the school trip.
A school bus can only hold K students, so the number of students going on the trip must be a multiple of K.
Find the minimum number of students who need to be convinced to change their minds to satisfy this.
EXPLANATION:
Suppose Y students go on the trip in the end.
Note that Y must be a multiple of K.
Since there are initially X students going on the trip, the number of students who need to be convinced to change their minds is then exactly |X-Y|.
So, an initial solution is to simply iterate through all possible valid choices of Y, i.e. Y = 0, K, 2K, \ldots and compute the minimum possible value of |X-Y|, which will be the answer.
This works in \mathcal{O}(N) time, which is fast enough for the given constraints and already enough to get AC.
It’s possible to further optimize the above solution. Observe that the optimal choice for Y will be the closest multiple of K to X.
That is, let m be the largest integer such that m\cdot K \le X.
Then, either Y = m\cdot K or Y = (m+1)\cdot K will be optimal.
Computing m is easy enough: we simply have m = \text{floor}\left(\frac{X}{K}\right).
Once m is known, check with both Y = m\cdot K and Y = (m+1)\cdot K.
Note that Y = (m+1)\cdot K must be checked only if it’s \le N.
This gives us a solution in constant time.
To further simplify implementation, it can be seen that we don’t even need to explicitly know the value of m.
Instead, observe that (X - m\cdot K) = X \bmod K, i.e. the remainder when X is divided by K.
Similarly, (m+1)\cdot K - X = K - (X\bmod K).
So, knowing X\bmod K alone is enough to solve the problem.
TIME COMPLEXITY:
\mathcal{O}(1) or \mathcal{O}(N) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n, x, k = map(int, input().split())
ans = x % k
if x + k - (x % k) <= n: ans = min(ans, k - x%k)
print(ans)