← 返回题目列表

Codeforces · 865/C

C. 得快点

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

您正在尝试刷新您最喜爱的视频游戏的记录。游戏由 N 个关卡组成,必须按顺序完成这些关卡才能通关。您通常会尽快完成每个级别,但有时会较慢地完成一个级别。具体来说,您将在 Fi 秒或 Si 秒内完成第 i 个关卡,其中 Fi < Si,并且有 Pi 百分比的机会在 Fi 秒内完成它。完成一个级别后,您可以决定继续游戏并玩下一个级别,或者重置游戏并从第一个级别重新开始。决定和行动都是即时的。

您的目标是在最多 R 秒内按顺序完成所有级别。在实现该目标之前,您希望尽量减少预期的游戏时间。如果您继续并以最佳方式重置,您预计会花多少总时间玩游戏?

输入

输入的第一行包含整数 N 和 R $$( 1 \leq N \leq 5 0, \sum F _ { i } \leq R \leq \sum S _ { i } )$$,分别是你想要完成游戏的关卡数和秒数。接下来是 N 行。第 i 行包含整数 Fi、Si、Pi (1 ≤ Fi < Si ≤ 100, 80 ≤ Pi ≤ 99)、级别 i 的快速时间、级别 i 的慢速时间以及以快速时间完成级别 i 的概率(以百分比表示)。

输出

打印预计总时间。您的答案必须正确,绝对误差或相对误差在 10 - 9 之间。

正式来说,让您的答案为 a,陪审团的答案为 b。如果 $${ \frac { | 则您的答案将被认为是正确的a - b | } { \operatorname* { m a x } ( 1, | b | ) } } \leq 1 0 ^ { - 9 }$$。

示例

输入 #1

1 8
2 8 81

输出 #1

3.14

输入 #2

2 30
20 30 80
3 9 85

输出 #2

31.4

输入 #3

4 319
63 79 89
79 97 91
75 87 88
75 90 83

输出 #3

314.159265358

注意

在第一个示例中,您永远不需要重置。有 81% 的机会在 2 秒内完成关卡,有 19% 的机会需要 8 秒,两者都在目标时间内。预计时间为 0.81·2 + 0.19·8 = 3.14。

在第二个示例中,如果您缓慢完成第一级,则应该在第一级之后重置。平均而言,在第一次快速尝试之前需要 0.25 次慢速尝试。那么无论你完成第二关是快还是慢都没关系。预计时间为 0.25·30 + 20 + 0.85·3 + 0.15·9 = 31.4。