← 返回题目列表

AtCoder · past202303_k

K. 金币和袋子游戏

中文机器翻译题面 查看原题

问题陈述

高桥和青木正在玩游戏 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