Informatica Online Judge

  불꽃놀이(Large) [1910 / 0776]

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


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[JOI Spring Training Camp Day1]

Background

경곽이는 자신을 포함한 n명의 친구들과 함께 불꽃놀이를 하기로 했다.

이번에 사용하는 불꽃은 불이 붙은 뒤 정확하게 t초간 탄다.

처음에 경곽이와 친구들은 수직선 형태의 긴 길에 한 명이 1개의 불꽃을 들고 있는 상태로 주어진 위치에 서 있다.

경곽이와 친구들은 각각 1이상 n 이하의 번호를 하나씩 부여받았다.

단 i < j라면 i번째 사람은 j번째 사람보다 왼쪽에 서 있거나, i번째 사람은 j번째 사람과 같은 위치이다.

i번째 사람은 가장 왼쪽에 있는 사람(1번 사람)으로부터 x_i미터 오른쪽으로 떨어진 위치에 있다.

경곽이는 k번째 사람이다.

불꽃놀이를 시작하려고 할 때, 라이터의 연료의 남은 량이 얼마되지 않아 오직 하나의 불꽃에만 불을 붙일 수 있다.

여기서 경곽이와 친구들은 우선 경곽이의 불꽃에 불을 붙이고, 불꽃으로부터 불꽃으로 불을 옮겨서 붙이기로 했다.

불꽃은 t초간 타기 때문에 경곽이와 친구들은 협력해서 불을 옮기는 수 밖에 없다.

불꽃으로부터 불꽃으로 불을 옮기기 위해서는 다음과 같은 조건을 만족해야 한다.

- 불을 옮기는 쪽의 불꽃은 점화 후 t초이내의 상태이어야 한다. 점화된 후 정확히 t초가 흐른 순간도 가능하다.

- 불을 옮겨받는 쪽의 불꽃은 아직 점화되지 않은 불꽃이어야만 한다.

- 불을 옮기는 쪽의 불꽃을 들고 있는 사람과 불을 옮겨받는 쪽의 불꽃을 든 사람은 같은 지점에 위치하지 않으면 안된다.


불꽃의 불을 옮기기 위해서 걸리는 시간은 무시한다.

처음 경곽이와 친구들이 서 있는 위치는 모두 다르므로 불을 옮기기 위해서는 적당히 이동하지 않으면 안된다.

경곽이와 친구들은 각각 원하는 속도로 왼쪽이나 오른쪽으로 이동할 수 있다.

하지만 너무 빠른 속도로 이동하는 것은 위험하므로 경곽이와 친구들은 1초 당 s미터 이하의 속도로 달리기로 했다.

여기서 s는 0이상의 정수이다.

모든 불꽃에 불을 붙이기 위해서는 속도 제한을 최소 1초 당 몇 미터로 설정해야할까?

이를 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에는 정수 n, k, t가 공백으로 구분되어 입력된다.

두 번째 줄부터 n줄에 걸쳐서 x_i가 입력된다.

[입력값의 정의역]
1 <= k <= n <= 100,000
1 <= t <= 1,000,000,000
0 <= x_i <= 1,000,000,000
x_1 = 0, x_i <= x_j ( 1 <= i <= j <= n )

[Sub-Task Info]
#Tiny : 1 <= n <= 20
#Small : 1 <= n <= 1,000
#Large : 추가제한사항 없음.

Output

설정할 수 있는 속도 s의 최솟값을 출력한다.

IO Example

입력
3 2 50
0
200
300

출력
2

* 설명
이 입력에서는 속도제산을 2미터로 하면 된다. 우선 1번 사람이 오른쪽으로 2번 사람은 왼쪽으로 3번 사람은 왼쪽으로 각각 초당 2미터를 진행하면 50초뒤 2번 사람으로부터 1번 사람의 불꽃으로 불을 옮길 수 있다.

다음으로 1번 사람은 오른쪽으로 3번 사람은 왼쪽으로 각각 2미터로 움직이면 25초뒤 1번 사람이 3번 사람의 불꽃에 불을 옮길 수 있다.

속도를 1로 하면 불가능하다. 따라서 답은 2

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