P1721 [NOI2016] The King's Drinking Water

The Flea Kingdom has $n$ cities. The great Flea King lives in the capital of the Flea Kingdom, that is, in city $1$. The biggest problem in the Flea Kingdom is drinking water. Because too many fleas live in the capital, and the kind Flea King also gives the water allocated to him to the residents, the Flea King often cannot get water to drink. Therefore, the Flea Kingdom built a cylindrical water tank in every city. These tanks are completely identical and tall enough. After a rainy day, city $i$ collected water with height $h_i$. Due to geographic and weather factors, the water heights collected by any two different cities are all distinct. The Flea King also invited ant craftsmen to help build a large underground connecting system. Each time the Flea King uses the underground connecting system, he can specify any number of cities, connect the tanks of these cities with the underground system for a sufficiently long time, and then turn the system off. By the principle of communicating vessels, after this operation the water in those cities’ tanks will reach the same height, and this height equals the average of the specified tanks’ heights. Because of the complexity of the underground system, the Flea King can use it at most $k$ times. Please tell the Flea King: how high can the water level in the capital’s tank (city $1$) be at most?

The first line contains three positive integers $n,k,p$, representing the number of cities in the Flea Kingdom, the maximum number of times the Flea King can use the underground connecting system, and the required precision of your output. The meaning of $p$ is explained in the Output Format. The next line contains $n$ positive integers describing the water levels in the cities’ tanks after the rain. The $i$-th integer $h_i$ is the water level in city $i$’s tank. It is guaranteed that the $h_i$ are pairwise distinct, and $1 \leq h_i \leq 10^5$.

Output a single real number, the maximum possible water level in city $1$’s tank. This real number may contain only a non-negative integer part, a decimal point, and a fractional part. The non-negative integer part is required and should not have a sign. If there is a fractional part, separate it from the integer part with one decimal point; if there is no fractional part, do not print a decimal point. The number of digits after the decimal point must not exceed $2p$. It is recommended to keep at least $p$ digits. It is guaranteed that the absolute error between the reference answer and the true answer is less than $10^{-2p}$. Your output is judged correct if and only if its absolute error with the reference answer is less than $10^{-p}$. If the absolute error of your output is not less than $10^{-p}$ but less than $10^{-5}$, you can receive $40\%$ of the score for that test point.

### Sample Explanation 1 Since the underground connecting system can be used at most once, there are the following five options: 1. Do not use the underground system: the water level in city $1$’s tank is $1$. 2. Use the system once to connect cities $1$ and $2$: the water level in city $1$’s tank is $5/2$. 3. Use the system once to connect cities $1$ and $3$: the water level in city $1$’s tank is $2$. 4. Use the system once to connect cities $2$ and $3$: the water level in city $1$’s tank is $1$. 5. Use the system once to connect cities $1,2,3$: the water level in city $1$’s tank is $8/3$. ### Sample Explanation 2 The optimal plan is to use the system twice: first connect cities $1$ and $3$, then connect cities $1$ and $2$. ### Sample 3 See the attached file. ### Hint To ensure precision, we generally need to keep more than $p$ decimal digits during computation. We can prove that in the reference solutions for all sub-tasks, if we always keep $\frac{6}{5}p$ decimal digits at any time, then for any input the absolute error of the output will be less than $10^{-p}$. To make it easier to handle high-precision decimals, we provide a fixed-point high-precision decimal class. Contestants may refer to and use this class as needed, or choose not to use it. For specific usage, please refer to the distributed document `decimal.pdf` (see the attachment). ### Constraints ::cute-table{tuack} | Test Point | $n$ | $k$ | $p$ | |:-:|:-:|:-:|:-:| | 1 | $\le 2$ | $\le 5$ | $=5$ | | $2$ | $\le 4$ | ^ | ^ | | $3$ | ^ | ^ | ^ | | 4 | $\le 10$ | $=1$ | ^ | | $5$ | ^ | $=10^9$ | ^ | | $6$ | ^ | $\le 10$ | ^ | | $7$ | ^ | ^ | ^ | | $8$ | $\le 100$ | $=1$ | ^ | | $9$ | ^ | $=10^9$ | $=40$ | | $10$ | ^ | $\le 10^9$ | ^ | | $11$ | ^ | ^ | ^ | | $12$ | ^ | ^ | ^ | | $13$ | $\le 250$ | ^ | $=100$ | | $14$ | $\le 500$ | ^ | $=200$ | | $15$ | $\le 700$ | ^ | $=300$ | | $16$ | ^ | ^ | ^ | | $17$ | ^ | ^ | ^ | | $18$ | $\le 2500$ | ^ | $=1000$ | | $19$ | $\le 4000$ | ^ | $=1500$ | | $20$ | $\le 8000$ | ^ | $=3000$ | Translated by ChatGPT 5