Mock CCO '18 Contest 3 Problem 6 - Roger Asks For More Marks

View as PDF

Submit solution

Points: 30 (partial)
Time limit: 0.25s
Memory limit: 64M

Problem type

Roger has taken N tests in preparation for CCO. On each test, there were a total of b_i marks available and Roger got a_i marks. Roger's final score is \frac{\sum_i a_i}{\sum_i b_i}. Roger's test percentages are all distinct.

Roger's teacher decides that, for some value of D, Roger's D lowest percentages will be dropped in evaluating his final score. Roger discovers that it may be possible to select a different set of D tests to drop which will result in a strictly higher score. Compute all D such that this is the case.


1 \le N \le 5 \cdot 10^4

0 \le a_i \le b_i < 4 \cdot 10^4

b_i > 0

Input Specification

The first line will contain an integer N.

Each of the next N lines contains two integers, a_i and b_i.

Output Specification

Output K+1 lines. On the first line, output K. On each of the next N lines, in ascending order, print the values of D for which Roger can do better than his teacher in maximizing his score. All valid values of D must be generated.

Sample Input

1 2
5 9
3 8
4 10
1 3

Sample Output



There are no comments at the moment.