2013年8月14日

UVa 542 - France '98

#include <cstdio>

int main() {
  char name[16][99];
  for (int i = 0; i < 16; i++) {
    gets(name[i]);
  }
  double p[16][16];
  for (int i = 0; i < 16; i++) {
    for (int j = 0; j < 16; j++) {
      scanf("%lf", &p[i][j]);
      p[i][j] /= 100;
    }
  }
  double round[4][16];
  for (int i = 0; i < 16; i += 2) {
    round[0][i] = p[i][i + 1];
    round[0][i + 1] = p[i + 1][i];
  }
  for (int r = 1; r < 4; r++) {
    int cmpNum = 1 << r;
    for (int i = 0; i < 16; i += cmpNum * 2) {
      for (int j = i; j < i + cmpNum; j++) {
        round[r][j] = 0;
        for (int k = i + cmpNum; k < i + cmpNum + cmpNum; k++) {
          round[r][j] += round[r - 1][j] * round[r - 1][k] * p[j][k];
        }
      }
      for (int j = i + cmpNum; j < i + cmpNum + cmpNum; j++) {
        round[r][j] = 0;
        for (int k = i; k < i + cmpNum; k++) {
          round[r][j] += round[r - 1][j] * round[r - 1][k] * p[j][k];
        }
      }
    }
  }
  for (int i = 0; i < 16; i++) {
    printf("%-10s p=%.2lf%%\n", name[i], round[3][i] * 100);
  }
  return 0;
}

沒有留言:

張貼留言