물 마시기

길이가 $n$인 실수 배열이 있다. $i$번째 실수는 $h_i$이다. 처음에 모든 $h_i$는 서로 다르다고 보장된다.

한 번의 연산에서는 원하는 개수만큼 $h_i$를 고르고, 고른 각 $h_i$의 값을 고른 수들의 평균으로 바꿀 수 있다. 고르는 수들이 서로 인접할 필요는 없다. 예를 들어 $h_1$과 $h_3$을 고르고 $h_2$는 고르지 않을 수 있다. 연산은 최대 $k$번까지 적용할 수 있다.

가능한 $h_1$의 최댓값을 구한다.

첫 줄에 양의 정수 $n$, $k$, $p$가 주어진다. 각각 배열의 길이, 연산 횟수의 상한, 요구되는 정밀도이다.

둘째 줄에는 양의 정수 $n$개가 주어진다. $i$번째 정수가 $h_i$이다. 모든 $h_i$는 서로 다르며, $1 ≤ h_i ≤ 10^5$이다.

가능한 $h_1$의 최댓값을 실수로 한 줄에 출력한다. 정수부는 반드시 출력하고, 소수부가 있을 때만 소수점을 쓴다. 소수점 아래는 최대 $2p$자리까지 허용되며, 최소 $p$자리를 출력하는 것을 권장한다. 참조 정답과 실제 정답의 절대 차이는 $10^{-2p}$ 이하로 보장된다.

출력과 참조 정답의 절대 차이가 $10^{-p}$보다 작으면 정답이다. 차이가 $10^{-p}$ 이상이고 $10^{-5}$보다 작으면 해당 테스트 케이스 점수의 40%를 받는다.

모든 테스트 케이스에 대해 $3 ≤ p ≤ 3000$, $1 ≤ n ≤ 8000$, $1 ≤ k ≤ 10^9$이다.

정확도를 보장하려면 가능한 한 $p$자리보다 많은 소수점 아래 자릿수를 유지하며 산술 연산을 해야 한다. 각 연산에서 소수점 아래를 최대 $\frac{6}{5}p$자리까지만 유지해도, 각 부분 문제의 참조 풀이는 출력과 참조 정답의 절대 차이를 $10^{-p}$보다 작게 유지한다는 것이 알려져 있다.

고정밀 부동소수점 라이브러리 library.zip이 제공된다. 사용은 선택 사항이다.

Decimal 라이브러리는 고정밀 부동소수점의 덧셈, 뺄셈, 곱셈, 나눗셈, 비교와 double, 정수, 문자열과의 상호 변환을 지원한다. 곱셈과 나눗셈에서는 한쪽 피연산자가 반드시 정수여야 한다. Decimal끼리는 곱하거나 나눌 수 없다.

라이브러리는 상수 $P$를 정의하며, 각 연산의 절대 오차는 최대 $10^{-P}$이다. C++ 버전에서는 drink_sample.cpp의 9번째 줄 const int PREC = 2100;이 $P$를 정한다. C 버전에서는 drink_sample.c의 9번째 줄 #define PREC 2100이, Pascal 버전에서는 drink_sample.pas의 8번째와 14번째 줄의 2100이 $P$이다. $P$를 바꾸려면 두 곳을 같은 값으로 고친다. 각 연산의 시간 복잡도는 $O(P)$이고, Decimal 인스턴스 하나의 공간 복잡도는 최대 $\frac{4P}{9}+16$바이트이다.

Decimal 함수를 호출할 때는 다음 조건을 지켜야 한다.

• 중간 단계의 Decimal 값의 절댓값은 $10^{18}$ 이하이다.
• int와 longint 인자의 절댓값은 $10^9$ 이하이다.
• long long과 int64 인자의 절댓값은 $10^{18}$ 이하이다.
• double 인자는 유효한 실수이고, 절댓값은 $10^9$ 이하이다.
• string 인자는 유효한 실수를 나타내야 한다. 음수는 부호로 시작하고 음이 아닌 수는 부호가 없다. 그 뒤에 정수부, 소수점, 소수부가 온다. 소수점과 소수부는 함께 생략할 수 있다. 절댓값은 $10^9$ 이하이다.
• 0으로 나눌 수 없다.
• Decimal을 문자열로 바꿀 때 소수점 아래 자릿수는 0보다 커야 한다. C에서는 to_string_d(Decimal, char*, int)가 반환하는 문자열을 담을 공간을 충분히 할당해야 한다.

drink_sample.cpp/c/pas는 라이브러리만 포함된 빈 프로그램이다. 이를 바로 수정해서 작업해도 되고, 그렇지 않아도 된다. decimal_test.cpp/c/pas는 Decimal 라이브러리의 사용법과 각 함수의 동작을 익히는 예제 프로그램이다.