Отримання знань

   Входные данные

   Выходные данные

   Пример входных данных

   Пример выходных данных

   Анализ условия и обсуждение идеи решения

   Пример решения на C++:

#include "iostream" 
#include "stdio.h" 
#include "stdlib.h" 
#include "string.h" 
#define MAXNUM 101
#define max(a,b)    (((a) > (b)) ? (a) : (b))
#define min(a,b)    (((a) < (b)) ? (a) : (b))
struct Struction
{
 int lValue;
 int a,b;
 int op;
 bool type_1,type_2;
};
void ParseLine(char * line,Struction * pro,int rIdx,int & idxMax);
void CalExpection();
double d[2][14][MAXNUM];
double p[2][MAXNUM];
Struction program_1[MAXNUM],program_2[MAXNUM];
int xMax,yMax,sumMax,varCon,curr,prev;
char cmdLine[256];
char var[10][24];
int main()
{
 int loop;
 gets(cmdLine);
 loop = atoi(cmdLine);
 while(loop--)
 {
  varCon = 0;
  xMax = 0;
  while(gets(cmdLine))
  {
   if(strlen(cmdLine) == 0)
    continue;
   if(strcmp(cmdLine,"END") == 0)
   {
    break;
   }
   ParseLine(cmdLine,program_1,0,xMax);
  }
  yMax = 0;
  while(gets(cmdLine))
  {
   if(strlen(cmdLine) == 0)
    continue;
   if(strcmp(cmdLine,"END") == 0)
   {
    break;
   }
   ParseLine(cmdLine,program_2,2,yMax);
  }
  sumMax = xMax + yMax + 1;
  varCon += 4;
  CalExpection();
  varCon -= 4;
  int minIdx;
  for(int i = varCon ; i > 0 ; i--)
  {
   minIdx = 0;
   for(int j = 1 ; j < i ; j++)
   {
    if(strcmp(var[j],var[minIdx]) < 0)
     minIdx = j;
   }
   printf("%.04f\n",d[prev][minIdx + 4][xMax]);
   if(minIdx < (i - 1))
   {
    strcpy(var[minIdx],var[i - 1]);
    d[prev][minIdx + 4][xMax] = d[prev][i + 3][xMax];
   }
  }
  if(loop > 0)
   printf("\n");
 }
    return 0;
}
void ParseLine(char * line,Struction * pro,int rIdx,int & idxMax)
{
 int i;
 char *pos, *start, *last;
 last = strstr(line,":=");
 if(last == NULL)
  return;
 //1,3
 last[0] = '\0';
 last += 2;
 pos = last;
 while(pos[0] == ' ' || pos[0] == '\t' || pos[0] == '\r' || pos[0] == '\n')
  pos++;
 start = pos;
 idxMax++;
 pro[idxMax+2].lValue = rIdx;
 pro[idxMax+2].a = rIdx;
 pro[idxMax+2].type_1 = false;
 pro[idxMax+2].b = rIdx + 1;
 pro[idxMax+2].type_2 = false; 
 if(start[0] >= '0' && start[0] <= '9')
 {
  while(pos[0])
  {
   if(pos[0] == ' ' || pos[0] == '\t' || pos[0] == '\r' || pos[0] == '\n' || pos[0] == '+' || pos[0] == '-')
   {
    break;
   }
   pos++;
  }
  last = pos;
  while(last[0])
  {
   if(last[0] == '+')
   {
    pro[idxMax+2].op = 1;
    break;
   }
   else if(last[0] == '-')
   {
    pro[idxMax+2].op = -1;
    break;
   }
   else
    last++;
  }
  last++;
  pos[0] = '\0';
  pro[idxMax].lValue = rIdx;
  pro[idxMax].a = atoi(start);
  pro[idxMax].type_1 = true;
  pro[idxMax].b = 0;
  pro[idxMax].type_2 = true;
  pro[idxMax].op = 1;
 }
 else
 {
  while(pos[0])
  {
   if(pos[0] == ' ' || pos[0] == '\t' || pos[0] == '\r' || pos[0] == '\n' || pos[0] == '+' || pos[0] == '-')
   {
    break;
   }
   else if(pos[0] >= 'a' && pos[0] <= 'z')
    pos[0] -= 32;
   pos++;
  }
  last = pos;
  while(last[0])
  {
   if(last[0] == '+')
   {
    pro[idxMax+2].op = 1;
    break;
   }
   else if(last[0] == '-')
   {
    pro[idxMax+2].op = -1;
    break;
   }
   else
    last++;
  }
  last++;
  pos[0] = '\0';
  for(i = 0 ; i < varCon ; i++)
  {
   if(strcmp(start,var[i]) == 0)
    break;
  }
  if(i == varCon)
  {
   strcpy(var[varCon],start);
   varCon++;
  }
  pro[idxMax].lValue = rIdx;
  pro[idxMax].a = i + 4;
  pro[idxMax].type_1 = false;
  pro[idxMax].b = 0;
  pro[idxMax].type_2 = true;
  pro[idxMax].op = 1;
 }
 //2
 pos = last;
 while(pos[0] == ' ' || pos[0] == '\t' || pos[0] == '\r' || pos[0] == '\n')
  pos++;
 start = pos;
 idxMax++;
 if(start[0] >= '0' && start[0] <= '9')
 {
  pro[idxMax].lValue = rIdx + 1;
  pro[idxMax].a = atoi(start);
  pro[idxMax].type_1 = true;
  pro[idxMax].b = 0;
  pro[idxMax].type_2 = true;
  pro[idxMax].op = 1;
 }
 else
 {
  while(pos[0])
  {
   if(pos[0] == ' ' || pos[0] == '\t' || pos[0] == '\r' || pos[0] == '\n')
   {
    break;
   }
   else if(pos[0] >= 'a' && pos[0] <= 'z')
    pos[0] -= 32;
   pos++;
  }
  pos[0] = '\0';
  for(i = 0 ; i < varCon ; i++)
  {
   if(strcmp(start,var[i]) == 0)
    break;
  }
  if(i == varCon)
  {
   strcpy(var[varCon],start);
   varCon++;
  }
  pro[idxMax].lValue = rIdx + 1;
  pro[idxMax].a = i + 4;
  pro[idxMax].type_1 = false;
  pro[idxMax].b = 0;
  pro[idxMax].type_2 = true;
  pro[idxMax].op = 1;
 }
 //4
 idxMax += 2;
 pos = cmdLine;
 while(pos[0] == ' ' || pos[0] == '\t' || pos[0] == '\r' || pos[0] == '\n')
  pos++;
 start = pos;
 while(pos[0])
 {
  if(pos[0] == ' ' || pos[0] == '\t' || pos[0] == '\r' || pos[0] == '\n')
  {
   break;
  }
  else if(pos[0] >= 'a' && pos[0] <= 'z')
   pos[0] -= 32;
  pos++;
 }
 pos[0] = '\0';
 for(i = 0 ; i < varCon ; i++)
 {
  if(strcmp(start,var[i]) == 0)
   break;
 }
 if(i == varCon)
 {
  strcpy(var[varCon],start);
  varCon++;
 }
 pro[idxMax].lValue = i + 4;
 pro[idxMax].a = rIdx;
 pro[idxMax].type_1 = false;
 pro[idxMax].b = 0;
 pro[idxMax].type_2 = true;
 pro[idxMax].op = 1;
}
void CalExpection()
{
 int i,num,sup,sub,x,y;
 double k,tempP;
 curr = 0;
 prev = 1;
 p[prev][0] = 1;
 for(i = 0 ; i < varCon ; i++)
  d[prev][i][0] = 0;
 for(num = 1 ; num < sumMax ; num++)
 {
  sup = min(num,xMax);
  sub = max(num - yMax,0);
  for(x = sub ; x <= sup ; x++)
  {
   for(i = 0 ; i < varCon ; i++)
   {
    y = num - x;
    d[curr][i][x] = 0;
    tempP = 0;
    if(x > 0)
    {
     if(program_1[x].lValue == i)
     {
      if(program_1[x].type_1 == true)
       k = program_1[x].a;
      else
       k = d[prev][program_1[x].a][x-1];
      if(program_1[x].type_2 == true)
       k += program_1[x].op * program_1[x].b;
      else
       k += program_1[x].op * d[prev][program_1[x].b][x-1];
     }
     else
      k = d[prev][i][x-1];
     if(y == 0)
      tempP = 1;
     else if(y == yMax)
     {
      if(x == xMax)
       tempP = p[prev][x-1] / (p[prev][x-1] + p[prev][x]);
      else
       tempP = p[prev][x-1] / (p[prev][x-1] + p[prev][x] / 2);
     }
     else
     {
      if(x == xMax)
       tempP = p[prev][x-1] / (p[prev][x-1] + 2 * p[prev][x]);
      else
       tempP = p[prev][x-1] / (p[prev][x-1] + p[prev][x]);
     }
     d[curr][i][x] += (k * tempP);
    }
    if(y > 0)
    {
     if(program_2[y].lValue == i)
     {
      if(program_2[y].type_1 == true)
       k = program_2[y].a;
      else
       k = d[prev][program_2[y].a][x];
      if(program_2[y].type_2 == true)
       k += program_2[y].op * program_2[y].b;
      else
       k += program_2[y].op * d[prev][program_2[y].b][x];
     }
     else
      k = d[prev][i][x];
     
     d[curr][i][x] += (k * (1 - tempP));
    }
   }
  }
  
  for(x = sub ; x <= sup ; x++)
  {
   y = num - x;
   p[curr][x] = 0;
   if(x > 0)
   {
    if(y == yMax)
     p[curr][x] += p[prev][x - 1];
    else
     p[curr][x] += (p[prev][x - 1] / 2);
   }
   if(y > 0)
   {
    if(x == xMax)
     p[curr][x] += p[prev][x];
    else
     p[curr][x] += (p[prev][x] / 2);
   }
  }
  i = curr;
  curr = prev;
  prev = i;
 }
}