레이팅 미적용젖소 베시는 차세대 히트 비디오 게임이 될 것이라 확신하는 게임을 설계했다. 바로 "화난 소들(Angry Cows)"이다. 베시가 완전히 독창적이라고 믿는 이 게임의 전제는, 플레이어가 새총으로 소 한 마리를 쏘아 수직선 위의 여러 지점에 놓인 건초 더미들로 이루어진 1차원 장면에 떨어뜨리는 것이다. 소는 착지 지점 근처의 건초 더미를 폭파시킬 만큼 충분한 힘으로 떨어지고, 이는 다시 연쇄 반응을 일으켜 추가로 건초 더미들이 폭발할 수 있다. 목표는 한 마리의 소로 연쇄 반응을 일으켜 모든 건초 더미를 폭파시키는 것이다.
수직선 위의 서로 다른 정수 위치 \(x_1, x_2, \ldots, x_N\)에 \(N\)개의 건초 더미가 놓여 있다. 위력 \(R\)로 발사된 소가 위치 \(x\)에 착지하면 "반지름 \(R\)"의 폭발이 일어나, \(x-R \ldots x+R\) 범위 안의 모든 건초 더미를 집어삼킨다. 그 건초 더미들은 (모두 동시에) 스스로 폭발하며, 각각 폭발 반지름은 \(R-1\)이다. 이 폭발에 휘말린, 아직 폭발하지 않은 더미들도 (모두 동시에) 폭발 반지름 \(R-2\)로 폭발하고, 이런 식으로 계속된다.
소 한 마리를 적절한 위치에 착지시켰을 때 장면의 모든 건초 더미가 연쇄적으로 폭파되도록 하는, 발사에 필요한 최소 위력 \(R\)을 구하여라.
출제자: Brian Dean
출제자: Brian Dean
입력의 첫째 줄에 \(N\) (\(2 \leq N \leq 50,000\))이 주어진다. 다음 \(N\)개의 줄에 정수 \(x_1 \ldots x_N\)이 주어진다 (각각 \(0 \ldots 1,000,000,000\) 범위).
모든 건초 더미를 폭파시키기 위해 소를 발사해야 하는 최소 위력 \(R\)을 출력한다. 답은 반올림하여 소수점 아래 정확히 1자리까지 출력해야 한다.
angry.in · 출력을 쓸 파일 angry.out5
8
10
3
11
13.0In this example, a cow launched with power 3 at, say, location 5, will cause
immediate detonation of hay bales at positions 3 and 8. These then explode
(simultaneously) each with blast radius 2, engulfing bales at positions 1 and
10, which next explode (simultaneously) with blast radius 1, engulfing the final
bale at position 11, which finally explodes with blast radius 0.