PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: Jeevan Jyot Singh
Tester: Hriday
Editorialist: Nishank Suresh
DIFFICULTY:
1123
PREREQUISITES:
Basic math
PROBLEM:
Given a stick of length L, you want to break it into exactly K positive integer-sized parts A_1, A_2, \ldots, A_K
What is the minimum possible value of \sum_{i=1}^{K-1} |A_i - A_{i+1}|?
EXPLANATION:
The answer is 0 if K divides L and 1 otherwise.
Proof
If K divides L, obviously we can make K parts of size \frac{L}{K} and the given expression evaluates to zero.
Otherwise, it’s always possible to obtain a difference of 1. Here’s a construction:
Let x = \left\lfloor \frac{L}{K}\right\rfloor and y = \left\lceil \frac{L}{K}\right\rceil.
Also, let r denote the remainder when L is divided by K. Since K doesn’t divide L, 0 \lt r \lt K.
Now, set A_1 = A_2 = \ldots = A_r = y, and everything else equal to x.
It’s easy to see that the sum of all A_i is L. Further, almost every pair of adjacent terms are equal: only A_r and A_{r+1} are not equal, and they differ by |x-y| = 1, as required.
TIME COMPLEXITY
\mathcal{O}(1) per test case.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
n, k = map(int, input().split())
print(1 if n%k > 0 else 0)