问题陈述
高桥和青木正在玩游戏 N 回合。 对于 i=1,\ldots,N, i第轮按从上到下的顺序包含以下步骤。
- If i \geq 2 和高桥在比赛中受到处罚 (i-1)第轮, i第一轮结束,但不执行以下步骤。
- 高桥被发牌 a_i 金币。
- Takahashi 执行以下操作之一。
- 把 \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.
- 向青木展示一个空袋子。
- 青木选择一个整数 x 之间 1 和 100,包含在内,概率相等。
- If x\leq p,他检查了袋子。如果里面没有金币,高桥就把 \left \lfloor \frac{a_i \times t}{100} \right \rfloor 金币入袋并受到惩罚。
- If x \gt p,他什么也没做。
- Takashi 获得了本轮中处理的所有金币,但现在不在袋子里。
在这里,青木选择 x 每轮独立。
高桥将在每一轮中做出选择以最大化期望值 E 总共赚取的金币总数 N 回合。找到这个最大值 E.
约束
- 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
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N t p a_1 \ldots a_N
输出
打印答案。如果您的输出与真实答案的绝对或相对误差最多为 10^{−6}.
示例输入 1
3 10 50 100 10 300
示例输出 1
384.50000000000000000000
这是高桥最大化所赚取的金币总数的期望值的方法。
- 在第一轮中,袋子里没有放入任何东西。
- 在第二轮中,将指定数量的金币放入袋子中(如果他在第一轮中没有受到惩罚)。
- 在第三轮中,袋子里没有放入任何东西。
示例输入 2
3 1 10 192 191 190
示例输出 2
570.89999999999997726263
此输入的真实答案是 570.9。上面的输出与该值并不相同,但误差足够小,可以被认为是正确的。
示例输入 3
4 17 55 32 10 77 1000000000
示例输出 3
906500100.00000000000000000000