화난 소들

젖소 베시는 차세대 히트 비디오 게임이 될 것이라 확신하는 게임을 설계했다. 바로 "화난 소들(Angry Cows)"이다. 베시가 완전히 독창적이라고 믿는 이 게임의 전제는, 플레이어가 새총으로 소를 쏘아 수직선 위의 여러 지점에 놓인 건초 더미들로 이루어진 1차원 장면에 떨어뜨리는 것이다. 각 소는 착지 지점 근처의 건초 더미를 폭파시킬 만큼 충분한 힘으로 떨어진다. 목표는 여러 마리의 소를 사용해 모든 건초 더미를 폭파시키는 것이다.

수직선 위의 서로 다른 정수 위치 \(x_1, x_2, \ldots, x_N\)에 \(N\)개의 건초 더미가 놓여 있다. 위력 \(R\)로 발사된 소가 위치 \(x\)에 착지하면 "반지름 \(R\)"의 폭발이 일어나, \(x-R \ldots x+R\) 범위 안의 모든 건초 더미가 파괴된다.

발사할 수 있는 소는 총 \(K\)마리이며, 모두 같은 위력 \(R\)을 가진다. \(K\)마리의 소를 사용해 장면의 모든 건초 더미를 폭파시킬 수 있게 하는 \(R\)의 최소 정수 값을 구하여라.

출제자: Brian Dean

출제자: Brian Dean

입력의 첫째 줄에 \(N\) (\(1 \leq N \leq 50,000\))과 \(K\) (\(1 \leq K \leq 10\))가 주어진다. 다음 \(N\)개의 줄에 정수 \(x_1 \ldots x_N\)이 주어진다 (각각 \(0 \ldots 1,000,000,000\) 범위).

모든 건초 더미를 폭파시키기 위해 각 소를 발사해야 하는 최소 위력 \(R\)을 출력한다.

riseoj 작성

출처 올림피아드 > USACO > 2015-2016 > January > Silver