/* Problem I: Single-Player Games
 * Author:    Mark Dettinger
 *
 * Algorithm:
 * Each tree definition yields one linear equation in a,b,...z.
 * The expected value for a given tree t is determined by solving the
 * linear equation system that contains the equations of the trees on
 * which t depends. If the determinant of this system is zero, the value
 * is undefined.
 */

#include <stdio.h>
#include <ctype.h>
#include <math.h>
#include <assert.h>

#define EPS (1E-9)
#define DBG(x)

typedef struct { double coeff[32]; } polynom;

FILE *input;
int game=0;              /* number of game */
double a[32][32];        /* the linear equation system */
int num_equations;       /* number of equations */
double b[32][32];        /* sub-system */
int n;                   /* equations in sub-system */
int p;                   /* read head position during parsing */
char s[1000];            /* tree definition during parsing */
int depends_on[32][32];  /* dependencies between identifiers */

void ws() { while (s[p] && isspace(s[p])) p++; }

polynom tree (int i)
{
  polynom result;
  int j;

  DBG(printf("enter tree at position %c\n",s[p]));
  for (j=0; j<=num_equations; j++)
    result.coeff[j] = 0.0;
  if (s[p]=='(')
    {
      int length;
      polynom q,sum;

      p++;
      ws();
      for (j=0; j<=num_equations; j++)
	sum.coeff[j] = 0.0;
      for (length=0; s[p]!=')'; length++)
	{
	  q = tree(i);
	  for (j=0; j<=num_equations; j++)
	    sum.coeff[j] += q.coeff[j];
	}
      p++;
      ws();
      for (j=0; j<=num_equations; j++)
	result.coeff[j] = sum.coeff[j]/length;
    }
  else if (isalpha(s[p]))
    {
      result.coeff[s[p]-'a'] = 1.0;
      depends_on[i][s[p]-'a'] = 1;
      p++;
      ws();
    }
  else if (s[p] == '-' || isdigit(s[p]))
    {
      sscanf(s+p,"%lf",&result.coeff[num_equations]);
      while (s[p] && (s[p] == '-' || isdigit(s[p]))) p++;
      ws();
    }
  else
    {
      printf("error!\n");
      assert(0);
    }
  return result;
}

void print_matrix()
{
  int i,j;

  for (i=0; i<num_equations; i++)
    {
      for (j=0; j<=num_equations; j++)
	printf("%7.3f",a[i][j]);
      printf("\n");
    }
}

void print_matrix2()
{
  int i,j;

  for (i=0; i<n; i++)
    {
      for (j=0; j<=n; j++)
	printf("%7.3f",b[i][j]);
      printf("\n");
    }
}

int read_case()
{
  polynom q;
  char c;
  int i,j;

  fscanf(input,"%d",&num_equations);
  while (fgetc(input)!='\n');
  if (num_equations==0) return 0;
  DBG(printf("%d equations\n",num_equations));
  for (i=0; i<num_equations; i++)
    {
      for (j=0; j<num_equations; j++)
	depends_on[i][j] = 0;
      depends_on[i][i] = 1;
      assert(fscanf(input,"%c = %[^\n] ",&c,s)==2);
      DBG(printf("%s\n",s));
      p = 0;
      q = tree(i);
      for (j=0; j<=num_equations; j++)
	a[c-'a'][j] = q.coeff[j];
      a[c-'a'][c-'a'] -= 1.0;
      a[c-'a'][num_equations] = -a[c-'a'][num_equations];
    }
  DBG(print_matrix());
  return 1;
}

void solve_case()
{
  int i,j,k,i2,j2,i3,eq,pivot;
  int used[32];
  double x[32],tmp;

  printf("Game %d\n",++game);

  /* compute indirect dependencies with Floyd-Warshall */
  for (k=0; k<num_equations; k++)
    for (i=0; i<num_equations; i++)
      for (j=0; j<num_equations; j++)
	depends_on[i][j] |= depends_on[i][k] && depends_on[k][j];

  for (eq=0; eq<num_equations; eq++) /* for each equation */
    {
      /* determine used variables */
      n = 0;
      DBG(printf("used vars:"));
      for (j=0; j<num_equations; j++)
	{
	  used[j] = depends_on[eq][j];
	  n += used[j];
	  DBG(if (used[j]) printf(" %c",j+'a'));
	}
      DBG(printf("\n"));
      
      /* create sub-matrix b that only contains used variables */
      for (i=i2=0; i<num_equations; i++)
	if (used[i])
	  {
	    for (j=j2=0; j<=num_equations; j++)
	      if (used[j] || j==num_equations)
		{
		  b[i2][j2] = a[i][j];
		  j2++;
		}
	    if (i==eq) i3=i2; /* save index */
	    i2++;
	  }
	      
      /* gaussian elimination: forward phase*/
      for (j=0; j<n; j++)
	{
	  /* find pivot row */
	  pivot = j;
	  for (i=pivot+1; i<n; i++)
	    if (fabs(b[i][j])>fabs(b[pivot][j]))
	      pivot = i;
	  /* exchange row j and pivot row */
	  for (k=0; k<=n; k++)
	    {
	      tmp = b[j][k];
	      b[j][k] = b[pivot][k];
	      b[pivot][k] = tmp;
	    }
	  if (fabs(b[j][j])<EPS) /* determinant of matrix is zero */
	    {
	      printf("Expected score for %c undefined\n",eq+'a');
	      goto finished;
	    }
	  /* eliminate */
	  for (i=j+1; i<n; i++)
	    for (k=n; k>=j; k--)
	      b[i][k] -= b[i][j]*b[j][k]/b[j][j]; 
	}

      /* gaussian elimination: backward phase*/
      for (j=n-1; j>=0; j--)
	{
	  x[j] = b[j][n]/b[j][j];
	  for (i=j-1; i>=0; i--)
	    {
	      b[i][n] -= x[j]*b[i][j];
	      b[i][j] = 0;
	    } 
	}
      DBG(print_matrix2());
    
      /* print result */
      printf("Expected score for %c = %.3f\n",eq+'a',x[i3]);
    finished:
    }
  printf("\n");
}

int main()
{
  input = fopen("games.in","r");
  assert(input!=NULL);
  while (read_case()) solve_case();
  fclose(input);
  return 0;
}