J-小C的学习计划_第十一届"图灵杯"NEUQ-ACM程序设计竞赛

时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小C是一个热爱学习的孩子，但是他却不知道该如何进行高效的学习，浪费了很多的学习时间，因此他每天都学的十分苦恼。

在某一天中，小C一共有 $n$ 门课程可供选择，第 $i$ 门课程的重要程度为 $a_i$ ，小C的目标是学够重要程度之和不少于 $m$ 的课程，只有完成目标小C才会停止进行学习。

但是小C不知道该按照什么样的顺序进行课程的学习，因此，他决定每次从所有的课程（不论之前是否学过这门课）中随机选择一门来进行一次的学习。也就是说，在一次的学习中，小C会从 $n$ 门课程中，等概率的选取其中一门课程来进行学习，并且可能会重复学习同一门课程，尽管这样做毫无意义。

现在，小C想知道，自己完成这一天的学习目标的期望学习次数是多少（答案四舍五入保留到小数点后6位）。

输入的第一行包含两个整数 $n(1\leq n \leq 20)$ 和 $m(1 \leq m \leq 10 ^ 9)$ ，分别表示课程数量和学习目标。

输入的第二行包含 $n$ 个整数 $a_i(1 \leq a_i \leq 10^8)$ ，表示每门课程的重要程度。

数据保证 $m\leq \sum\limits_{i=1}^na_i$ 。

输出一个 $6$ 位小数 $ans$ ，表示小C完成这一天的学习目标的期望学习次数。

示例1

复制

2 2
1 2

复制

2.000000

对于样例1，

进行1次学习的概率为 $\frac{1}{2}$ ，

进行2次学习的概率为 $\frac{1}{4}$ ，

……，

进行n次学习的概率为 $\frac{1}{2^n}$ ，

因此答案 $ans = \sum\limits_{i=1}^{\infty} \frac{i}{2^i} = 2.000000$

示例2

复制

2 3
1 2

复制

3.000000

示例3

复制

4 10
1 2 3 4

复制

8.333333