F - Arcs on a Circle Editorial /

Time Limit: 5 sec / Memory Limit: 512 MB

配点 : 2100 点

問題文

長さ C の円周があり、この上に N 本の円弧を配置します。円弧 i の長さは L_i です。

それぞれの円弧 i は、円周上の一様ランダムな位置に配置されます。 すなわち、円周上のランダムな点が選ばれ、その点を中心とした長さ L_i の円弧が出現します。

これらの円弧は、それぞれ独立に配置されます。例えば、円弧が交差したり、ある円弧が別の円弧を含むことがあります。

円周上のすべての点が少なくとも一本の円弧で覆われる確率はいくらでしょうか？ 円弧はその両端も覆うものとします。

制約

  • 2 \leq N \leq 6
  • 2 \leq C \leq 50
  • 1 \leq L_i < C
  • 入力値はすべて整数である。

入力

入力は標準入力から以下の形式で与えられる。

N C
L_1 L_2 ... L_N

出力

円周上のすべての点が少なくとも一本の円弧で覆われる確率を出力せよ。 解答は、絶対誤差が 10^{-11} 以下であれば正答とみなされる。

入力例 1

2 3
2 2

出力例 1

0.3333333333333333

二本の円弧の中心間の距離が 1 以上でなければなりません。長さ 3 の円周上でそのようになる確率は 1 / 3 です。

入力例 2

4 10
1 2 3 4

出力例 2

0.0000000000000000

円弧の長さの合計がちょうど C であり、円周上のすべての点が少なくとも一本の円弧に覆われることはありえますが、この事象の発生確率は 0 です。

入力例 3

4 2
1 1 1 1

出力例 3

0.5000000000000000

入力例 4

3 5
2 2 4

出力例 4

0.4000000000000000

入力例 5

4 6
4 1 3 2

出力例 5

0.3148148148148148

入力例 6

6 49
22 13 27 8 2 19

出力例 6

0.2832340720702695

Score : 2100 points

Problem Statement

You have a circle of length C, and you are placing N arcs on it. Arc i has length L_i.

Every arc i is placed on the circle uniformly at random: a random real point on the circle is chosen, then an arc of length L_i centered at this point appears.

Note that the arcs are placed independently. For example, they may intersect or contain each other.

What is the probability that every real point of the circle will be covered by at least one arc? Assume that an arc covers its ends.

Constraints

  • 2 \leq N \leq 6
  • 2 \leq C \leq 50
  • 1 \leq L_i < C
  • All input values are integers.

Input

Input is given from Standard Input in the following format:

N C
L_1 L_2 ... L_N

Output

Print the probability that every real point of the circle will be covered by at least one arc. Your answer will be considered correct if its absolute error doesn't exceed 10^{-11}.

Sample Input 1

2 3
2 2

Sample Output 1

0.3333333333333333

The centers of the two arcs must be at distance at least 1. The probability of this on a circle of length 3 is 1 / 3.

Sample Input 2

4 10
1 2 3 4

Sample Output 2

0.0000000000000000

Even though the total length of the arcs is exactly C and it's possible that every real point of the circle is covered by at least one arc, the probability of this event is 0.

Sample Input 3

4 2
1 1 1 1

Sample Output 3

0.5000000000000000

Sample Input 4

3 5
2 2 4

Sample Output 4

0.4000000000000000

Sample Input 5

4 6
4 1 3 2

Sample Output 5

0.3148148148148148

Sample Input 6

6 49
22 13 27 8 2 19

Sample Output 6

0.2832340720702695