P13315 [GCJ 2012 #1A] Password Problem

我有一个非常长的密码，有时候在输入时会出错。现在我已经输入了部分密码，但可能在输入前面的某些字符时按错了键。已知我每个字符输入正确的概率，你觉得我该怎么做？ 我有三种选择： 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$。 我并不知道自己实际错了几个，但对于任何策略，都可以算出期望按键次数。如下表： | 概率 | "gu" | "gx" | "xu" | "xx" | 期望值 | |:-:|:-:|:-:|:-:|:-:|:-:| | 如果继续输入 | $4$ | $10$ | $10$ | $10$ | $7.84$ | | 如果退格一次 | $6$ | $6$ | $12$ | $12$ | $8.4$ | | 如果退格两次 | $8$ | $8$ | $8$ | $8$ | $8$ | | 如果直接放弃 | $7$ | $7$ | $7$ | $7$ | $7$ | 如果我继续输入，有 $0.36$ 的概率只需 $4$ 次按键，有 $0.64$ 的概率需要 $10$ 次按键。大量重复这种情况，平均每次需要 $0.36 \times 4 + 0.64 \times 10 = 7.84$ 次按键。但在这个例子中，直接放弃（重输）只需要 $7$ 次按键，是更优选择。

输入的第一行为测试用例数 $T$。接下来有 $T$ 组测试数据。每组数据第一行为两个整数 $A$ 和 $B$，表示我已经输入的字符数 $A$，以及密码总长度 $B$。 接下来一行给出 $A$ 个实数：$p_1, p_2, \dots, p_A$，其中 $p_i$ 表示第 $i$ 个字符输入正确的概率。这些实数为小数，最多有一个小数点，小数点不会出现在数字开头或结尾。

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

**限制条件** - $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 完成。