Problem L
Blooper Game
Mario is competing in the most important elimination game of his entire life. He has been given a dalgona cookie, which is a cookie made out of caramelized sugar, that has a shape with $N$ sides etched into its surface. He also have a sewing needle that he is using to cut out the shape that is on the cookie. It sounds easy enough but if he messes up any of the edges and breaks the cookie, he will be inked by a Blooper and eliminated. As it currently stands, if he tries to cut an edge of length $s$ from the shape, he has a probability of $\frac{1}{s}$ of succeeding at the cut. The chances of him successfully cutting every edge, and thus cutting out the shape from the cookie, is quite slim so he devises a strategy to succeed. At any point in time, he can lick a single edge of the shape, and by licking away some of the sugar, this raises the probability of cutting that edge to the $P$-th power $(0 < P < 1)$, thus improving his chances at avoiding the icky inkage. Mario can also lick the same edge multiple times if he thinks that will be optimal, in which case the probability of cutting that edge is raised to the $P$-th power for every lick. However, time is running out so he can only lick $L$ times before time runs out. What is the maximum probability of avoiding the icky inkage after time runs out?
Input
The first line of input contains two integers $N$ $(3
\leq N \leq 100\, 000)$ and $L$ $(0
\leq L \leq 10^9)$ and a real number $P$ $(0
< P < 1)$, representing the number of sides of the
shape that is etched into the cookie, the number of licks Mario
can make before time runs out, and the power that each side’s
probability is raised to after a lick respectively.
$P$ will contain at most
$7$ digits after the
decimal point.
Another $N$ lines follow
with a single integer $s_
i$ $(1 \leq s_ i \leq
10^9)$ representing a side length of the cookie. Note
that the sides are not necessarily straight, so these side
lengths may not necessarily follow the triangle inequality.
Output
Output one line containing a single real number $d$ equal to the maximum probability of avoiding getting inked, assuming he uses his licks wisely. Your answer should not exceed an absolute or relative error of $10^{-6}$.
Sample Input 1 | Sample Output 1 |
---|---|
3 1 0.5 2 2 2 |
0.1767767 |
Sample Input 2 | Sample Output 2 |
---|---|
10 10 0.25 7 7 5 1 9 1 9 5 2 6 |
0.0690066 |