Informatica Online Judge

  젖소 축구(Bronze) [2186 / 088A]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 13   Total Tried : 19


The Champion of this Problem (C++) : t1234 - 0ms / 543byte
My Best Submission (C++) : N/A

[USACO 2018(Dhruv Rohatgi)]

Background

곧 시작될 젓소 축구 토너먼트를 준비하며, 농부 존은 N마리(순서대로 1 ... N 번)의 젖소들에게 공 패스 훈련시키고 있다.

농장 한 쪽에 한 줄로 젖소들이 서있는데, i번째 젖소는 헛간으로부터 $x_i$ 만큼 떨어져 있고, 각각 서로 다른 위치에 서있다.

훈련을 시작하면, 농부 존은 여러 개의 공을 몇 마리의 젖소들에게 한 번에 모두 패스할 것이다.

i번째 젖소가 공을 받으면, 가장 가까이에 있는 젖소에게 다시 공을 패스한다.
(같은 거리에 있는 젓소들이 여러 마리인 경우, 가장 왼쪽에 있는 젖소에게 공을 패스한다.)

농부 존은 모든 젖소들이 적어도 한 번씩은 공을 패스 받을 수 있도록, 패스 연습을 시키고 싶어한다.

그렇게 하기 위해서, 처음에 필요한 공들의 최소 개수를 구해보자.

Input

첫 번째 줄에는 젖소의 마릿 수(N)가 입력된다.
두 번째 줄에는 N개의 정수가 공백을 두고 입력된다. i번째 정수 $x_i$는 i번째 소의 위치를 의미한다.

[입력값의 정의역]

$1≤N≤100$
$1≤x_i≤1000$

Output

모든 젖소들이 적어도 한 번씩은 공을 가져볼 수 있도록 하기 위해, 처음에 패스해 주어야하는 공의 최소 개수를 출력한다.

IO Example

입력
5
7 1 3 11 4

출력
2

* 설명 :
처음에 1, 11 위치에 있는 젖소에게 공을 패스해주어야 한다. 1 위치에 있는 젖소는 3 위치에 있는 젓소에 공을 패스하고, 그 다음에는 3 위치에 있는 젖소와 4 위치에 있는 젖소가 서로 공을 주고 받게 될 것이다. 11 위치에 있는 젖소는 7 위치에 있는 젖소에게 공을 패스하고, 그 다음에는 4 위치의 젖소에게 공이 패스 되어 3 위치에 있는 젖소와 4위치에 있는 젖소가 서로 공을 주고 받게 될 것이다. 이런 방법으로 최소 1번씩 공을 패스 받게 될 수 있다.

농부 존이 처음에 1개의 공만 패스해서, 모든 젖소들이 적어도 한 번씩 공을 패스 받게 할 수 있는 가능한 방법이 없다는 것을 알 수 있다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]