레이팅 미적용농부 존은 소의 몸무게만으로 그 소에게 점박이 무늬가 있는지 예측하는 자동 시스템을 고안했다. 새로운 소 C를 분류하기 위해 FJ는 자신의 소 떼에서 C와 몸무게가 가장 가까운 소 C'를 찾는다. C'에게 점박이 무늬가 있으면 FJ는 C에게도 있을 것이라 추측하고, C'에게 없으면 C에게도 없을 것이라 추측한다. 가장 가까운 이웃 C'가 유일하지 않고 FJ의 소 두 마리가 동률이라면, 그 두 최근접 이웃 중 한 마리라도 점박이 무늬가 있으면 FJ는 C에게 점박이 무늬가 있을 것이라 추측한다.
FJ는 새로 들어온 소 무리에 이 점박이 예측기를 시험해 보려 한다. 소들의 몸무게를 재어 보니, 새로 도착한 무리에는 A 이상 B 이하의 모든 정수 몸무게의 소가 한 마리씩 있었다. FJ의 분류기를 사용할 때 이 소들 중 몇 마리가 점박이가 있는 것으로 분류되는지 구하라. 분류기는 FJ의 기존 소 N마리의 데이터만 사용한다는 점에 유의하라. A와 B가 모두 꽤 클 수 있으므로, A부터 B까지 하나씩 반복하는 프로그램은 충분히 빠르게 동작하지 않을 가능성이 높다.
(참고: 이 문제의 지문은 가져오는 과정에서 일부만 복원되었다.)
첫째 줄: 세 정수 N, A, B가 주어진다(1 <= A <= B <= 1,000,000,000).
둘째 줄부터 1+N째 줄까지: 각 줄에 소 한 마리가 "S W"(몸무게 W의 점박이 소) 또는 "NS W"(몸무게 W의 점박이가 아닌 소) 형태로 주어진다. 몸무게는 1 ... 1,000,000,000 범위의 정수이다.
FJ의 알고리즘이 점박이가 있다고 분류할 새로 들어오는 소의 수를 정수 하나로 출력한다.
learning.in · 출력을 쓸 파일 learning.out3 1 10
S 10
NS 4
S 16Output details: The incoming cows of weights 1, 2, 7, 8, 9, and 10 will all be classified as having spots.
riseoj 작성
출처 올림피아드 > USACO > 2014-2015 > December > Bronze