1701. [Usaco2007 Jan]Cow School牛学校
#1701. [Usaco2007 Jan]Cow School牛学校
题目描述
Bessy 正在上学并且分数还不错. 她考了N (一个数据中1 <= N <= 50,000, 其余数据 1 <= N <= 50,00) 次试,每次考试得分为T_i, 满分为P_i(0 <= T_i <= P_i < 40,000; 0 < P_i). 在计算总分时,她的老师先将把分数(P_i/T_i)最高的D个试卷去掉,然后将其余P_i 的和除以其余T_i的和作为Bessy的分数. Bessy精通数学,所以很快发觉这并没有想象中那么好. Bessy想告诉她的老师所有附和以下条件的D: 如果令一组(D个)分数去掉,她的分数回比老师算出来的更高. Bessy 很惊讶地发现她没有两次考试得分百分点是一样的.
输入格式
*第一行: N
*第2..N+1行: 第i行里有 T_i 和 P_i.
输出格式
- 第一行: K, 符合条件的D的个数.
*第2..K+1行: 按递增顺序,每行一个符合条件的D.
样例
样例输入
5
1 2
5 9
3 8
4 10
1 3
输入解释:
Bessy 考了5门试, 分数分别为1/2, 5/9, 3/8, 4/10, 1/3.
样例输出
2
1
2
输出解释:
当D=1时, 去掉1/3将使总分变成13/29, 而去掉3/8则得到11/24.
当D=2时, 去掉1/3和3/8得到总分10/21. 更高的7/14则能由去掉3/8和4/10
得到.