Practice on Toph

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

No Expectations!

By shefin · Limits 1s, 512 MB

You have a jug and nn mugs. The jug’s capacity is cc liters and the ithi^{th} mug’s capacity is aia_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:

  1. 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 22.

  2. From the mugs you presently have, you choose a mug jj uniformly at random. After that, you fill the mug with aja_j liters of water from the jug and give it to the customer. So, the water in the jug reduces by aja_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 aj\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

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

In each test case, the first line contains two space-separated integers nn and cc, the number of mugs, and the jug's capacity.
The next line contains nn space-separated integers. The ithi^{th} integer ai(1aic)a_i (1\leq a_i\leq c) denotes the capacity of the ithi^{th} mug.

Scoring

Subtask 1 (35 Points):
1n1001\leq n\leq 100
1c3001\leq c\leq 300

Subtask 2 (65 Points):
1n,c1041\leq n, c\leq 10^4
The sum of nn over all test cases doesn’t exceed 10410^4.

Output

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 10610^{-6}.

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

Sample

InputOutput
2
3 10
10 3 6
2 5
5 5
1.333333
1.000000

Sample Case 1 Explanation:

There are only 33 scenarios:

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

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

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

Scenario 33:
You give mug 33 to the 1st1^{st} customer. As mug 22's capacity is less than mug 33's capacity, you'll throw out mug 22. The jug has now 44 liters of water.

When the 2nd2^{nd} customer asks for water, you'll throw out mug 11 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 2nd2^{nd} customer won't be served.

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

    Discussion

    Statistics


    0% Solution Ratio

    Submit

    Login to submit

    Editorial

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

    Related Contests

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