Problem Description

At the end of the land, a gray-white lighthouse stands on a long coastline. The currents in this sea area are complex and the reefs are everywhere, yet it is a necessary passage for many routes. Without such a tall and bright lighthouse to light the way for passing ships, perhaps more unfortunate lives would be buried under the sea. To take good care of this beacon on the sea, a group of well-trained keepers take turns on duty here. Day after day, the work is boring but cannot afford any mistakes, and their tense nerves can only relax when the next shift arrives.

Before electricity became common, lighthouses usually used kerosene lamps to guide sailors. Each time fuel is added to this lighthouse, two keepers need to each carry an oil barrel of capacity $L$. Whenever it is the shift group that includes Y and S to take care of the lighthouse, it is always Y and S who are responsible for refueling. When carrying kerosene to the lamp room, not filling the barrel does not affect the normal operation much; it just means making a few more trips. However, if both keepers try to be lazy, the problem may be more than just a few extra trips. Y and S came up with a good idea: to fill oil into each other’s barrels.

In the lighthouse there are $N$ containers used to transfer stored kerosene into the oil barrels. The capacity of the $i$-th container is $a_i$. Y and S first find a way to decide who refuels first. They refuel one after another. When it is one keeper’s turn, each time this keeper randomly selects one container uniformly from all containers, fills it with oil, and pours all of it into the other person’s barrel. Either keeper may stop after any number of operations (possibly 0), but the second player must wait until the first player stops before starting. After both finish, they compare whose barrel has been filled more by the other person, and then each carries their own barrel to the lamp room. However, if at some point a keeper selects a container and fills the other person’s barrel to full, but there is still kerosene left in the container that cannot be poured out, then this unlucky keeper must carry both barrels alone to the lamp room—adding some fun to the monotonous life. Clearly, if the container randomly chosen by the first player would cause overflow, then the second player could pour any amount of kerosene into the first player’s barrel and mock them; therefore, we stipulate that when the first player overflows, the first player must carry both barrels.

Now there is only one question left: when both Y and S use optimal strategies to make the other person carry as much more kerosene as possible than themselves, what is the probability that the kerosene carried by the first player is not more than that carried by the second player?

Input Format

The first line contains two positive integers $N$ and $L$, representing the number of transfer containers and the capacity of the oil barrels.

The second line contains $N$ positive integers $a_1, \cdots, a_N$, representing the capacity of each transfer container.

Output Format

Output a real number representing the probability that the kerosene carried by the first player is not more than that carried by the second player. Your output is considered correct if its absolute error from the standard output does not exceed $10^{-6}$.

2 4
1 2

0.687500000000000000

见附件中的 2.in

见附件中的 2.out

见附件中的 3.in

见附件中的 3.out

Hint

Sample Explanation 1

It can be proven that in this case the first player’s strategy must be to fill the other person’s barrel to full, and if they manage to fill it exactly, they will surely win. After several random selections, the probability of filling the other person’s barrel to exactly full 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$$

Constraints

For $100\%$ of the testdata, 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$.

Source

From the 2023 Tsinghua University Student Algorithm Contest and Intercollegiate Invitational (THUPC2023) Preliminary.

Resources such as the editorial can be found at https://github.com/THUSAAC/THUPC2023-Pre.

Translated by ChatGPT 5