1053 : 射击游戏
- 时间限制Time Limit
- 1 秒Sec
- 内存限制Memory Limit
- 128 兆MB
- 提交次数Submitted
- 11 次Times
- 通过次数Solved
- 6 次Times
标准评测 Standard
从标准输入读入,结果写到标准输出。评测将输出拆成 token,与标准答案逐项比较,不按整段逐字节比对。
Read from standard input and write to standard output. The judge splits the output into tokens and compares them with the official answer; it does not compare raw bytes.
| 比对Compare | token 相同即通过。中间的空格、制表符、换行可多可少。Matching tokens pass. Extra spaces, tabs, or newlines between them are ignored. |
|---|---|
| 不同则错Differs | token 个数或内容不同即错误。23 与 2 3、02 与 2、2.0 与 2 均视为不同。A different token count or value is wrong. 23 vs 2 3, 02 vs 2, and 2.0 vs 2 all differ. |
| 输入Input | 标准输入,格式见题面。Standard input; format as in the statement. |
| 输出Output | 标准输出。Standard output. |
| 时间与内存Time and memory | 记这一份程序的 CPU 时间和内存峰值。题目上的时间限制、内存限制就是这一份的上限。The record is this program’s CPU time and peak memory. The limits on the problem apply to this one run. |
题目描述Description
A和B在玩一个射击游戏,战场由若干单位正方形积木组成。积木占据了连续的若干列,且图形周长等于它最小包围矩形的周长。下图(a)是一个合法的战场,但(b)和(c)都不是:(b)中有空列;(c)的图形周长为14,而最小包围矩形(用虚线画出)的周长为12。受重力影响,每个积木的正下方要么是地面,要么是另一个积木。为了让战场看上去错落有致、玩着更刺激,它不能恰好是一个矩形(即:不能每列积木都一样高)。

游戏规则如下:
- A和B轮流射击,A先射击。
- 每次射击时,首先选择一行(该行必须至少有一个积木),以及“左”和“右”中的一个方向,然后往这个方向开火。子弹的威力为1~3的均匀随机整数(即:威力为1、2、3的概率各为1/3),表示子弹能打掉的积木个数,被打掉的积木将直接从战场中消失。如果该行的积木个数小于威力值,则子弹将在打掉该行所有积木后消失。例如,若选择往右射击从下往上数第3行,且威力为2,且这一行一共有4个积木,则最左边的两个积木将被打掉。注意:这两个积木可以不连续。
- 每次射击完成后,悬空的积木垂直往下落。所有积木不再下落后,下一位选手才能开始射击。
- 谁打掉了最后一个积木,谁就获胜。
假定开局是
,根据规则1,A先开火。射击后,B可能面临的后续局面中的其中三个如下表:
| 行编号 (从下往上数) |
子弹前进方向 | 威力(随机值) | 刚射击后 | 积木稳定后 |
|---|---|---|---|---|
| 2 | 从右往左 | 1 | ![]() |
同左图 |
| 1 | 从右往左 | 2 | ![]() |
![]() |
| 1 | 从左往右 | 3 | ![]() |
![]() |
假定A和B都足够聪明,采取让自己获胜概率尽量高的策略,你的任务是计算出A获胜的概率。
输入格式Input
输入文件最多包含25组测试数据,每个数据仅包含两行,第一行是整数n(1<=n<=6),即积木的列数。第二行包含n个正整数h1, h2,…, hn(1<=hi<=6),表示从左往右数第i列的高度。积木的排列方式保证符合题目描述(即:图形周长等于它最小包围矩形的周长,且各列的高度不全相同)。n=0表示输入结束,你的程序不应当处理这一行。
输出格式Output
对于每组数据,输出仅一行,即A获胜的概率,四舍五入保留六位小数。
样例Sample
出题Author
SRbGa
来源Source
湖南省第六届大学生计算机程序设计竞赛(HNCPC2010)
题目到此结束End of problem




