1인용 게임

게임은 여러 사람이 함께할 때 가장 재미있지만, 함께할 상대가 늘 있는 것은 아니다. 그래서 혼자 하는 게임(1인용 게임)이 만들어졌다. 가장 잘 알려진 예는 사무실에서 수많은 시간을 허비하게 만든 고전 게임 "솔리테어(Solitaire)"다.

1인용 게임의 목표는 보통 승패나 점수가 정해지는 최종 상태에 도달할 때까지 수(move)를 두는 것이다. 대부분의 플레이어는 좋은 전략으로 결과를 최적화하려 한다. 이 문제에서는 대신 무작위로 플레이할 때 어떤 일이 일어나는지를 다룬다. 시간을 보내는 용도라면 무작위 플레이도 다른 전략만큼 충분하다.

게임은 (무한할 수도 있는) 트리로 간결하게 표현된다. 트리의 각 노드는 하나의 게임 상태이고, 루트는 시작 위치다. 내부 노드의 자식들은 한 번의 수로 이동할 수 있는 상태들이다. 잎(leaf) 노드는 최종 상태며, 각 잎에는 정수 점수가 매겨진다. 이 값이 그 잎에서 게임이 끝났을 때 얻는 점수다.

트리는 다음 문법으로 정의된다.

Definition ::= Identifier "=" RealTree
  RealTree ::= "(" Tree+ ")"
      Tree ::= Identifier | Integer | "(" Tree+ ")"
Identifier ::= a | b | ... | z
   Integer  ∈  {..., -3, -2, -1, 0, 1, 2, 3, ...}

정의(Definition)는 오른쪽의 RealTree를 왼쪽의 식별자(Identifier)에 대입한다. RealTree는 루트 노드와, 대괄호로 감싼 하나 이상의 자식들로 이루어진다. Tree는 다음 중 하나다.

• 식별자가 가리키는 트리,
• 정수 하나로 표현되는 잎 노드, 또는
• 하나 이상의 Tree(자식들)를 대괄호로 감싼 내부 노드.

무작위로 플레이할 때의 기댓값 점수를 구하여라. 즉, 모든 내부 노드에서 자식 하나를 균등한 확률로 선택한다. 게임이 확률 1로 끝나기만 하면, 이 기댓값은 여기서 정의 가능한 무한 트리에 대해서도 잘 정의된다.

입력은 여러 개의 게임 트리 설명으로 이루어진다. 각 설명은 그 설명이 사용하는 식별자 개수 n이 적힌 줄로 시작한다. 식별자는 알파벳 앞에서부터 n개의 소문자다. 이어지는 n개의 줄에는 이 식별자들의 정의가 a, b, ... 순서로 주어진다. 정의에는 임의의 공백이 들어갈 수 있으나(단, 하나의 정수 안에는 공백이 없다), 정의의 오른쪽에는 앞에서부터 n개의 소문자 식별자만 사용된다.

입력은 n이 0인 설명으로 끝난다. 이 설명은 처리하지 않는다.

각 게임 트리 설명마다 먼저 Game k를 출력한다. 여기서 k는 설명의 번호이며 1부터 시작한다. 그다음, n개의 식별자를 a, b, ... 순서로 각각 한 줄씩 출력한다.

• 해당 식별자의 트리가 확률 1로 끝난다면, Expected score for <id> = <value>를 출력한다. <value>는 무작위 플레이의 기댓값 점수를 소수점 아래 셋째 자리까지 반올림한 값이다.
• 그렇지 않다면 Expected score for <id> undefined를 출력한다.

연속한 두 게임 사이에는 빈 줄을 하나 출력한다.