Problem F
Pool Filling
You are the owner of a resort with $n$ Olympic-sized pools (equally sized, of course), but some of them might only be partially filled. Thankfully, you have just received a water truck delivering a tank of exactly one Olympic swimming pool’s worth of water. This will let you fill up your pools more!
However, the only way you can transfer water is using a special pump. The two ends of the pump can be connected either to (1) two different pools or (2) the water truck and a pool. After operating the pump, it will equalize the volume of water in the two connected objects. You may use the pump as many times as you want.
The goal is to, after any number of water transfers, maximize the total amount of water in all of your pools at the end.
Input
First line: $1 \leq n < 40$, number of pools.
Second line: $n$ decimal numbers between 0 and 1 inclusive with up to 2 decimal places, representing the portion of each of the $n$ pools that is filled. The values are not given in any particular order.
Output
Ouput one number: the maximum total amount of water you can have in your pools in terms of Olympic-sized swimming pools.
Your answer should have an absolute error or relative error of at most $10^{-5}$.
| Sample Input 1 | Sample Output 1 |
|---|---|
2 0.5 0.5 |
1.375 |
