#P1487. Single-Player Games
Single-Player Games
题目描述
玩游戏时如果有其他人参与会更有趣,但需要他人时他们未必有空,这促使了单人游戏的发明。最著名的例子之一是Windows系统自带的“纸牌”游戏,它可能是全球办公室中浪费时间最多的游戏。
单人游戏的目标通常是通过“移动”达到最终状态,最终状态对应胜利、失败或一个分数。大多数玩家会通过策略优化结果,但本题关注随机游玩的情况——毕竟这类游戏的主要目的是消磨时间,而随机策略同样能达到这一目标。
游戏可以紧凑地表示为(可能无限的)树结构:
- 树的每个节点代表一个游戏状态,根节点是初始状态;
- 内部节点的子节点是一次移动后可能到达的状态;
- 叶节点是最终状态,每个叶节点对应一个分数。
树的定义遵循以下语法:
Definition ::= 标识符 "=" RealTree
RealTree ::= "(" Tree+ ")"
Tree ::= 标识符 | 整数 | "(" Tree+ ")"
标识符 ::= a|b|...|z
整数 ∈ {...,-3,-2,-1,0,1,2,3,...}
通过定义,等号右侧的RealTree
会被赋给左侧的标识符。RealTree
由根节点和一个或多个子节点组成(用括号包裹)。Tree
可以是:
- 某个标识符对应的树;
- 叶节点(单个整数);
- 内部节点(括号包裹的一个或多个子树)。
你的任务是计算随机游玩时的期望分数——即每个内部节点等概率选择子节点时的期望值。只要游戏以概率1结束,期望分数就是有定义的(即使树是无限的)。
输入
输入包含多个游戏树描述:
- 每行开头是整数n,表示使用的标识符数量(取小写字母前n个,如n=2则为a、b);
- 接下来n行是标识符的定义(按a、b、...顺序),定义中可能包含任意空格,但整数内部无空格;
- 输入以n=0结束,该用例不处理。
输出
对每个游戏树描述:
- 先输出游戏编号;
- 按a、b、...顺序输出每个标识符的期望分数,要求精确到小数点后三位。若游戏以概率1结束,输出期望分数;否则输出
Expected score of id undefined
(id为标识符); - 每个测试用例后输出空行。
输入样例
1
a = ((1 7) 6 ((8 3) 4))
2
a = (1 b)
b = (4 a)
1
a = (a a a)
0
输出样例
Game 1
Expected score for a = 4.917
Game 2
Expected score for a = 2.000
Expected score for b = 3.000
Game 3
Expected score for a undefined
题目来源
1998年西南欧洲区域竞赛