Description

我有一个非常长的密码，有时候在输入时会出错。现在我已经输入了部分密码，但可能在输入前面的某些字符时按错了键。已知我每个字符输入正确的概率，你觉得我该怎么做？

我有三种选择：

1. 继续输入剩下的密码，然后按下“回车”。我知道剩下的字符我一定能全部正确输入。如果之前输入的某个字符错了，我就需要重新输入整个密码并再次按“回车”——而这次我一定能全部输入正确。
2. 按下“退格键”若干次，删除我已经输入的最后若干字符，然后像选项 1 那样输入剩下的密码并按“回车”。如果没有删除的字符中有错的，我仍需重新输入整个密码并再次按“回车”，这次我一定能全部输入正确。
3. 直接放弃，按“回车”重新输入整个密码，再按一次“回车”。我知道这次我一定能全部输入正确。

我希望让期望按键次数最小。每输入一个字符算一次按键，每按一次“退格键”也算一次按键，每按一次“回车”完成一次尝试或直接放弃也算一次按键。

注意：“期望”按键次数是指如果这种情况发生很多次，平均每次需要的按键数。见下例。

例子

假设我的密码是“guest”，我已经输入了前两个字符，但每个字符输入时出错的概率都是 $40\%$。那么共有四种情况：

• 我输入了“gu”，全对。这种情况概率为 $0.6 \times 0.6 = 0.36$。
• 我输入了 'g' 正确，'u' 错了，此时输入的是“gx”。（这里 'X' 表示输错的字符。）概率为 $0.6 \times 0.4 = 0.24$。
• 我输入了 'u' 正确，'g' 错了，输入的是“xu”。概率为 $0.4 \times 0.6 = 0.24$。
• 两个都错了，输入的是“xx”。概率为 $0.4 \times 0.4 = 0.16$。

我并不知道自己实际错了几个，但对于任何策略，都可以算出期望按键次数。如下表：

如果我继续输入，有 $0.36$ 的概率只需 $4$ 次按键，有 $0.64$ 的概率需要 $10$ 次按键。大量重复这种情况，平均每次需要 $0.36 \times 4 + 0.64 \times 10 = 7.84$ 次按键。但在这个例子中，直接放弃（重输）只需要 $7$ 次按键，是更优选择。

Input Format

输入的第一行为测试用例数 $T$。接下来有 $T$ 组测试数据。每组数据第一行为两个整数 $A$ 和 $B$，表示我已经输入的字符数 $A$，以及密码总长度 $B$。

接下来一行给出 $A$ 个实数：$p_1, p_2, \dots, p_A$，其中 $p_i$ 表示第 $i$ 个字符输入正确的概率。这些实数为小数，最多有一个小数点，小数点不会出现在数字开头或结尾。

Output Format

对于每个测试用例，输出一行 "Case #x: y"，其中 $x$ 为测试用例编号（从 1 开始），$y$ 为在最优策略下，除去已经输入的字符后，期望还需按下的按键数。$y$ 的绝对或相对误差需不超过 $10^{-6}$。

3
2 5
0.6 0.6
1 20
1
3 4
1 0.9 0.1

Case #1: 7.000000
Case #2: 20.000000
Case #3: 4.500000

Hint

限制条件

• $1 \leq T \leq 20$
• 对所有 $i$，$0 \leq p_i \leq 1$

测试集 1（10 分，可见结果）

• $1 \leq A \leq 3$
• $A < B \leq 100$

测试集 2（10 分，隐藏结果）

• $1 \leq A \leq 99999$
• $A < B \leq 100000$

翻译由 ChatGPT-4.1 完成。