/ TYWZ / 题库 /

Manuscript Review

Manuscript Review

题目描述

断罪中学的王大锤和赵铁柱同学成立了一个兴趣社团“龙门城邦地理”,并号召全校同学为第一期社刊投稿,最终他们共计收到了\(N\)篇稿件。审稿的过程需要一定的成本,若将第\(i\)篇稿件全部交给王大锤审查,则成本为\(A_i\);若完全交给赵铁柱审查,则成本为\(B_i\)。当然他们二人也可以选择合作审查一篇稿件,对于第\(i\)篇稿件,二人可以任选闭区间\([0,100]\)之内的一个 实数 \(p_i\),将\(p_i\%\)的部分交给王大锤,成本为\(0.01p_iA_i\);余下\((100-p_i)\%\)的部分交给赵铁柱,成本为\(0.01(100-p_i)B_i\)。总的审稿成本等于 二人各自的成本之和取最大值 。请你设计一种方案,通过调整\(p_1 \cdots p_N\)的值,使得总成本最小化。

输入格式

第一行是一个正整数\(T\),表示测试数据的组数;
之后每组数据,第一行是一个正整数\(N\),表示稿件的总数;
之后\(N\)行,每行两个正整数\(A_i, B_i\),表示该篇稿件完全交给王大锤或者赵铁柱的成本分别为多少。

输出格式

每组数据输出一行,将总成本的最小值以 最简分数 的形式输出(若答案为整数则分母为1)。

样例

输入

3
3 
1 4
3 1
5 2
5
5 1
2 8
10 7
7 4
3 9
2
1 4
4 1

输出

17/7
25/2
1/1

样例说明

第一组数据的最优解:\(p_1=100, \quad p_2=0, \quad p_3 = 100 \times 2/7\)

数据规模及约定

本题共有20个测试文件,所有测试点均满足\(T \le 5\)
测试点1~4:\(N \le 2000\), \((A_i, B_i)\)只可能是\((1,1), \quad (1,2) \quad (2,1)\)三者之一
测试点5~8:\(N \le 2 \times 10^5\), \((A_i, B_i)\)只可能是\((1,1), \quad (1,2) \quad (2,1)\)三者之一
测试点9~11:\(N \le 2000\),\(A_i = 1\)
测试点12~14:\(N \le 2 \times 10^5\),\(A_i = 1\)
测试点15~17:\(N \le 2000\)
所有测试数据均满足:\(N \le 2 \times 10^5, \quad 1 \le A_i, B_i \le 10^5\)
时间限制1s,空间限制64MB。

信息

ID
1058
难度
9
分类
(无)
标签
(无)
递交数
4
已通过
2
通过率
50%
上传者