레이팅 미적용다가오는 발굽 공놀이 대회를 준비하기 위해, 농부 존은 \(N\)마리의 소들(편의상 \(1\dots N\)으로 번호가 매겨져 있으며, \(1 \leq N \leq 100\))에게 공 패스 훈련을 시키고 있다. 소들은 모두 헛간 한쪽의 매우 긴 직선을 따라 서 있으며, 소 \(i\)는 헛간에서 \(x_i\) 단위만큼 떨어진 곳에 서 있다 (\(1 \leq x_i \leq 1000\)). 각 소는 서로 다른 위치에 서 있다.
훈련이 시작될 때, 농부 존은 여러 개의 공을 서로 다른 소들에게 건네줄 것이다. 소 \(i\)가 농부 존에게서든 다른 소에게서든 공을 받으면, 자신에게 가장 가까운 소에게 공을 패스한다(같은 거리에 있는 소가 여러 마리라면, 그중 가장 왼쪽에 있는 소에게 패스한다). 모든 소가 최소한의 패스 연습이라도 할 수 있도록, 농부 존은 모든 소가 적어도 한 번은 공을 잡게 하고 싶다. 농부 존이 적절한 초기 소들에게 공을 건네준다고 가정할 때, 이를 보장하기 위해 처음에 나눠 주어야 하는 공의 최소 개수를 구하도록 도와주자.
출제자: Dhruv Rohatgi
출제자: Dhruv Rohatgi
입력의 첫째 줄에 \(N\)이 주어진다. 둘째 줄에 공백으로 구분된 정수 \(N\)개가 주어지며, \(i\)번째 정수는 \(x_i\)이다.
모든 소가 적어도 한 번은 공을 잡을 수 있도록 농부 존이 처음에 소들에게 건네주어야 하는 공의 최소 개수를 출력한다.
hoofball.in · 출력을 쓸 파일 hoofball.out5
7 1 3 11 42In the above example, Farmer John should pass a ball to the cow at \(x=1\) and
pass a ball to the cow at \(x=11\). The cow at \(x=1\) will pass her ball to the cow
at \(x=3\), after which this ball will oscillate between the cow at \(x=3\) and the
cow at \(x=4\). The cow at \(x=11\) will pass her ball to the cow at \(x=7\), who will
pass the ball to the cow at \(x=4\), after which this ball will also cycle between
the cow at \(x=3\) and the cow at \(x=4\). In this way, all cows will be passed a
ball at least once (possibly by Farmer John, possibly by another cow).
It can be seen that there is no single cow to whom Farmer John could initially pass a ball
so that every cow would eventually be passed a ball.
riseoj 작성
출처 올림피아드 > USACO > 2017-2018 > February > Bronze