分数: 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