Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

You have a jug and $n$ mugs. The jug’s capacity is $c$ liters and the $i^{th}$ mug’s capacity is $a_i$ liters. Initially, the jug is filled with water.

You run a shop. When a customer asks for water, you have to follow these two steps sequentially:

You throw out all the mugs that have a capacity greater than the amount of water in the jug. If there are no mugs left, you close the shop. Otherwise, you go to step $2$.

From the mugs you presently have, you choose a mug $j$ uniformly at random. After that, you fill the mug with $a_j$ liters of water from the jug and give it to the customer. So, the water in the jug reduces by $a_j$ liters. For some weird reason, the customers never give back the mugs to you. As a result, you become angry and throw out all the mugs that have the capacity $\leq a_j$ liters.

What is the expected number of times you can serve the customers? **Note that, the customers come to your shop until you close your shop.**

Input starts with an integer $T(1\leq T\leq 100)$, the number of test cases.

In each test case, the first line contains two space-separated integers $n$ and $c$, the number of mugs, and the jug's capacity.

The next line contains $n$ space-separated integers. The $i^{th}$ integer $a_i (1\leq a_i\leq c)$ denotes the capacity of the $i^{th}$ mug.

**Scoring**

Subtask 1 (35 Points):

$1\leq n\leq 100$

$1\leq c\leq 300$

Subtask 2 (65 Points):

$1\leq n, c\leq 10^4$

The sum of $n$ over all test cases doesn’t exceed $10^4$.

For each test case, in a line, print the expected number of times you can serve the customers. Your answer will be considered correct if the absolute or relative error doesn’t exceed $10^{-6}$.

Formally, let's assume that your answer is $x$, and the answer of the jury is $y$. Your answer will be considered correct if and only if $\frac{\lvert x-y \lvert}{max(1,\lvert y \lvert)}\leq 10^{-6}$.

Input | Output |
---|---|

2 3 10 10 3 6 2 5 5 5 | 1.333333 1.000000 |

**Sample Case 1 Explanation:**

There are only $3$ scenarios:

**Scenario** $1$:

You give mug $1$ to the $1^{st}$ customer. Then you'll throw all other mugs as their capacity is less than mug $1$.

**Scenario** $2$:

You give mug $2$ to the $1^{st}$ customer. As there are no mugs that have a capacity less or equal to mug $2$'s capacity, you won't throw out any. The jug has now $7$ liters of water.

When the $2^{nd}$ customer asks for water, you'll throw out mug $1$ as its capacity is greater than the present amount of water in the jug. Then only mug $3$ is left and you will give it to this customer.

**Scenario** $3$:

You give mug $3$ to the $1^{st}$ customer. As mug $2$'s capacity is less than mug $3$'s capacity, you'll throw out mug $2$. The jug has now $4$ liters of water.

When the $2^{nd}$ customer asks for water, you'll throw out mug $1$ as its capacity is greater than the present amount of water in the jug. As there are no mugs left, you'll close the shop and the $2^{nd}$ customer won't be served.

So, the expected number of times you can serve the customers is = $\frac{1}{3}\times1 + \frac{1}{3}\times2 + \frac{1}{3}\times1 = 1.333333$

0% Solution Ratio

Login to submit

To know about expected value, you can read this. Subtask 1: At first, let’s sort the array of the mu...

Toph uses cookies. By continuing you agree to our Cookie Policy.