페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#10455

여유로운 집합 20s 2048MB

문제

에이다(Ada)와 존(John)은 가장 친한 친구이다. 지루해진 에이다는 존에게 퍼즐 하나를 풀어 달라고 부탁한다.

집합 S는, 서로 다른 두 원소의 차의 절댓값이 항상 \mathbf{K} 이상이면 여유롭다(spacious)고 하자. 즉, 모든 x, y \in S에 대해 x \ne y이면 |x - y| \ge \mathbf{K}이다.

에이다는 크기가 \mathbf{N}인 서로 다른 정수들의 목록 \mathbf{A}와 정수 \mathbf{K}를 가지고 있다. 각 \mathbf{A_i}에 대해, 에이다는 존에게 다음을 구해 달라고 한다. 목록 \mathbf{A}의 원소들로 이루어진 집합 S_i 중에서, S_i가 \mathbf{A_i}를 포함하고 또한 여유로운 집합일 때, S_i의 크기의 최댓값을 구하라.

참고: 집합 S_i는 목록에서 연속한 원소들로만 이루어질 필요가 없다.


입력

입력의 첫 줄에는 테스트 케이스 수 \mathbf{T}가 주어진다. \mathbf{T}개의 테스트 케이스가 이어진다.
각 테스트 케이스의 첫 줄에는 정수 두 개 \mathbf{N}, \mathbf{K}가 주어진다.
그 다음 줄에는 \mathbf{N}개의 정수 \mathbf{A_1} \mathbf{A_2} \dots \mathbf{A_N}이 주어진다.


출력

각 테스트 케이스마다 Case #x: y_1 ~ y_2 \dots ~ y_\mathbf{N} 형식의 한 줄을 출력하라. 여기서 x는 (1부터 시작하는) 테스트 케이스 번호이고, y_i는 \mathbf{A_i}를 포함하는 여유로운 집합 중에서 \mathbf{A}의 원소들로 만들 수 있는 집합의 크기의 최댓값이다.


예제 

2
3 2
1 2 3
6 4
2 7 11 19 5 3
Case #1: 2 1 2
Case #2: 4 4 4 4 3 4
샘플 케이스 #1에서는 넓은 집합에 1과 2를 함께 넣을 수도 없고 2와 3을 함께 넣을 수도 없다. 따라서 S_2 = \{2\}이고 S_1 = S_3 = \{1,3\}으로 하면 최대 크기가 된다. 샘플 케이스 #2에서 최대 크기를 가지는 집합의 한 예는 다음과 같다: S_1 = S_2 = S_3 = S_4 = \{2,7,11,19\}, S_5 = \{11,19,5\}, S_6 = \{7,11,19,3\}.

출처

GCJ 2023b C

로그인해야 코드를 작성할 수 있어요.