케이크

시간 제한2초메모리 제한128 MB

요약

N개의 케이크 조각을 최대 M번 잘라서 가장 무거운 조각과 가장 가벼운 조각의 차이를 최소화하는 문제입니다.

난이도: 어려움10점 중 8점
유형: 이분 탐색, 그리디, 수학, 구현
정답자: 아직 제출이 없습니다

문제

지민이는 케이크 조각 N개를 가지고 있다. 각 조각의 무게는 양수이며, 서로 같을 수도 있고 다를 수도 있다. 지민이는 조각을 최대 M번 자를 수 있다. 한 번 자르면 현재 있는 조각 하나를 골라, 무게의 합이 원래 조각의 무게와 같은 두 개의 양수 무게 조각으로 나눈다.

모든 자르기를 마친 뒤 가장 무거운 조각과 가장 가벼운 조각의 무게 차이를 생각하자. 이 차이가 최소가 되도록 할 때의 값을 출력한다.

입력

첫째 줄에 케이크 조각의 개수 N이 주어진다. N은 50보다 작거나 같다.

둘째 줄에 N개 조각의 무게가 주어진다. 각 무게는 1,000,000,000보다 작거나 같은 자연수이다.

셋째 줄에 자를 수 있는 최대 횟수 M이 주어진다. M은 100,000보다 작거나 같은 자연수이다.

출력

가장 무거운 조각과 가장 가벼운 조각의 무게 차이의 최솟값을 출력한다.

절대 오차 또는 상대 오차가 $10^{-9}$ 이하이면 정답으로 인정된다.

예제5

예제 1
입력
```
2
1 3
1
```
예상 출력
```
0.5
```
예제 2
입력
```
5
1 1 1 1 1
4
```
예상 출력
```
0.0
```
예제 3
입력
```
2
1 3
1
```
예상 출력
```
0.5
```
예제 4
입력
```
3
7 11 13
10
```
예상 출력
```
0.3999999999999999
```
예제 5
입력
```
5
13 69 41 37 80
27
```
예상 출력
```
1.4666666666666668
```