Arcs on a Circle

AtCoder

IDagc020_f

Time5000ms

Memory256MB

Difficulty—

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$ [samples]

Samples

Input #1

2 3
2 2

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$.

Input #2

4 10
1 2 3 4

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$.

Input #3

4 2
1 1 1 1

Output #3

0.5000000000000000

Input #4

3 5
2 2 4

Output #4

0.4000000000000000

Input #5

4 6
4 1 3 2

Output #5

0.3148148148148148

Input #6

6 49
22 13 27 8 2 19

Output #6

0.2832340720702695

API Response (JSON)

{
  "problem": {
    "name": "Arcs on a Circle",
    "description": {
      "content": "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, t",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 5000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "agc020_f"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You have a circle of length $C$, and you are placing $N$ arcs on it. Arc $i$ has length $L_i$.\nEvery arc $i$ is placed on the circle uniformly at random: a random real point on the circle is chosen, t...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments