/ Vijos / 题库 /

考试

考试

时间限制:1秒  内存限制:256M


【问题描述】

  贝茜正在上学并且每次考试分数都不错,她考了 \(N\) 次试,第 \(i\) 次考试得分为 \(T_i\),满分为 \(P_i\)。

  在计算总成绩前,她的老师先把的分数率 \(F_i\) 最低的 \(d\) 份试卷去掉,其中:\(F_i=\frac{T_i}{P_i}\),然后计算剩余 \(N-d\) 次考试的得分 \(T_i\) 之和总分 \(P_i\)之和,最后计算总成绩:\(G=\frac{∑T_i}{∑P_i}\)。

  贝茜精通数学,所以很快发现老师的算法会导致她总成绩偏低,并告诉老师“去掉其他的d次考试后成绩后,她的总成绩G比老师算出来的更高”。贝茜注意到,N次考试中没有任何两次考试的得分率是一样的。

【输入格式】

  第一行一个整数 \(N\),表示考试次数。接下来的 \(N\) 行,每行两个整数,分别表示 \(T_i\) 和 \(P_i\)。

【输出格式】

  第 1 行输出 \(K\),符合条件的整数 \(d\) 的个数,之后 \(K\) 行按递增顺序,每行一个符合条件的 \(d\)。

【输入输出样例】

 Input

5
1 2
5 9
3 8
4 10
1 3

 Output

2
1
2

【输入输出样例说明】

  当 \(D=1\) 时,老师的算法时去掉 \(\frac{1}{3}\),这将使总分变成 \(\frac{13}{29}\),而去掉\(\frac{8}{3}\)则可以得到\(\frac{11}{24}\)
  当 \(D=2\) 时,老师的算法时去掉\(\frac{1}{3}\)和\(\frac{3}{8}\),这将使总分变成\(\frac{10}{21}\),而去掉\(\frac{3}{8}\)和\(\frac{4}{10}\),则可以得到\(\frac{7}{14}\)。

【数据说明】

  对于 \(100\%\) 的数据,\(1 ≤ N ≤50000\),\(0 ≤ T_i,P_i ≤ 40000\)。

【来源】

  Mr.he

信息

ID
2698
难度
10
分类
计算几何 | 凸包 点击显示
标签
(无)
递交数
1
已通过
0
通过率
0%
上传者