← 返回题目列表

Codeforces · 261/B

B. 马克西姆和餐厅

中文机器翻译题面 查看原题

马克西姆开了自己的餐厅! The restaurant has got a huge table, the table's length is p meters.

Maxim今晚有一个晚宴,有n位客人会来找他。让我们从 1 到 n 对 Maxim 餐厅的客人进行索引。马克西姆知道所有来找他的客人的规模。 The i-th guest's size (ai) represents the number of meters the guest is going to take up if he sits at the restaurant table.

晚饭前很久,客人们就在餐厅门前按照某种顺序排起了长队。然后马克西姆让客人一一进来。当餐厅餐桌上没有座位可以容纳排队的其他客人时,Maxim 就会停止让客人进来。如果餐厅中所有客人的人数加上队列中该客人的人数之和大于 p,则餐厅餐桌上没有位置可供队列中的其他客人使用。在这种情况下,为了不冒犯餐桌上没有座位的客人,Maxim 不会让任何其他客人进入餐厅,即使队列中的以下客人之一可以坐在餐桌上。

Maxim 现在想知道,在所有可能的 n! 情况下,来到餐厅的平均访客数量是多少?队列中客人的顺序。帮助Maxim,计算这个数字。

输入

第一行包含整数 n (1 ≤ n ≤ 50) — 餐厅的客人人数。 The next line contains integers a1, a2, ..., an (1 ≤ ai ≤ 50) — the guests' sizes in meters. The third line contains integer p (1 ≤ p ≤ 50) — the table's length in meters.

行中的数字由单个空格分隔。

输出

在一行中打印一个实数——问题的答案。如果绝对误差或相对误差不超过 10 - 4,则答案将被视为正确。

示例

输入 #1

3
1 2 3
3

输出 #1

1.3333333333

注意

在第一个示例中,人员将按以下顺序出现:

- (1, 2, 3) — there will be two people in the restaurant;
- (1, 3, 2) — 餐厅内将有一个人;
- (2, 1, 3) — there will be two people in the restaurant;
- (2, 3, 1) — 餐厅内将有一个人;
- (3, 1, 2) — there will be one person in the restaurant;
- (3, 2, 1) — there will be one person in the restaurant.

总共我们得到 (2 + 1 + 2 + 1 + 1 + 1) / 6 = 8 / 6 = 1.(3)。