#B3821. Minimum and Maximum Unmarked Neighbors

    ID: 11478 Type: Default 1000ms 256MiB

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