你们中的许多人一定熟悉 Google Code Jam 的回合规则。让我们提醒您一些对于解决此问题至关重要的关键时刻。在这一轮中,建议参与者解决几个问题,每个问题分为两个子问题:一个限制较小的简单问题(小输入),一个限制较大的困难问题(大输入)。只有在解决了该问题的小输入后,您才能提交大输入的解决方案。对求解输入的顺序没有其他限制。特别是,参与者可以先解决小输入,然后切换到另一个问题,然后返回大输入。解决每个输入都会为参与者提供一定数量的分数(通常每个问题都不同)。这仅考虑在所有输入测试中都能正常工作的完整解决方案。参与者在提交小输入后立即获得测试结果,但大输入的测试结果要在回合结束后才会出来。在最终成绩表中,参赛者按照得分不增加的顺序进行排序。如果分数相同,则按照罚时从小到大的顺序对参赛者进行排序。根据 Google Code Jam 规则,时间惩罚是最后提交正确解决方案的时间。
Vasya 决定在另一轮中尝试新的战术。一轮开始后,男孩很快地读完了所有问题,并准确地评估了解决这些问题所需的时间。具体来说,对于 n 个问题中的每一个问题,Vasya 都知道五个值:
- 解决第 i 个问题的小输入为参与者提供了 ScoreSmli 分数,解决大输入则为参与者提供了更多分数。也就是说,第 i 个问题可以获得的最大分数等于 ScoreSmalli + scoreLargei。
- 对于 Vasya 来说,编写第 i 个问题的小输入的解决方案正好需要 timeSmali 分钟。改进这段代码并将其转化为大输入的解决方案又需要花费几分钟的时间。
- Vasya 有很多练习,所以他从第一次尝试就解决了所有小输入。但对于大输入来说就不那么容易了:大输入的解决方案在回合结束时有 probFaili 概率被证明是错误的。请记住,这些解决方案不会影响参与者的积分和时间惩罚。
一轮持续 t 分钟。阅读问题和提交解决方案的时间可以认为为零。 Vasya 可以在回合结束时准确提交解决方案。
Vasya 想要选择一组输入及其解决方案的顺序,以使总接收点的期望尽可能最大。如果有多种方法可以做到这一点,他需要最小化时间惩罚的期望。帮助瓦夏解决这个问题。
输入
第一行包含两个整数 n 和 t (1 ≤ n ≤ 1000, 1 ≤ t ≤ 1560)。接下来是 n 行,每行包含 5 个数字:scoreSmalli、scoreLargei、timeSmali、timeLargei、probFaili (1 ≤ ScoreSmli、scoreLargei ≤ 109、1 ≤ timeSmalli、timeLargei ≤ 1560、0 ≤ probFaili ≤ 1)。
probFaili 是实数,小数点后最多有 6 位数字。输入中的所有其他数字都是整数。
输出
打印两个实数——总分的最大期望和相应的最小可能的时间惩罚期望。如果绝对误差或相对误差不超过 10 - 9,则答案将被视为正确。
示例
输入 #1
3 40 10 20 15 4 0.5 4 100 21 1 0.99 1 4 1 1 0.25
输出 #1
24.0 18.875
输入 #2
1 1 100000000 200000000 1 1 0
输出 #2
100000000 1
注意
在第一个示例中,解决问题的最佳顺序之一是:
1.第三个问题的输入较小。
2.第一个问题的输入量较小。
3.第三个问题的输入量大。
4.第一个问题输入量大。
请注意,如果您解决第二个问题的小输入而不是第三个问题的两个输入,那么总分期望将相同,但时间惩罚期望会更差(38)。