#P1487. Single-Player Games

    ID: 488 传统题 1000ms 256MiB 尝试: 3 已通过: 1 难度: 10 上传者: 标签>动态规划树结构模拟概率论递推Southwestern European Regional Contest 1998

Single-Player Games

题目描述

玩游戏时如果有其他人参与会更有趣,但需要他人时他们未必有空,这促使了单人游戏的发明。最著名的例子之一是Windows系统自带的“纸牌”游戏,它可能是全球办公室中浪费时间最多的游戏。

单人游戏的目标通常是通过“移动”达到最终状态,最终状态对应胜利、失败或一个分数。大多数玩家会通过策略优化结果,但本题关注随机游玩的情况——毕竟这类游戏的主要目的是消磨时间,而随机策略同样能达到这一目标。

游戏可以紧凑地表示为(可能无限的)树结构:

  • 树的每个节点代表一个游戏状态,根节点是初始状态;
  • 内部节点的子节点是一次移动后可能到达的状态;
  • 叶节点是最终状态,每个叶节点对应一个分数。

树的定义遵循以下语法:

Definition ::= 标识符 "=" RealTree  
RealTree ::= "(" Tree+ ")"  
Tree ::= 标识符 | 整数 | "(" Tree+ ")"  
标识符 ::= a|b|...|z  
整数 ∈ {...,-3,-2,-1,0,1,2,3,...}  

通过定义,等号右侧的RealTree会被赋给左侧的标识符。RealTree由根节点和一个或多个子节点组成(用括号包裹)。Tree可以是:

  • 某个标识符对应的树;
  • 叶节点(单个整数);
  • 内部节点(括号包裹的一个或多个子树)。

你的任务是计算随机游玩时的期望分数——即每个内部节点等概率选择子节点时的期望值。只要游戏以概率1结束,期望分数就是有定义的(即使树是无限的)。

输入

输入包含多个游戏树描述:

  1. 每行开头是整数n,表示使用的标识符数量(取小写字母前n个,如n=2则为a、b);
  2. 接下来n行是标识符的定义(按a、b、...顺序),定义中可能包含任意空格,但整数内部无空格;
  3. 输入以n=0结束,该用例不处理。

输出

对每个游戏树描述:

  1. 先输出游戏编号;
  2. 按a、b、...顺序输出每个标识符的期望分数,要求精确到小数点后三位。若游戏以概率1结束,输出期望分数;否则输出Expected score of id undefined(id为标识符);
  3. 每个测试用例后输出空行。

输入样例

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年西南欧洲区域竞赛