3. (USACO Dec18)平衡木

【题目描述】

(译者：Satoshi, 转载请注明出处)

为了给谷仓的新畜栏省钱，奶牛贝茜开始在当地的杂戏团表演。通过在很高的平衡木上来回走动来展现她非凡的平衡感。

贝茜每次赚多少钱跟她在最终在平衡木的哪一个位置跳下来有关。平衡木从左到右的位置标为$0,1,..., N+1$。如果贝茜到达了位置$0$或者位置$N+1$她就会从平衡木的一端掉下来并且（很悲伤的）赚不到一分钱。

如果贝茜在一个给定的位置k, 她可以做下面两件事中的一件：

1. 投掷一枚硬币。如果是反面，贝茜移动到位置$k-1$；如果是正面，贝茜移动到位置$k+1$.（正反面的概率各是$\frac {1}{2}$）

2. 从平衡木上跳下来并且获得收入$f(k)$$(0<=f(k)<=10^9)$

因为移动取决于随机投掷硬币，贝茜意识到她不能保证任何特定的收入。然而，根据贝茜开始的位置，她想知道获得收入的最高期望(通过最合适的策略)。比如说，如果她的策略将会有$\frac {1}{2}$的机率赚到$10$块钱，$\frac {1}{4}$的机率赚到$8$块钱，$\frac {1}{2}$的机率赚到$0$块钱，那么她的收入期望将会是加权平均数$10(1/2)+8(1/4)+0(1/4)=7$。

【输入格式】

第一行包含一个正整数$N$。剩下的N行包含$f(1)...f(N)$

【输出格式】

输出$N$行，第$i$行向下取整到收入的$10^5$倍

【样例输入】

2
1
3

【样例输出】

150000 
300000

【提示】

对于27%的数据n<=5000

对于100%的数据n<=100000

大洋里

【来源】

http://www.usaco.org/index.php?page=viewproblem2&cpid=864

USACO Dec 2018 Platinum Division