인기도:B(A,B,C), 성공률:높음(낮음,보통,높음), 레벨:2(1~4)
About IsBiggerSmarter? ¶
어떤 사람들은 코끼리가 클수록 더 똑똑하다고 생각한다. 그런 생각이 틀렸다는 것을 증명하기 위해, 일련의 코끼리들을 분석해서 체중은 증가하는 순서로, IQ는 감소하는 순서로 된 가장 긴 시퀀스를 뽑아보자.
Input ¶
한 줄에 한 마리씩, 여러 코끼리에 대한 정보가 입력된다. 파일 종료 문자가 입력되면 입력이 끝난다. 각 코끼리에 대한 정보는 한 쌍의 정수로 입력되는데, 첫번째 정수는 체중을 킬로그램 단위로 나타낸 것이고, 두번째 정수는 IQ에 100을 곱한 값이다. 두 정수는 모두 1 이상 10,000 이하다. 최대 1,000 마리의 코끼리에 대한 정보가 입력될 수 있다. 체중이 같은 코끼리가 두 마리 이상 있을 수 있으며, IQ가 같은 코끼리가 두 마리 이상 있을 수도 있다. 그리고 체중과 IQ가 모두 똑같을 수도 있다.
Output ¶
첫째 줄에는 찾아낸 코끼리 시퀀스의 길이를 나타내는 정수 n을 출력한다. 그 밑으로는 n줄에 걸쳐서 각 코끼리를 나타내는 양의 정수를 하나씩 출력한다. i번째 데이터 행으로 입력된 숫자들을 Wi, Si라고 표기해보자. 찾아낸 n마리의 코끼리의 시퀀스가 a1, a2, ... ,an 이라면 다음과 같은 관계가 성립해야 한다.
이런 관계가 만족되면서 n은 최대한 큰 값이어야 한다. 모든 부등호에는 등호는 포함되지 않는다. 즉 체중은 반드시 증가해야 하며(같으면 안됨), IQ는 감소해야 한다.(IQ도 같으면 안 됨). 조건이 맞으면 아무 답이나 출력해도 된다.
Sample Input ¶
6008 1300 6000 2100 500 2000 1000 4000 1100 3000 6000 2000 8000 1400 6000 1200 2000 1900
1 4 2 3 3 2 4 100 5 90 6 80 7 70 8 60 9 5 10 50 11 45
