멘사(PAPRIKA)

멘사에 가입한 N명의 사람들이 한 줄로 서있다. 각 사람들은 모두 자신의 IQ가 기록된 신분증을 갖고 있다.

단, 이 사람들은 모두 멘사 회원이므로 실제 IQ가 148이 넘기 때문에 신분증에 기록된 IQ는 148을 뺀 값으로 기록한다.

한편, 멘사에서는 N명의 멘사 회원들 중 신분증에 표시된 IQ가 X보다 높은 사람들에게 ‘더 지니어스’라는 보드게임 파티에 초대한다.

신분증을 날조하는 것은 불가능하기 때문에 ‘더 지니어스’에 초대되는 사람의 수는 고정되어 있다.

어떤 사람들은 ‘더 지니어스’에 참여하고 싶어 하지만, ‘더 지니어스’에 참여하는 것을 별로 원치 않은 사람들도 있다.

그래서 N명의 사람들은 자기들끼리 신분증을 바꿔서 ‘더 지니어스’에 참여하고 싶은 사람들이 참여할 수 있게 하려고 한다.

이 사람들은 아래와 같은 방법으로 신분증을 바꾼다.

자신과 그 오른쪽 사람 중 신분증에 기재된 IQ가 더 높은 사람이 ‘더 지니어스’에 참여하는 것을 원치 않고, 더 낮은 사람이 ‘더 지니어스’에 참여하고 싶어 한다면, 서로 신분증을 바꾼다. 그 이외의 경우에는 신분증을 바꾸지 않는다. 두 사람의 IQ가 같은 경우 신분증을 바꾸지 않는다.
이 작업을 가장 왼쪽 사람부터 시작한다.

신분증을 바꾼 후, 자신이 원하는 대로 ‘더 지니어스’에 참여하거나 그렇지 않은 사람의 수를 구하여라.

입력

첫 번째 줄에는 사람의 수 N과 ‘더 지니어스’에 참여하기 위한 기준 IQ값 X가 주어진다. (1 ≤ N, X ≤ 1,000)

두 번째 줄부터 N개의 줄에는 각 사람의 정보가 주어진다.

첫 번째 수는 각 사람의 신분증에 기재된 IQ값이고 (1 ≤ IQ ≤ 1,000)
두 번째 수는 각 사람의 취향(0이면 ‘더 지니어스’에 참여하고 싶어 하려는 것이며, 1이면 ‘더 지니어스’에 참여하고 싶지 않다는 것)을 나타내는 정수이다.

출력

신분증을 바꾼 후, 자신이 원하는 대로 ‘더 지니어스’에 참여하거나 그렇지 않은 사람의 수를 출력한다.

예제1

예제2

예제3

사람들은 신분증은 아래와 같은 순서로 바꾼다.

신분증을 바꾼 후, 각 사람의 IQ는 15, 8, 12, 3, 10, 1이며, 1, 3번째 사람이 ‘더 지니어스’에 초대된다.

1번째 사람은 ‘더 지니어스’에 참여하고 싶어하지 않는데‘더 지니어스’에 초대되었으며, 5번째 사람은 ‘더 지니어스’에 참여하고 싶어 하는데 ‘더 지니어스’에 초대되지 않았다.

이 둘을 제외하면 나머지 4명은 모두 자신이 원하는 대로 이루어졌다.

출처

COCI 2014/2015 contest6 1

멘사(PAPRIKA) 1초 128MB