29786번 - Spacious Sets 서브태스크다국어

Ada and John are best friends. Since they are getting bored, Ada asks John to solve a puzzle for her.

A set $S$ is considered spacious if the absolute difference between each pair of distinct elements of $S$ is at least $\mathbf{K}$, that is, $|x - y| \ge \mathbf{K}$ for all $x, y \in S$, with $x \ne y$.

Ada has a list of distinct integers $\mathbf{A}$ of size $\mathbf{N}$, and an integer $\mathbf{K}$. For each $\mathbf{A_i}$, she asks John to find the maximum size of a set $S_i$ made of elements from $\mathbf{A}$, such that $S_i$ contains $\mathbf{A_i}$ and is spacious.

Note: The sets $S_i$ do not need to be made of consecutive elements from the list.

The first line of the input gives the number of test cases, $\mathbf{T}$. $\mathbf{T}$ test cases follow.

The first line of each test case contains two integers $\mathbf{N}$ and $\mathbf{K}$.

The next line contains $\mathbf{N}$ integers $\mathbf{A_1} \mathbf{A_2} \dots \mathbf{A_N}$.

For each test case, output one line containing Case #x: y1 y2 ... yN$, where $x$ is the test case number (starting from 1) and $y_i$ is the maximum size of a spacious set of elements from $\mathbf{A}$ that contains $\mathbf{A_i}$.

• $1 \le \mathbf{T} \le 100$.
• $-10^9 \le \mathbf{A_i} \le 10^9$, for all $i$.
• $\mathbf{A_i} \ne \mathbf{A_j}$, for all $i \ne j$.

• $1 \le \mathbf{N} \le 10$.
• $1 \le \mathbf{K} \le 100$.

• $1 \le \mathbf{K} \le 10^9$.

For at most 15 cases:

• $1 \le \mathbf{N} \le 10^5$.

For the remaining cases:

• $1 \le \mathbf{N} \le 10^3$.

In Sample Case #1, a spacious set cannot contain $1$ and $2$, nor it can contain $2$ and $3$. That implies that $S_2 = \{2\}$ and using $S_1 = S_3 = \{1,3\}$ makes them of maximum size.

In Sample Case #2, possible sets of maximum size are:

• $S_1 = S_2 = S_3 = S_4 = \{2,7,11,19\}$,
• $S_5 = \{11,19,5\}$, and
• $S_6 = \{7,11,19,3\}$.