ccf#NOI2016E. 国王饮水记 (Drinking Water)

国王饮水记 (Drinking Water)

Description

In Flea country there are nn cities and the great flea king lives in the capital of the flea country, namely city 11.

The biggest problem in the flea country is drinking water. Because there are too many fleas living in the capital, the flea king compassionately distributes the water allocated to him to the residents of the flea country to drink, which often causes the flea king to go thirsty.

As a result, the Flea nation built a cylindrical water tank in each city. These water tanks are identical and sufficiently high. After a rainy day, the first ii cities have collected a height of hih_i water. Due to the influence of geography and weather, the height of water collected in any two different cities is different from each other.

The flea king also invited ant craftsmen to help, and built a huge underground connection system. Every time the flea king uses the underground connection system, he can connect the water tanks of as many cities as he wants. After connecting the water tanks of these cities with the underground connection system for a long enough time, the underground connection system can be closed. After this operation, the water in the water tanks in all connected cities will reach the same height, and this height is equal to the average of the heights of the specified water tanks.

Due to the complexity of the underground connection system, the flea king can only use kk underground connection system.

Please tell the flea king the highest possible water level in the water tank of city 11 using atmost kk underground connection systems.

Input Format

The first line of input contains three positive integers n,k,pn,k,p, representing the number of cities in the flea country, the maximum number of times the flea king can use the underground connection system, and the accuracy required by the answer you output respectively. The meaning of pp will be explained in the output format.

The next line contains nn positive integers where each positive integer hih_i represents the water level of the ii-th city's water tank after the rain. It is guaranteed that the level of water for two cities is different and 1hi1051 \leq h_i \leq 10^5.

Output Format

Output only one real number in one line, which is the highest possible level in the water tank of city 11.

This real number can only contain non-negative integer part, decimal point, and decimal part. The non-negative integer part is a necessary part, and no sign is added. If there is a decimal part, the non-negative integer part and the decimal part are separated by a decimal point. If there is no decimal part, no decimal point is added.

The real number you output cannot have more than 2p2p digits after the decimal point. It is recommended to keep at least pp bits. Test data guarantees that the absolute error between the reference answer and the real answer is less than 102p10^{-2p}.

Your output is judged to be correct if and only if the absolute error between your output and the reference answer is less than 10p10^{-p}.

If the absolute error between your output and the reference answer is not less than 10p10^{-p} but less than 10510^{-5}, you will get 40%40\% score.

3 1 3
1 4 3
2.666667

Since the underground connection system is used at most once, there are five options:

  1. To not use underground connection system: In this case the water tank level of the city 11 is 11.
  2. Use the one-time connection systemt to connect cities 11,22: In this case the water tank level of the city 11 is 5/25/2.
  3. Use the one-time connection system to connect cities 11,33: In this case the water tank level of the city 11 is 4/24/2.
  4. Use the one-time connection system, connect cities 22,33: In this case the water tank level of the city 11 is 11.
  5. Use the one-time connection system, connect cities 11,22,33: In this case the water tank level of the city 11 is 8/38/3.
3 2 3
1 4 3
3.000000

In this case, the optimal solution is to use two connected systems, the first connection between cities 1,31,3, and the second connection between cities 1,21,2.

Sample 3

See attached files 3.in and 3.out

Constraints

In order to ensure the accuracy of the answer, we generally need to keep more than pp decimal places. It can be proved that if it is guaranteed that in the reference algorithm, at any time the answer is retained with 65p\frac{6}{5}p decimal places, the absolute error between the output obtained for any input and the reference answer is less than 10p10^{-p}.

In order to facilitate the participants to handle high-precision decimals, we provide fixed-point high-precision decimals. Participants can refer to and use this category according to their own needs, or not use this category at all. For specific usage, please refer to the issued document decimal.pdf.

Test Case # nn kk pp
1 2\le 2 5\le 5 =5=5
2 4\le 4
3
4 10\le 10 =1=1
5 =109=10^9
6 10\le 10
7
8 100\le 100 =1=1
9 =109=10^9 =40=40
10 109\le 10^9
11
12
13 250\le 250 =100=100
14 500\le 500 =200=200
15 700\le 700 =300=300
16
17
18 2500\le 2500 =1000=1000
19 4000\le 4000 =1500=1500
20 8000\le 8000 =3000=3000

All test data, satisfies $1 \le n \le 8000,1 \le k \le {10} ^ 9, 3 \le p \le 3000$.