题目描述

你正在参加一场抽奖活动，奖品是终身免费煎饼。已有 $\textbf{N}$ 张彩票售出。每张彩票包含一个 $1$ 到 $\textbf{K}$ 之间的整数（含端点）。不同的彩票可以包含相同的整数。你确切知道所有已售出彩票上的数字，并希望通过购买两张彩票（可以包含相同的整数）来最大化中奖概率。你可以自由选择 $1$ 到 $\textbf{K}$ 之间的任意整数作为这两张彩票的数字。

你知道自己是最后一位顾客，因此在你购买彩票后，不会再有任何彩票售出。接着，系统会均匀随机选择一个 $1$ 到 $\textbf{K}$ 之间的整数 $c$（含端点）。如果满足以下条件之一，你将赢得抽奖：

• 你的一张彩票到 $c$ 的距离严格小于其他所有彩票；
• 你的两张彩票到 $c$ 的距离相同，且严格小于其他所有彩票。

否则，你将不会赢得抽奖。

给定已售出的 $\textbf{N}$ 张彩票上的整数，通过最优选择你的两张彩票上的整数，你能够达到的最大中奖概率是多少？

输入格式

输入的第一行包含测试用例的数量 $\textbf{T}$。随后是 $\textbf{T}$ 个测试用例。每个测试用例包含两行：第一行是两个整数 $\textbf{N}$ 和 $\textbf{K}$，分别表示已售出的彩票数量和可选整数的上限；第二行包含 $\textbf{N}$ 个整数 $\textbf{P}_1, \textbf{P}_2, \ldots, \textbf{P}_\textbf{N}$，表示已售出彩票上的整数。

输出格式

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是你通过最优选择彩票能够达到的最大中奖概率。$y$ 的答案将被认为是正确的，如果其绝对误差或相对误差不超过 $10^{-6}$。关于误差范围的解释及可接受的实数格式，请参考 FAQ。

4
3 10
1 3 7
4 10
4 1 7 3
4 3
1 2 3 2
4 4
1 2 4 2

Case #1: 0.5
Case #2: 0.4
Case #3: 0.0
Case #4: 0.25

提示

样例解释

在样例 #1 中，你可以购买数字为 $4$ 和 $8$ 的彩票。当 $c$ 为 $4$、$5$、$8$、$9$ 或 $10$ 时，你将赢得抽奖，中奖概率为 $\frac{5}{10} = 0.5$。购买数字为 $6$ 和 $8$ 的彩票也能达到 $0.5$ 的中奖概率，但没有其他组合能超过这一概率。

在样例 #2 中，$6$ 和 $8$ 是一个可能的最优组合，当 $c$ 为 $6$、$8$、$9$ 或 $10$ 时，你将赢得抽奖。注意，已售出彩票上的数字不一定按升序排列。

在样例 #3 中，所有可能的 $c$ 都与至少一张已售出的彩票距离为 $0$，因此无论你如何选择彩票，都无法赢得抽奖。

在样例 #4 中，如果你至少选择一张数字为 $3$ 的彩票，你将在 $c = 3$ 时赢得抽奖，中奖概率为 $\frac{1}{4} = 0.25$。对于其他整数 $c$，你无法获胜，因此这是你能达到的最佳概率。

数据范围

• $1 \leq \textbf{T} \leq 100$。
• $1 \leq \textbf{N} \leq 30$。
• 对于所有 $i$，$1 \leq \textbf{P}_i \leq \textbf{K}$。

测试集 1（9 分，可见判定）

• $1 \leq \textbf{K} \leq 30$。

测试集 2（16 分，可见判定）

• $1 \leq \textbf{K} \leq 10^9$。

翻译由 DeepSeek V3 完成