#P5198. [NWERC2017]English Restaurant

    ID: 2265 传统题 1000ms 512MiB 尝试: 17 已通过: 9 难度: 8 上传者: 标签>难度分类提高+/省选-动态规划区间 DP枚举最后一次操作计数 DP线性 DP组合数学Pascal 递推CF2500

[NWERC2017]English Restaurant

[NWERC2017] English Restaurant

一家餐馆有n张桌子,第i张桌子的座位数为c_i。

在一段时间里,先后一共有t群人来到餐馆,任意两群人来的时间不会一样,你可以认为他们来的时间相差非常大。

每群人的人数都在1到g之间等概率随机,这群人会找到一张座位数最少的,且可以容纳下这群人的,同时没有被其它人占据的桌子。

如果找不到这样的桌子,他们就会失望地离开餐馆。

一旦他们坐下了,他们就会一直用餐直到餐馆打烊。

比如有3张桌子,容量分别为5,8,9。如果先后来了人数分别为5,10,3的3群人,最终会有8个人用餐。

第一群人占据容量为5的桌子,第二群人失望地离开,第三群人占据容量为8的桌子。

请计算假如t群人每群人的人数都在1到g之间等概率随机,那么最后会留在餐馆用餐的人数的期望值是多少呢?

输入输出格式

输入格式

从标准输入读入。第一行三个正整数 n,g,tn,g,t(1≤n≤1001\le n\le100,1≤g≤2001\le g\le200,1≤t≤1001\le t\le100)。

第二行 nn 个正整数 c1,c2,…,cnc_1,c_2,\ldots,c_n(1≤ci≤2001\le c_i\le200),表示各桌容量。

输出格式

向标准输出写出一行一个实数,表示最终用餐人数的期望。绝对或相对误差小于 10−610^{-6} 即可。

样例

样例输入

3 3 2
1 2 3

样例输出

3.666666667