Problem C
Inflation
To avoid inflating the balloons by hand, the organisers also bought $n$ helium gas canisters. Each canister can only be used to inflate one balloon, and must be emptied completely into that balloon (it is not possible to disconnect a canister from a balloon before the canister has been fully used).
Unfortunately the gas canisters were bought at a garage sale, and may contain differing amounts of helium. Some may even be empty! To make the best of this challenging situation, the canisters will have to be paired with the balloons smartly.
The organisers want to assign all of the gas canisters to separate balloons, such that the balloon that is inflated the least (relative to its capacity) still contains the maximum possible fraction of helium inside. What is the maximum such (minimum) fraction that is possible?
Balloons filled beyond their capacity will explode. Explosions are upsetting and must be avoided.
Input
The input consists of:
-
One line with the integer $n$ ($1 \le n \le 2\cdot 10^5$), the number of balloons and gas canisters.
-
One line with $n$ integers $c_1, \ldots , c_ n$ ($0 \le c_ i \le n$ for each $i$), the amounts of helium in the gas canisters, in decilitres.
Output
If it is possible to fill all the balloons without any exploding, output the maximum fraction $f$ such that every balloon can be filled to at least $f$ of its capacity. Otherwise, output “impossible”.
Your answer should have an absolute or relative error of at most $10^{-6}$.
| Sample Input 1 | Sample Output 1 |
|---|---|
6 6 1 3 2 2 3 |
0.6 |
| Sample Input 2 | Sample Output 2 |
|---|---|
2 2 2 |
impossible |
| Sample Input 3 | Sample Output 3 |
|---|---|
5 4 0 2 1 2 |
0 |
