2205.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 2205 on 2006-04-18 at 12:00:47 */ 
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const int COL[] = { 5, 4, 5, 4 };
const double eps = 1e-8;

int main()
{
	double chnc[5][5], pec[4][5];
	int path[5][5];
	int t, T, i, j;
	
	scanf("%d", &T);
	for(t = 1; t <= T; t++) {
		for(i = 0; i < 4; i++)
			for(j = 0; j < COL[i]; j++) {
				int a, b; scanf("%d/%d", &a, &b);
				pec[i][j] = a * 1.0 / b;
			}
		printf("data set #%d\n", t);
		int cn;
		for(cn = 0; cn < 3; cn++) {
			char b, e; scanf("\n%c\n%c", &b, &e);
			for(i = 0; i < 5; i++)
				for(j = 0; j < 5; j++)
					chnc[i][j] = path[i][j] = 0;
			chnc[0][b-'A'] = path[0][b-'A'] = 1;
			for(i = 0; i < 4; i++)
				for(j = 0; j < COL[i]; j++) {
					int l, r;
					if(fabs(chnc[i][j]) < eps) continue;
					if(i & 1) l = j, r = j+1;
					else l = j-1, r = j;
					if(fabs(pec[i][j]) > eps) path[i+1][r] += path[i][j];
					chnc[i+1][r] += chnc[i][j] * pec[i][j];
					if(l < 0 || fabs(1-pec[i][j]) < eps) continue;
					path[i+1][l] += path[i][j];
					chnc[i+1][l] += chnc[i][j] * (1-pec[i][j]);
				}
			printf("%c->%c %d paths, %.0lf%% chance\n", b, e, path[4][e-'A'], floor(100*chnc[4][e-'A']+eps));
		}
	}
	
	return 0;
}