[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
得到.

---

提示

没有写明提示

---

题目来源

Gold