← 返回题目列表

Codeforces · 1067/D

D. 电脑游戏

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

Ivan 玩一些电脑游戏。游戏中有 $$$n$$$ 任务。每个任务可以升级一次,这会增加完成奖励。每个任务有$$$3$$$参数$$$a_{i}$$$、$$$b_{i}$$$、$$$p_{i}$$$:升级前完成任务的奖励、升级后完成任务的奖励($$$a_{i} < b_{i}$$$)以及成功完成任务的概率。

每一秒 Ivan 都可以尝试完成一个任务,他将以 $$$p_{i}$$$ 的概率成功。如果成功,伊万将获得奖励和升级任何一项任务的机会(不一定是他刚刚完成的任务)。万一失败,他什么也得不到。任务完成后不会消失。

Ivan 有 $$$t$$$ 秒。他希望在 $$$t$$$ 秒后最大化他的总收益的预期值。帮他算一下这个值。

输入

第一行包含 $$$2$$$ 整数 $$$n$$$ ($$$ 1 \le n \le 10^{5}$$$) 和 $$$t$$$ ($$$ 1 \le t \le 10^{10}$$$) - 任务数量和总时间。

以下 $$$n$$$ 行包含任务描述。每个描述都是 $$$3$$$ 数字 $$$a_{i}$$$ $$$b_{i}$$$ $$$p_{i}$$$ ($$$1 \le a_{i} < b_{i} \le 10^{8}$$$, $$$0 < p_{i} < 1$$$) — 升级前完成任务的奖励、升级后完成任务的奖励以及成功完成任务的概率追求。 $$$a_{i}$$$ 和 $$$b_{i}$$$ 是整数。所有概率最多保留 $$$9$$$ 小数位。

输出

打印期望值。

如果绝对或相对误差不超过 $$$10^{-6}$$$,您的答案将被接受。正式来说,让您的答案为$$$a$$$,陪审团的答案为$$$b$$$。如果 $$$\frac{|a-b|}{max⁡(b, \,\, 1)} \le 10^{-6}$$$,则认为您的答案是正确的。

示例

输入 #1

3 2
3 1000 0.5
1 2 0.48
3 20 0.3

输出 #1

252.2500000000000

输入 #2

2 2
1 1000 0.1
2 3 0.2

输出 #2

20.7200000000000