← 返回题目列表

AtCoder · abc402_e

H. 需要付款

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

分数: 450 点

问题陈述

30XX年,每次提交某项竞赛都需要付费。

比赛有 N 问题。问题 i 有 S_i 积分,以及每次提交费用 C_i 日元。

当高桥提交给 i第题,他用概率解决了它 P_i %。每个提交的结果都独立于其他提交的结果。

他有 X 日元。他不能提交任何会导致他的总支出超过 X 日元。

求他选择提交时所解决问题的总分的期望值,以最大化该值。

他可以在看到上一次提交的结果后决定下一次提交哪个问题,并且多次解决同一问题将获得与解决一次相同的分数。

约束

  • 1 \leq N \leq 8
  • 1 \leq S_i \leq 2718
  • 1 \leq C_i \leq X \leq 5000
  • 1 \leq P_i \leq 100
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N X
S_1 C_1 P_1
S_2 C_2 P_2
\vdots
S_N C_N P_N

输出

打印答案。如果您的输出的绝对或相对误差不超过 10^{-6}.


示例输入 1

3 2
100 1 50
200 1 20
1000 1 1

示例输出 1

95

考虑以下提交策略:

  • 首先,提交第一个问题。
  • 如果提交正确,则提交第二个问题;否则,再次提交第一个问题。

该策略的预期总分是 95 点。任何策略都不能超过预期分数 95,所以打印 95.


示例输入 2

2 7
100 3 50
100 2 50

示例输出 2

125

示例输入 3

5 32
500 9 57
300 4 8
300 3 32
300 7 99
100 8 69

示例输出 3

953.976967020096

示例输入 4

7 78
100 1 100
200 2 90
300 3 80
400 4 60
450 5 50
525 6 30
650 7 1

示例输出 4

1976.2441416041121021