← 返回题目列表

Codeforces · 97/C

C. 制胜策略

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

一所大学刚刚发现了一项名为 ACM ICPC v2.0 的体育编程竞赛。此次比赛与著名的ACM ICPC没有太大区别,比如参赛者不能参加超过两次决赛。然而,有一个显着的区别:比赛中的队伍应由 n 名参赛者组成。

参加过几次 ACM ICPC v2.0 决赛并没有赢得任何奖牌后,学生和大学校长意识到现在是时候改变准备过程了。具体来说,作为第一个创新,决定改变团队的组建过程。在花费了大量时间研究其他大学表现的统计数据后,他们设法获得了一些有趣的信息:赢得奖牌的概率与过去参加决赛的队伍人数之间的依赖关系。更正式地说,我们知道 n + 1 个实数 p0 ≤ p1 ≤ ... ≤ pn,其中 pi 是如果该队有 i 名参加过往届决赛的选手,且其他 n - i 名选手是第一次进入决赛,则在决赛中获得奖牌的概率。

尽管有这些有用的数据,但大学管理者无法确定这样的团队组建策略,以提供在 ACM ICPC v2.0 决赛中赢得奖牌的平均概率的最大概率(我们应该希望在遥远的未来提供这样的结果,并且我们也应该有源源不断的学生)。那么你呢,你能提供这样的最佳策略吗?在第一阶段,大学管理者想知道最大平均概率的值。

更正式地说,假设大学派出一支队伍参加第 k 届世界决赛。该队有 k 名参加过往届决赛的选手(0 ≤ ak ≤ n)。由于每个人最多只能参加两次决赛,因此必须满足以下条件: $$(\forall k) \; a_k \leq \sum_{i=1}^{k-1} (n - 2a_i)$$。你的任务是选择序列 $$(a_{m})_{m=1}^{\infty}$$ 使得极限 Ψ 存在且其值最大:

$$\Psi = \lim_{m \to \infty} \frac{\sum_{i=1}^{m} p_{a_i}}{m}$$

由于 $$(a_{m})_{m=1}^{\infty}$$ 是无限序列,因此您应该只打印 Ψ 极限的最大值。

输入

第一行包含一个整数n(3≤n≤100),n是团队参与者的数量。第二行包含 n + 1 个实数,小数点后不超过 6 位 pi (0 ≤ i ≤ n, 0 ≤ pi ≤ 1)——如果该队有 i 名已进入决赛的选手,则该队获得奖牌的概率。对于所有 0 ≤ i ≤ n - 1,也应满足条件 pi ≤ pi + 1。

输出

打印唯一的实数——如果使用最优策略,每年赢得奖牌的预期平均数量。结果可能有绝对或相对误差 10 - 6。

示例

输入 #1

3
0.115590 0.384031 0.443128 0.562356

输出 #1

0.4286122500

输入 #2

3
1 1 1 1

输出 #2

0.9999999999

注意

在第二次测试中,无论团队中有哪些参与者,都注定会成功。