가장 가까운 선택
면접 대비시간 제한10초메모리 제한1024 MB
1부터 K까지의 번호가 적힌 티켓 N장이 이미 팔린 상태에서, 두 장을 골라 1부터 K 중 내 티켓이 가장 가까운 번호의 비율을 최대로 만든다.
문제
평생 공짜 팬케이크를 받는 추첨에 참여하려고 한다. 이미 N장의 티켓이 팔렸다. 각 티켓에는 1 이상 K 이하의 정수 하나가 적혀 있다. 서로 다른 티켓에 같은 정수가 적혀 있어도 된다. 이미 팔린 티켓에 적힌 수를 모두 알고 있으며, 티켓 두 장을 사서 당첨 확률을 최대화하려고 한다. 두 티켓에는 같은 정수가 적혀도 된다. 두 티켓에 적을 정수는 1 이상 K 이하에서 마음대로 고를 수 있다.
마지막 손님은 자신뿐이므로, 티켓을 산 뒤에는 더 이상 티켓이 팔리지 않는다. 그다음 1 이상 K 이하의 정수 c가 균등한 확률로 하나 선택된다. 내 티켓 중 하나가 다른 모든 티켓보다 c에 더 가깝거나, 내 티켓 두 장이 c까지 같은 거리에 있고 다른 모든 티켓보다 더 가까우면 추첨에서 이긴다. 그렇지 않으면 추첨에서 지지 않는다.
지금까지 팔린 N장의 티켓에 적힌 정수가 주어질 때, 두 티켓에 적을 정수를 최적으로 고를 때 얻을 수 있는 최대 당첨 확률은 얼마인가?
입력
입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. T개의 테스트 케이스가 이어진다. 각 테스트 케이스는 두 줄로 이루어진다. 테스트 케이스의 첫 줄에는 정수 N과 K가 주어진다. N은 이미 팔린 티켓의 수, K는 고를 수 있는 정수의 범위의 상한이다. 둘째 줄에는 이미 팔린 티켓에 적힌 정수를 나타내는 N개의 정수 P1, P2, …, PN이 주어진다.
출력
각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 티켓을 최적으로 골랐을 때 얻을 수 있는 최대 당첨 확률이다.
y는 정답과의 절대 오차 또는 상대 오차가 10−6 이내이면 정답으로 인정된다.
제한
- 1 ≤ T ≤ 100.
- 1 ≤ N ≤ 30.
- 모든 i에 대해 1 ≤ Pi ≤ K.
힌트
예제 1에서 4와 8이 적힌 티켓을 사면 4, 5, 8, 9, 10이 선택될 때 이겨서 당첨 확률이 5/10=0.5가 된다. 6과 8이 적힌 티켓을 사도 당첨 확률이 0.5이지만, 어떤 조합으로도 그보다 높일 수 없다.
예제 2에서 6과 8이 최적의 티켓 조합 중 하나이며, c가 6, 8, 9, 10 중 하나일 때 이긴다. 티켓에 적힌 정수가 반드시 정렬된 순서로 주어지는 것은 아니다.
예제 3에서는 가능한 모든 c가 이미 팔린 티켓과 거리 0이므로, 어떤 선택을 해도 이길 수 없다.
예제 4에서 두 티켓 중 적어도 하나에 3을 고르면 c=3일 때 이겨서 당첨 확률이 1/4=0.25가 된다. c가 다른 정수일 때 이길 방법이 없으므로 이것이 최선이다.