#P18068. GPA Optimization Plan
GPA Optimization Plan
GPA Optimization Plan
题目描述
成绩单上有 门课程,分属 个学期。第 门课的学分、绩点和所属学期分别为 。
每个学期可以选择至多一门课程,将其改为 PNP 模式,也可以不选择。选择 PNP 的课程不参与平均绩点计算。若参与计算的课程集合为 ,则平均绩点为
$$\operatorname{GPA}(R)=\frac{\sum_{i\in R}s_i g_i}{\sum_{i\in R}s_i}.$$保证前 门课满足 ,即每个学期最初都有两门课。
对每个 ,只考虑成绩单的前 门课,求选择 PNP 课程后能够得到的最大 GPA。不同 的选择相互独立。
输入格式
第一行整数 ,表示测试用例数。每组数据第一行两个整数 ,接下来 行每行三个整数 。
,,,,。每组均满足上述前 门课的学期限制。所有测试用例的 之和不超过 。
输出格式
每组数据输出 行,依次表示各个前缀的最大 GPA。
若输出为 、标准答案为 ,须满足 。
样例 1
输入
2
5 1
9 7 1
1 2 1
9 6 1
6 4 1
4 7 1
9 2
9 1 1
9 9 1
1 9 2
4 4 2
6 10 1
8 6 2
2 7 1
8 6 2
6 5 1
输出
7.0000000000
6.5000000000
6.2631578947
6.3913043478
9.0000000000
9.3750000000
8.3000000000
8.1818181818
7.6470588235
7.2500000000