시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 188 30 19 29.688%

문제

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

입력

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

출력

첫째 줄에 최대 M번 잘라서 가장 무게가 많이 나가는 조각과 적게 나가는 조각의 차이를 가장 작게 만들었을 때, 가장 무게가 많이 나가는 조각과 적게 나가는 조각의 차이를 소수점 10째자리까지 출력한다. 절대/상대 오차는 10-9까지 허용한다.

예제 입력

2
1 3
1

예제 출력

0.5

힌트

출처