比赛场次 619
比赛名称 2024暑假C班集训9
比赛状态 已结束比赛成绩
开始时间 2024-07-09 08:00:00
结束时间 2024-07-09 12:00:00
开放分组 全部用户
注释介绍
题目名称 (USACO Dec18)平衡木
输入输出 balance_beam.in/out
时间限制 1000 ms (1 s)
内存限制 256 MiB
测试点数 11 评测插件
用户 结果 时间 内存 得分
Gravatar┭┮﹏┭┮ AAAAAAAAAAA 0.116 s 5.56 MiB 100
GravatardarkMoon AAAAAAAAAAA 0.166 s 6.39 MiB 100
Gravatar李奇文 AAAAWWWWWWW 2.194 s 5.32 MiB 36
Gravatarliuyiche AWWWWWWWWWW 0.000 s 0.00 MiB 9
Gravatardream AWTTTTTTTTT 9.005 s 6.25 MiB 9
Gravatar健康铀 RRRRRRRRRRR 0.000 s 0.00 MiB 0

(USACO Dec18)平衡木

★★★☆   输入文件:balance_beam.in   输出文件:balance_beam.out   评测插件
时间限制:1 s   内存限制:256 MiB

【题目描述】

(译者: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