Problem C
Inflation

To avoid inflating the balloons by hand, the organisers also
bought
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
( ), the number of balloons and gas canisters. -
One line with
integers ( for each ), 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
Your answer should have an absolute or relative error of at
most
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 |