IsBiggerSmarter？

원문보기

---

인기도:B(A,B,C), 성공률:높음(낮음,보통,높음), 레벨:2(1~4)

About IsBiggerSmarter？

어떤 사람들은 코끼리가 클수록 더 똑똑하다고 생각한다. 그런 생각이 틀렸다는 것을 증명하기 위해, 일련의 코끼리들을 분석해서 체중은 증가하는 순서로, IQ는 감소하는 순서로 된 가장 긴 시퀀스를 뽑아보자.

Input

한 줄에 한 마리씩, 여러 코끼리에 대한 정보가 입력된다. 파일 종료 문자가 입력되면 입력이 끝난다. 각 코끼리에 대한 정보는 한 쌍의 정수로 입력되는데, 첫번째 정수는 체중을 킬로그램 단위로 나타낸 것이고, 두번째 정수는 IQ에 100을 곱한 값이다. 두 정수는 모두 1 이상 10,000 이하다. 최대 1,000 마리의 코끼리에 대한 정보가 입력될 수 있다. 체중이 같은 코끼리가 두 마리 이상 있을 수 있으며, IQ가 같은 코끼리가 두 마리 이상 있을 수도 있다. 그리고 체중과 IQ가 모두 똑같을 수도 있다.

Output

첫째 줄에는 찾아낸 코끼리 시퀀스의 길이를 나타내는 정수 n을 출력한다. 그 밑으로는 n줄에 걸쳐서 각 코끼리를 나타내는 양의 정수를 하나씩 출력한다. i번째 데이터 행으로 입력된 숫자들을 W[i], S[i]라고 표기해보자. 찾아낸 n마리의 코끼리의 시퀀스가 a[1], a[2], ... ,a[n] 이라면 다음과 같은 관계가 성립해야 한다.

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

풀이

작성자	사용언어	개발시간	코드
문보창	C++	.	IsBiggerSmarter？/문보창

쓰레드

두번째 테스트 케이스를 추가하였습니다. - 보창

---

문제분류 AOI