Problem Description

At the edge of the earth, a gray-white lighthouse stands along the long coastline. This sea area has complex currents and rugged reefs, yet it is a necessary route for many ships. Without this tall and bright lighthouse to illuminate the way for passing ships, more unfortunate lives might be lost at sea. To oversee this beacon of the sea, a group of well-trained watchers take turns guarding it. The monotonous work day after day is tedious yet cannot afford any mistakes; the tense nerves only relax when the next shift arrives.

Before the普及 of electricity, lighthouses typically used kerosene lamps to guide sailors. Each time kerosene was added to this lighthouse, two watchers needed to carry a barrel with a volume of \( L \); whenever it was Y and S's shift to care for the lighthouse, they were always responsible for refueling it. When transporting kerosene to the lamp room, not filling the barrel to the brim had little impact on the normal operation of the lighthouse, except for the need to make more trips. However, if both watchers were lazy, the problem might not be just about making more trips. Y and S came up with a good plan: they would fill each other's barrels.

There are \( N \) containers in the lighthouse used to transfer stored kerosene into barrels, with the \( i \)-th container having a volume of \( a_i \). Y and S first decide who will fill their barrel first. They take turns filling; when it's a watcher's turn, they randomly select a container with equal probability, fill it to the brim, and pour it all into the other's barrel. Both watchers can end their filling after any number of operations (including zero), but the latter must wait until the former finishes. After Y and S both finish filling, they compare who filled the other's barrel more fully, and then each carries their own barrel to the lamp room. However, if a watcher selects a container and fills the other's barrel to the brim but still has kerosene left in the container, then this unlucky watcher must carry both barrels to the lamp room—which also adds a bit of fun to the monotonous life. Obviously, if the first player's random selection causes an overflow, the second player can fill any amount into the first player's barrel and gloat; thus, we agree that when the first player overflows, they must carry both barrels.

Now, there is only one question left: when Y and S both adopt the optimal strategy to make the other carry more kerosene than themselves, what is the probability that the first player carries no more kerosene than the second player?

Input Format

The first line of input includes two positive integers \( N \) and \( L \), representing the number of transfer containers and the volume of the barrels, respectively.

The second line includes \( N \) positive integers \( a_1, \cdots, a_N \), representing the volume of each transfer container.

Output Format

Output a real number representing the probability that the first player carries no more kerosene than the second player. Your output is considered correct if the absolute error from the standard output does not exceed \( 10^{-6} \).

Sample Input and Output

Sample Input #1

2 4
1 2

Sample Output #1

0.687500000000000000

Sample Input #2

See attached file 2.in

Sample Output #2

See attached file 2.out

Sample Input #3

See attached file 3.in

Sample Output #3

See attached file 3.out

Notes

Sample Explanation 1

It can be proven that the first player's strategy is to fill the other's barrel to the brim, and doing so guarantees a win. The probability of filling the other's barrel exactly after several random selections is:

\[ \left(\frac{1}{2}\right)^2 + \binom{3}{1}\left(\frac{1}{2}\right)^3 + \left(\frac{1}{2}\right)^4 = \frac{11}{16} = 0.6875 \]

Data Range

For \( 100\% \) of the data, it is guaranteed that \( 1 \le N \le 2 \times 10^3 \), \( 1 \le L \le 10^9 \), \( 1 \le a_i \le 2 \times 10^3 \).

Problem Source

From the 2023 Tsinghua University Student Programming Contest and University Invitational (THUPC2023) Preliminary Round.

Solutions and other resources can be found at https://github.com/THUSAAC/THUPC2023-Pre.

见题面 Input 部分

见题面 Output 部分