인기도: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 이라면 다음과 같은 관계가 성립해야 한다.
W[a[1]] < W[a[2]] < ... < W[a[n]]이고, S[a[1]] > S[a[2]] > ... > S[a[n]] 이런 관계가 만족되면서 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
Sample Output ¶
4 4 5 9 7
7 4 5 6 7 8 10 11
