← 返回题目列表

AtCoder · abc008_3

C. 硬币

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

問題文

高桥可以区分正反面。 我有 N 硬币。硬币大小不同,每枚硬币都有 1 正整数被一一写入。

随机分配这些硬币(N! 将组合排列成一行,使它们具有相同的概率。然后执行以下步骤:

  1. 将所有硬币正面朝上。
  2. 从最左边的硬币开始,翻转当前查看的硬币右侧的所有硬币(不包括其本身),这些硬币上写有当前查看的硬币上写的整数的倍数。

高桥先生想知道完成此操作后正面朝上的硬币数量的预期值。

我希望你创建一个程序来计算高桥君处的期望值。


入力

输入将以以下形式从标准输入给出。

N
C_1
C_2
:
C_N
  • 1 行包含一个代表硬币数量的整数。 来自行 N (1 ≦ N ≦ 100) 被给予。
  • 2 从行 N 行数过多 在 i (1 ≦ i ≦ N) 行中,i 最大硬币上写的整数 写入 C_i (1 ≦ C_i ≦ 10^9) 。

部分点

针对此问题设置了部分分数。 满足

  • N ≦ 8 的数据集 如果您正确回答 1 , 给出99 点。
  • 没有附加约束的数据集 如果您正确回答 2 ,那么 1 给出积分,总分 获得 100 点。

出力

打印正面朝上的硬币数量的预期值。绝对误差或相对误差 10^{-6} 或更少是可以接受的。还在输出末尾添加换行符。


入力例1

3
2
4
8

出力例1

2.166666666667

每枚硬币的尺寸按从最小到最小的顺序排列。 写入数字 2 , 4 , 8 。例如,3! 如果硬币按大小升序排列,则将执行以下步骤。

  1. 初始状态下,所有硬币都是正面朝上,所以从左边开始,硬币是[表, 表, 表]。
  2. 接下来,从左边开始 2 之后的币种中, 寻找上面写有2 倍数的硬币。从左边开始 从左起第 2 枚硬币 第 3 枚硬币适用,因此翻转这些硬币。结果,硬币是[表, 裏, 裏]。 只有第
  3. 接下来,从左边开始 3 之后的币种中, 寻找上面写有4 倍数的硬币。从左边开始 从左起第 3 枚硬币是相关的,因此翻转这枚硬币。结果,硬币是[表, 裏, 表]。 只有第

硬币的两面变化如下图所示。在此图中,白色硬币表示为面朝上的硬币,黑色硬币表示为面朝下的硬币。

这样,3! = 6 每条街道排列的最终状态如下图所示。

由上可知,期望值为 13/6 = 2.16666666666... 。


入力例2

4
5
5
5
5

出力例2

2.000000000000

无论你怎么排列,从左到右,[表, 裏, 表, 裏]。 只有第


入力例3

5
2
3
2
6
12

出力例3

3.100000000000