COCI 2014/2015 contest6 1- 멘사(PAPRIKA) > 문제은행 : 정보올림피아드&알고리즘




2825 : 멘사(PAPRIKA)

제한시간
1000 ms   
메모리제한
128 MB   
해결횟수
37 회   
시도횟수
99 회   

문제

멘사에 가입한 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이면 ‘더 지니어스’에 참여하고 싶지 않다는 것)을 나타내는 정수이다.

출력형식

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

입·출력 예

4 5
2 0
3 0
4 0
5 0

입력 예

5 5
3 1
2 0
13 1
2 0
10 1

출력 예

5

입력 예

6 10
15 1
12 1
8 0
10 1
3 0
1 1

출력 예

4

Hint!

예제 3 설명 사람들은 신분증은 아래와 같은 순서로 바꾼다. - 두 번째 사람이 세 번째 사람과 신분증을 바꾼다. - 네 번째 사람이 다섯 번째 사람과 신분증을 바꾼다. 신분증을 바꾼 후, 각 사람의 IQ는 15, 8, 12, 3, 10, 1이며, 1, 3번째 사람이 ‘더 지니어스’에 초대된다. 1번째 사람은 ‘더 지니어스’에 참여하고 싶어하지 않는데‘더 지니어스’에 초대되었으며, 5번째 사람은 ‘더 지니어스’에 참여하고 싶어 하는데 ‘더 지니어스’에 초대되지 않았다. 이 둘을 제외하면 나머지 4명은 모두 자신이 원하는 대로 이루어졌다.



경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP