Hide

Problem L
Blooper Game

/problems/bloopergame/file/statement/en/img-0001.png

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

Please log in to submit a solution to this problem

Log in