시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 118 34 20 25.974%

문제

동호는 월드 고등학교의 학생이다. 동호는 학교에서 N개의 시험을 봤다. 시험 점수는 Ti와 Pi로 주어진다. Ti는 i번째 시험에서 동호가 받은 점수를 의미하고, Pi는 i번째 시험의 토탈 점수를 의미한다.

이제 이 N개의 점수를 가지고 성적을 매겨야 하는데 성적은 Ti의 합을 Pi의 합으로 나눈 값을 의미한다. 만약에 동호가 1/2, 5/9, 3/8, 4/10, 1/3 의 점수를 얻었다면 (Ti/Pi의 형식) 동호가 받을 성적은 1+5+3+4+1/2+9+8+10+3 = 14/32 ≒ 0.44가 될 것이다.

그런데 동호의 담임 선생님은 그냥 이렇게 점수를 주면 동호의 성적이 너무 형편없기 때문에 동호가 본 N개의 시험 중, Ti를 Pi로 나눈 값, 즉 백분율이 작은 D개의 시험을 빼서 N-D개의 시험에 대해서만 성적을 합산하려 한다. 예를 들어 위에서 D가 1일 경우에는 1/3이 가장 작기 때문에 동호의 성적은 1/3을 뺀 1/2, 5/9, 3/8, 4/10을 더한 1+5+3+4/ 2+9+8+10 = 13/29 ≒ 0.45가 된다.

그런데 동호는 이러한 선생님의 선택에 반발을 하였다. 어차피 D개의 성적을 뺄 거면 다른 것을 빼지 왜 백분율이 작은 것을 빼냐는 것이다. 만약에 D가 1일 경우 1/3을 빼지 않고 3/8을 빼면 점수가 11/24 ≒ 0.46이 되어 위의 경우보다 점수가 더 높게 된다는 것이다.

동호의 담임선생님은 점수를 올려준다는데도 이에 반발한 동호에게 매우 화가 났다. 그래서 동호의 담임선생님은 즉석에서 다음과 같은 문제를 동호에게 내 주었다. 동호의 시험 점수가 주어져 있을 때, 동호의 이론이 성립하는 D를 모두 구하라는 것이다. 즉, 백분율이 작은 D개를 빼는 것 보다 다른 D개를 빼서 점수를 더 높이는 것이 가능한 D를 모두 구하라는 것이다. 동호는 매우 당황하였다. 점수를 올리려다가 큰 난관에 부딪힌 것이다. 여러분은 동호를 도와서 위의 조건은 만족하는 D를 모두 구하는 프로그램을 작성하여야 한다.

입력

첫째 줄에 동호가 시험을 본 개수 N(1≤N≤5,000, 단 마지막 데이터의 경우에 한해서 N=50,000이다). 그리고 두 번째 줄부터 N+1번째 줄까지 N개의 줄에 걸쳐 Ti와 Pi가 (0 ≤ Ti ≤ Pi ≤ 40,000  0 < Pi) 공백을 사이에 두고 주어진다.

출력

첫 줄에 가능한 D의 개수 K(0≤K≤N) 를 출력한다. 그리고 두 번째 줄부터 K+1번째 줄까지 가능한 D를 오름차순으로 모두 출력한다.

예제 입력 1

5
1 2
5 9
3 8
4 10
1 3

예제 출력 1

2
1
2
W3sicHJvYmxlbV9pZCI6IjE4NTkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMxMzFcdWM4MDEiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjNkOVx1ZDYzOFx1YjI5NCBcdWM2ZDRcdWI0ZGMgXHVhY2UwXHViNGYxXHVkNTU5XHVhZDUwXHVjNzU4IFx1ZDU1OVx1YzBkZFx1Yzc3NFx1YjJlNC4gXHViM2Q5XHVkNjM4XHViMjk0IFx1ZDU1OVx1YWQ1MFx1YzVkMFx1YzExYyBOXHVhYzFjXHVjNzU4IFx1YzJkY1x1ZDVkOFx1Yzc0NCBcdWJkMjRcdWIyZTQuIFx1YzJkY1x1ZDVkOCBcdWM4MTBcdWMyMThcdWIyOTQgVDxzdWI+aTxcL3N1Yj5cdWM2NDAgUDxzdWI+aTxcL3N1Yj5cdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBUPHN1Yj5pPFwvc3ViPlx1YjI5NCBpXHViYzg4XHVjOWY4IFx1YzJkY1x1ZDVkOFx1YzVkMFx1YzExYyBcdWIzZDlcdWQ2MzhcdWFjMDAgXHViYzFiXHVjNzQwIFx1YzgxMFx1YzIxOFx1Yjk3YyBcdWM3NThcdWJiZjhcdWQ1NThcdWFjZTAsIFA8c3ViPmk8XC9zdWI+XHViMjk0IGlcdWJjODhcdWM5ZjggXHVjMmRjXHVkNWQ4XHVjNzU4IFx1ZDFhMFx1ZDBjOCBcdWM4MTBcdWMyMThcdWI5N2MgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWM4MWMgXHVjNzc0IE5cdWFjMWNcdWM3NTggXHVjODEwXHVjMjE4XHViOTdjIFx1YWMwMFx1YzljMFx1YWNlMCBcdWMxMzFcdWM4MDFcdWM3NDQgXHViOWU0XHVhY2E4XHVjNTdjIFx1ZDU1OFx1YjI5NFx1YjM3MCBcdWMxMzFcdWM4MDFcdWM3NDAgVDxzdWI+aTxcL3N1Yj5cdWM3NTggXHVkNTY5XHVjNzQ0IFA8c3ViPmk8XC9zdWI+XHVjNzU4IFx1ZDU2OVx1YzczY1x1Yjg1YyBcdWIwOThcdWIyMDggXHVhYzEyXHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNTdkXHVjNWQwIFx1YjNkOVx1ZDYzOFx1YWMwMCAxXC8yLCA1XC85LCAzXC84LCA0XC8xMCwgMVwvMyBcdWM3NTggXHVjODEwXHVjMjE4XHViOTdjIFx1YzViYlx1YzVjOFx1YjJlNFx1YmE3NCAoVDxzdWI+aTxcL3N1Yj5cL1A8c3ViPmk8XC9zdWI+XHVjNzU4IFx1ZDYxNVx1YzJkZCkgXHViM2Q5XHVkNjM4XHVhYzAwIFx1YmMxYlx1Yzc0NCBcdWMxMzFcdWM4MDFcdWM3NDAgMSs1KzMrNCsxXC8yKzkrOCsxMCszID0gMTRcLzMyIFx1MjI1MiAwLjQ0XHVhYzAwIFx1YjQyMCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWRmOFx1YjdmMFx1YjM3MCBcdWIzZDlcdWQ2MzhcdWM3NTggXHViMmY0XHVjNzg0IFx1YzEyMFx1YzBkZFx1YjJkOFx1Yzc0MCBcdWFkZjhcdWIwZTUgXHVjNzc0XHViODA3XHVhYzhjIFx1YzgxMFx1YzIxOFx1Yjk3YyBcdWM4ZmNcdWJhNzQgXHViM2Q5XHVkNjM4XHVjNzU4IFx1YzEzMVx1YzgwMVx1Yzc3NCBcdWIxMDhcdWJiMzQgXHVkNjE1XHVkM2I4XHVjNWM2XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWIzZDlcdWQ2MzhcdWFjMDAgXHViY2Y4IE5cdWFjMWNcdWM3NTggXHVjMmRjXHVkNWQ4IFx1YzkxMSwgVDxzdWI+aTxcL3N1Yj5cdWI5N2MgUDxzdWI+aTxcL3N1Yj5cdWI4NWMgXHViMDk4XHViMjA4IFx1YWMxMiwgXHVjOTg5IFx1YmMzMVx1YmQ4NFx1YzcyOFx1Yzc3NCBcdWM3OTFcdWM3NDAgRFx1YWMxY1x1Yzc1OCBcdWMyZGNcdWQ1ZDhcdWM3NDQgXHViZTdjXHVjMTFjIE4tRFx1YWMxY1x1Yzc1OCBcdWMyZGNcdWQ1ZDhcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjXHViOWNjIFx1YzEzMVx1YzgwMVx1Yzc0NCBcdWQ1NjlcdWMwYjBcdWQ1NThcdWI4MjQgXHVkNTVjXHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0IFx1YzcwNFx1YzVkMFx1YzExYyBEXHVhYzAwIDFcdWM3N2MgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IDFcLzNcdWM3NzQgXHVhYzAwXHVjN2E1IFx1Yzc5MVx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHViM2Q5XHVkNjM4XHVjNzU4IFx1YzEzMVx1YzgwMVx1Yzc0MCAxXC8zXHVjNzQ0IFx1YmU4MCAxXC8yLCA1XC85LCAzXC84LCA0XC8xMFx1Yzc0NCBcdWIzNTRcdWQ1NWMgMSs1KzMrNFwvIDIrOSs4KzEwID0gMTNcLzI5IFx1MjI1MiAwLjQ1XHVhYzAwIFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZGY4XHViN2YwXHViMzcwIFx1YjNkOVx1ZDYzOFx1YjI5NCBcdWM3NzRcdWI3ZWNcdWQ1NWMgXHVjMTIwXHVjMGRkXHViMmQ4XHVjNzU4IFx1YzEyMFx1ZDBkZFx1YzVkMCBcdWJjMThcdWJjMWNcdWM3NDQgXHVkNTU4XHVjNjAwXHViMmU0LiBcdWM1YjRcdWNjMjhcdWQ1M2MgRFx1YWMxY1x1Yzc1OCBcdWMxMzFcdWM4MDFcdWM3NDQgXHViZTg0IFx1YWM3MFx1YmE3NCBcdWIyZTRcdWI5NzggXHVhYzgzXHVjNzQ0IFx1YmU3Y1x1YzljMCBcdWM2NWMgXHViYzMxXHViZDg0XHVjNzI4XHVjNzc0IFx1Yzc5MVx1Yzc0MCBcdWFjODNcdWM3NDQgXHViZTdjXHViMGQwXHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHViOWNjXHVjNTdkXHVjNWQwIERcdWFjMDAgMVx1Yzc3YyBcdWFjYmRcdWM2YjAgMVwvM1x1Yzc0NCBcdWJlN2NcdWM5YzAgXHVjNTRhXHVhY2UwIDNcLzhcdWM3NDQgXHViZTdjXHViYTc0IFx1YzgxMFx1YzIxOFx1YWMwMCAxMVwvMjQgXHUyMjUyIDAuNDZcdWM3NzQgXHViNDE4XHVjNWI0IFx1YzcwNFx1Yzc1OCBcdWFjYmRcdWM2YjBcdWJjZjRcdWIyZTQgXHVjODEwXHVjMjE4XHVhYzAwIFx1YjM1NCBcdWIxOTJcdWFjOGMgXHViNDFjXHViMmU0XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViM2Q5XHVkNjM4XHVjNzU4IFx1YjJmNFx1Yzc4NFx1YzEyMFx1YzBkZFx1YjJkOFx1Yzc0MCBcdWM4MTBcdWMyMThcdWI5N2MgXHVjNjJjXHViODI0XHVjOTAwXHViMmU0XHViMjk0XHViMzcwXHViM2M0IFx1Yzc3NFx1YzVkMCBcdWJjMThcdWJjMWNcdWQ1NWMgXHViM2Q5XHVkNjM4XHVjNWQwXHVhYzhjIFx1YjllNFx1YzZiMCBcdWQ2NTRcdWFjMDAgXHViMGFjXHViMmU0LiBcdWFkZjhcdWI3OThcdWMxMWMgXHViM2Q5XHVkNjM4XHVjNzU4IFx1YjJmNFx1Yzc4NFx1YzEyMFx1YzBkZFx1YjJkOFx1Yzc0MCBcdWM5ODlcdWMxMWRcdWM1ZDBcdWMxMWMgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWJiMzhcdWM4MWNcdWI5N2MgXHViM2Q5XHVkNjM4XHVjNWQwXHVhYzhjIFx1YjBiNCBcdWM4ZmNcdWM1YzhcdWIyZTQuIFx1YjNkOVx1ZDYzOFx1Yzc1OCBcdWMyZGNcdWQ1ZDggXHVjODEwXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzgzOCBcdWM3ODhcdWM3NDQgXHViNTRjLCBcdWIzZDlcdWQ2MzhcdWM3NTggXHVjNzc0XHViODYwXHVjNzc0IFx1YzEzMVx1YjliZFx1ZDU1OFx1YjI5NCBEXHViOTdjIFx1YmFhOFx1YjQ1MCBcdWFkNmNcdWQ1NThcdWI3N2NcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWM5ODksIFx1YmMzMVx1YmQ4NFx1YzcyOFx1Yzc3NCBcdWM3OTFcdWM3NDAgRFx1YWMxY1x1Yjk3YyBcdWJlN2NcdWIyOTQgXHVhYzgzIFx1YmNmNFx1YjJlNCBcdWIyZTRcdWI5NzggRFx1YWMxY1x1Yjk3YyBcdWJlN2NcdWMxMWMgXHVjODEwXHVjMjE4XHViOTdjIFx1YjM1NCBcdWIxOTJcdWM3NzRcdWIyOTQgXHVhYzgzXHVjNzc0IFx1YWMwMFx1YjJhNVx1ZDU1YyBEXHViOTdjIFx1YmFhOFx1YjQ1MCBcdWFkNmNcdWQ1NThcdWI3N2NcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWIzZDlcdWQ2MzhcdWIyOTQgXHViOWU0XHVjNmIwIFx1YjJmOVx1ZDY2OVx1ZDU1OFx1YzYwMFx1YjJlNC4gXHVjODEwXHVjMjE4XHViOTdjIFx1YzYyY1x1YjlhY1x1YjgyNFx1YjJlNFx1YWMwMCBcdWQwNzAgXHViMDljXHVhZDAwXHVjNWQwIFx1YmQ4MFx1YjUyYVx1ZDc4YyBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YzVlY1x1YjdlY1x1YmQ4NFx1Yzc0MCBcdWIzZDlcdWQ2MzhcdWI5N2MgXHViM2M0XHVjNjQwXHVjMTFjIFx1YzcwNFx1Yzc1OCBcdWM4NzBcdWFjNzRcdWM3NDAgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IERcdWI5N2MgXHViYWE4XHViNDUwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjNWVjXHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViM2Q5XHVkNjM4XHVhYzAwIFx1YzJkY1x1ZDVkOFx1Yzc0NCBcdWJjZjggXHVhYzFjXHVjMjE4IE4oMSZsZTtOJmxlOzUsMDAwLCBcdWIyZTggXHViOWM4XHVjOWMwXHViOWM5IFx1YjM3MFx1Yzc3NFx1ZDEzMFx1Yzc1OCBcdWFjYmRcdWM2YjBcdWM1ZDAgXHVkNTVjXHVkNTc0XHVjMTFjIE49NTAsMDAwXHVjNzc0XHViMmU0KS4gXHVhZGY4XHViOWFjXHVhY2UwIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIE4rMVx1YmM4OFx1YzlmOCBcdWM5MDRcdWFlNGNcdWM5YzAgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwIFQ8c3ViPmk8XC9zdWI+XHVjNjQwIFA8c3ViPmk8XC9zdWI+XHVhYzAwICgwICZsZTsgVDxzdWI+aTxcL3N1Yj4gJmxlOyBQPHN1Yj5pPFwvc3ViPiAmbGU7IDQwLDAwMCZuYnNwOyAwICZsdDsgUDxzdWI+aTxcL3N1Yj4pIFx1YWNmNVx1YmMzMVx1Yzc0NCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHViNDUwXHVhY2UwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwIFx1YWMwMFx1YjJhNVx1ZDU1YyBEXHVjNzU4IFx1YWMxY1x1YzIxOCBLKDAmbGU7SyZsZTtOKSBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWFkZjhcdWI5YWNcdWFjZTAgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgSysxXHViYzg4XHVjOWY4IFx1YzkwNFx1YWU0Y1x1YzljMCBcdWFjMDBcdWIyYTVcdWQ1NWMgRFx1Yjk3YyBcdWM2MjRcdWI5ODRcdWNjMjhcdWMyMWNcdWM3M2NcdWI4NWMgXHViYWE4XHViNDUwIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxODU5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQ293IFNjaG9vbCIsImRlc2NyaXB0aW9uIjoiPHA+QmVzc3kgaXMgZ29pbmcgdG8gc2Nob29sIGFuZCBkb2luZyB3ZWxsLiBTaGUgaGFzIHRha2VuIE4gKDEgJmx0Oz0gTiAmbHQ7PSA1MDAwIC0tIGV4Y2VwdCBvbmUgY2FzZSB3aGVyZSAxICZsdDs9IE4gJmx0Oz0gNTAsMDAwKSB0ZXN0cyBhbmQgcmVjb3JkZWQgdGhlIHNjb3JlcyAoVF9pIHBvaW50cyBvdXQgb2YgUF9pIHBvaW50cyBmb3IgdGVzdCBpOyAwICZsdDs9IFRfaSAmbHQ7PSBQX2kgJmx0OyA0MCwwMDA7IDAgJmx0OyBQX2kpIGFzIHRoaXMgdGFzayYjMzk7cyBpbnB1dC48XC9wPlxyXG5cclxuPHA+SGVyIHRlYWNoZXIgd2lsbCBkcm9wIHRoZSBEIHRlc3RzIHdpdGggdGhlIGxvd2VzdCBwZXJjZW50YWdlIChUX2lcL1BfaSkgYmVmb3JlIGNhbGN1bGF0aW5nIEJlc3NpZSYjMzk7cyBmaW5hbCBncmFkZSAod2hpY2ggaXMgdGhlIHN1bSBvZiB0aGUgcmVtYWluaW5nIHRlc3Qgc2NvcmUgcG9pbnRzIG92ZXIgdGhlIHN1bSBvZiB0aGUgcmVtYWluaW5nIHRvdGFsIHRlc3QgcG9pbnRzKS4gQmVzc3kgaXMgZ29vZCBhdCBtYXRoIGFuZCBxdWlja2x5IHJlYWxpemVzIHRoYXQgdGhpcyBkb2VzIG5vdCBiZW5lZml0IGhlciBhcyBtdWNoIGFzIGl0IG1pZ2h0LjxcL3A+XHJcblxyXG48cD5UbyBwcm92ZSBoZXIgcG9pbnQsIEJlc3N5IHdhbnRzIHRvIGZpbmQgYWxsIHZhbHVlcyBvZiBEIGZvciB3aGljaCBzaGUgY291bGQgaGF2ZSBlbmRlZCB1cCB3aXRoIGEgaGlnaGVyIGdyYWRlIGJ5IGNob29zaW5nIHRvIGRyb3AgZGlmZmVyZW50IHRlc3RzIHRoYW4gdGhlIHRlYWNoZXIgd291bGQgaGF2ZS4gSGVscCBoZXIgYnkgZmluZGluZyBhbmQgcHJpbnRpbmcgYWxsIHZhbHVlcyBvZiBEIGZvciB3aGljaCB0aGlzIGlzIHBvc3NpYmxlLjxcL3A+XHJcblxyXG48cD5CZXNzeSBoYXMgbm90ZWQgdGhhdCwgYW1hemluZ2x5LCBzaGUgaGFzIG5ldmVyIHNjb3JlZCB0aGUgc2FtZSBwZXJjZW50YWdlIG9uIHR3byBkaWZmZXJlbnQgdGVzdHMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD4qIExpbmUgMTogQSBzaW5nbGUgaW50ZWdlciwgTjxcL3A+XHJcblxyXG48cD4qIExpbmVzIDIuLk4rMTogTGluZSBpKzEgY29udGFpbnMgdHdvIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VyczogVF9pIGFuZCBQX2k8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD4qIExpbmUgMTogQSBzaW5nbGUgaW50ZWdlciBLICgwICZsdDs9IEsgJmx0Oz0gTikgdGhhdCBpcyB0aGUgbnVtYmVyIG9mIHZhbHVlcyBvZiBEIGZvciB3aGljaCBCZXNzeSBjb3VsZCBoYXZlIGVuZGVkIHVwIHdpdGggYSBoaWdoZXIgZ3JhZGUgYnkgZHJvcHBpbmcgYSBkaWZmZXJlbnQgc2V0IG9mIEQgdGVzdHMgdGhhbiB0aGUgdGVhY2hlci48XC9wPlxyXG5cclxuPHA+KiBMaW5lcyAyLi5LKzE6IFRoZSB2YWx1ZXMgb2YgRCBmb3Igd2hpY2ggdGhpcyBpcyB0cnVlLCBpbiBhc2NlbmRpbmcgbnVtZXJpY2FsIG9yZGVyLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Olympiad > USA Computing Olympiad > 2006-2007 Season > USACO January 2007 Contest > Gold 3번

  • 문제를 번역한 사람: author11
  • 빠진 조건을 찾은 사람: edenooo