← 返回题目列表

Codeforces · 28/C

C. 洗澡队列

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

校园里住着n名学生。每天早上,所有学生都在同一时间起床并去洗澡。有m个房间,有洗脸盆。这些房间中的第 i 个房间有一个洗脸盆。每个学生以相同的概率独立选择一个房间并前往该房间。当所有学生选择好自己的房间后,每个房间的学生按照洗手盆的数量分成队列,使最大队列的数量尽可能少。计算所有房间中最大队列大小的期望值。

输入

第一行包含两个正整数 n 和 m (1 ≤ n, m ≤ 50) — 学生数量和房间数量。第二行包含 m 个整数 a1, a2, ... , am (1 ≤ ai ≤ 50)。 ai表示第i个房间的洗手盆数量。

输出

输出单个数:最大队列大小的期望值。您的答案的绝对或相对误差必须小于 10 - 9。

示例

输入 #1

1 1
2

输出 #1

1.00000000000000000000

输入 #2

2 2
1 1

输出 #2

1.50000000000000000000

输入 #3

2 3
1 1 1

输出 #3

1.33333333333333350000

输入#4

7 5
1 1 2 3 1

输出#4

2.50216960000000070000