레이팅 미적용전염성이 매우 강한 소 질병 COWVID-19가 발생한 후, 농부 존은 소들의 건강을 걱정하고 있다.
\(N\)마리의 소(\(1 \leq N \leq 1000\))에게 "사회적 거리두기"를 시키려고 최선을 다했음에도 불구하고, 안타깝게도 여전히 많은 소가 이 병에 걸렸다. \(1 \ldots N\)으로 번호가 매겨진 소들은 긴 길(사실상 1차원 수직선)을 따라 서로 다른 지점에 서 있으며, 소 \(i\)는 위치 \(x_i\)에 서 있다. 농부 존은 어떤 반지름 \(R\)이 존재하여, 감염된 소로부터 \(R\) 단위 이내(경계 포함)에 서 있는 모든 소도 감염되고, 그 소는 다시 \(R\) 단위 이내의 다른 소들에게 감염을 옮기며, 이런 식으로 계속된다는 것을 알고 있다.
안타깝게도 농부 존은 \(R\)을 정확히 알지 못한다. 다만 어떤 소들이 감염되었는지는 알고 있다. 이 데이터가 주어질 때, 처음에 병에 감염되어 있었을 수 있는 소의 최소 마릿수를 구하시오.
문제 제공: Brian Dean
문제 제공: Brian Dean
입력의 첫째 줄에 \(N\)이 주어진다. 다음 \(N\)개의 줄 각각에 소 한 마리를 나타내는 두 정수 \(x\)와 \(s\)가 주어진다. \(x\)는 위치(\(0 \leq x \leq 10^6\))이고, \(s\)는 건강한 소면 0, 병에 걸린 소면 1이다. 적어도 한 마리의 소는 병에 걸려 있으며, 병의 전파로 인해 병에 걸렸을 수 있는 모든 소는 이미 병에 걸린 상태이다.
병이 전파되기 전, 처음에 병에 걸려 있었을 수 있는 소의 최소 마릿수를 출력한다.
socdist2.in · 출력을 쓸 파일 socdist2.out6
7 1
1 1
15 1
3 1
10 0
6 13In this example, we know that \(R < 3\) since otherwise the cow at position 7
would have infected the cow at position 10. Therefore, at least 3 cows must
have started out infected -- one of the two cows at positions 1 and 3, one of
the two cows at positions 6 and 7, and the cow at position 15.
riseoj 작성
출처 올림피아드 > USACO > 2019-2020 > US Open > Bronze