시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB87723418336.970%

문제

지민이는 케이크를 N조각 사왔다. 각 조각은 무게가 서로 다르다. 지민이는 케이크를 최대 M번 자르려고 하는데, 한 조각을 한 번 자를 때마다 두 개의 서로 다른 조각으로 나누어진다. 최대 M번 잘라서 가장 무게가 많이 나가는 조각과 적게 나가는 조각의 무게 차이를 가장 작게 만들었을 때, 그 차이를 출력하라.

입력

첫째 줄에 케이크 조각의 개수 N이 주어진다. N은 50보다 작거나 같다. 둘째 줄에 각 조각의 무게가 주어진다. 이 값은 1,000,000,000보다 작거나 같은 자연수이다. 셋째 줄에는 M이 주어진다. M은 100,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 가장 무게가 많이 나가는 조각과 적게 나가는 조각의 최소 무게 차이를 출력한다. 절대/상대 오차는 10-9까지 허용한다.

예제 입력 1

2
1 3
1

예제 출력 1

0.5

예제 입력 2

5
1 1 1 1 1
4

예제 출력 2

0.0

예제 입력 3

2
1 3
1

예제 출력 3

0.5

예제 입력 4

3
7 11 13
10

예제 출력 4

0.3999999999999999

예제 입력 5

5
13 69 41 37 80
27

예제 출력 5

1.4666666666666668

출처