AT_past202303_k.金貨と袋のゲーム

高桥和青木正在进行一个有 $N$ 轮的游戏。在第 $i$ 轮（$i=1,\ldots,N$）中，依次进行以下步骤：

• 如果 $i \geq 2$ 且高桥在第 $(i-1)$ 轮受到惩罚，则本轮直接结束，不再进行以下步骤。
• 高桥获得 $a_i$ 枚金币。
• 高桥执行以下两种操作之一：
  • 将 $\left\lfloor \frac{a_i \times t}{100}\right\rfloor$ 枚金币放入袋中并展示给青木（其中 $\lfloor x\rfloor$ 表示不超过 $x$ 的最大整数）。保证 $\left\lfloor \frac{a_i \times t}{100}\right\rfloor \geq 1$。
  • 展示一个空袋子给青木。
• 青木以等概率从 $1$ 到 $100$ 中随机选择一个整数 $x$。
  • 如果 $x \leq p$，他会检查袋子。如果袋子为空，高桥需要将 $\left\lfloor \frac{a_i \times t}{100}\right\rfloor$ 枚金币放入袋中，并受到惩罚。
  • 如果 $x > p$，青木什么也不做。
• 高桥获得本轮中除袋中外其余的所有金币。

其中，青木在每一轮的选择都是独立进行的。

高桥将在每一轮选择操作，使所有 $N$ 轮所得金币总数的期望值 $E$ 最大。请你求出 $E$ 的最大值。

输入从标准输入读入，格式如下：

$N$ $t$ $p$ $a_1$ $\ldots$ $a_N$

输出答案。如果你的输出与真实答案的绝对误差或相对误差不超过 $10^{-6}$，则视为正确。

样例解释 1

以下是高桥获取金币总数期望最大化的一种方案：

• 第一轮，袋子不放入任何金币。
• 第二轮，放入指定数量的金币（如果上一轮未受到惩罚）。
• 第三轮，不放入金币。

样例解释 2

本输入对应的正确答案是 $570.9$。上面的输出值虽然与此不同，但误差足够小，仍然被认为是正确的。

数据范围

• $1 \leq N \leq 100$
• $1 \leq t,p \leq 99$
• $1 \leq a_i \leq 10^9$
• $\left\lfloor \frac{a_i \times t}{100} \right\rfloor \geq 1$
• 所有输入均为整数。

由 ChatGPT 5 翻译