Informatica Online Judge

  제자리 멀리뛰기 [0432 / 01B0]

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


The Champion of this Problem (C++) : gs16051 - ms / 425byte
My Best Submission (C++) : N/A

[]

Background

GSHS는 체력측정 중 제자리 멀리뛰기가 가장 중요하다.

GSHS의 체육선생님께서는 학생들의 제자리 멀리뛰기 실력을 키우기 위해 특수 훈련을 준비중이다.

특수 훈련장소는 GSHS특수 트레이닝 센터로 이 곳은 끓는 용암으로 가득 차 있다.

체육선생님께서는 이 용암으로 가득찬 방의 가운데 있는 돌섬에 학생들을 보낸 후 탈출하기를 기대하고 있다.

탈출할 수 있는 방법은 돌섬에서 탈출구까지 존재하는 작은 디딤돌로 점프하여 탈출구까지 가는 것이다.

돌섬에서 탈출구 사이에는 총 $n$개의 디딤돌이 있다.

선생님은 이 $n$개의 디딤돌 중 $m$개를 제거하여 학생들이 최대한 멀리뛰기 연습을 하게 하고자 한다.

즉, 학생들이 각 디딤돌을 점프한 거리의 최솟값을 최대한 크게 하려고 한다.

물론 학생들은 체력이 좋기 때문에 두 디딤돌 사이의 아무리 멀더라도 점프할 수 있다.

그리고 학생들은 게으르기 때문에 탈출 시 $n-m$개의 모든 디딤돌들을 밟으면서 탈출한다.

학생들이 돌섬으로부터 탈출구까지의 거리 $d$가 주어지고, 각 $n$개의 작은 디딤돌의 위치가 주어지며, 삭제할 수 있는 디딤돌의 수 $m$이 주어질 때, 학생들이 점프하는 최소거리의 최댓값을 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에는 갇힌 돌섬으로부터 탈출구까지의 거리 $d$( $1 <= d <= 1,000,000,000$ ),

디딤돌의 수 $n$( $0 <= n <= 50,000$ ), 제거할 수 있는 디딤돌의 수 $m$ ($0 <= m <= n$ )이 공백으로 구분되어 주어진다.

두 번째 줄부터 n줄에 걸쳐서 돌섬으로부터 각 디딤돌이 얼마나 떨어져 있는지를 나타내는 하나의 정수가 한 줄에 하나씩 주어진다.

Output

$m$개의 디딤돌을 제거한 뒤 학생들이 점프할 수 있는 최소거리의 최댓값을 출력한다.

IO Example

입력
25 5 2
2
14
11
21
17

출력
4

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