#B3821. Minimum and Maximum Unmarked Neighbors
Minimum and Maximum Unmarked Neighbors
Minimum and Maximum Unmarked Neighbors
Given n elements labeled from 1 to n, exactly k of them will be marked. Two elements are considered adjacent if their labels differ by 1. An unmarked element is counted if at least one of its adjacent elements is marked. Your task is to determine the minimum and maximum possible numbers of such unmarked elements.
Explanation:
- If k = 0 or k = n, no unmarked element can have a marked neighbor, so the answer is 0 for both cases.
- Otherwise, to minimize the count, you can cluster all marked elements together at one end, which makes only one unmarked neighbor adjacent to the cluster; hence the minimum is 1.
- For the maximum, if you spread out the marked elements so that none of their adjacent unmarked cells overlap, each marked element (when placed away from the boundaries) can contribute 2 unmarked neighbors. Thus, the maximum number is given by \(\min(n - k, 2k)\).
Given these observations, output two integers: the minimum and maximum possible counts.
inputFormat
The input consists of a single line containing two integers n and k (0 ≤ k ≤ n) separated by a space.
outputFormat
Output two integers separated by a space: the minimum and the maximum number of unmarked elements (which have at least one marked adjacent element).
sample
5 2
1 3