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$.

Test Set 1 (4점)

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

Test Set 2 (10점)

• 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\}$.