#include<iostream>#include<iomanip>usingnamespacestd;/* Total number of columns in board (including blank spaces) */#defineCOLS 9/* Total number of rows in board (actually rows of pegs) */#defineROWS 4/* Class to represent fractions and allow operations on them */classfract {public: int numer, denom;/* Constructors */fract() :numer(0),denom(1) {}fract(int n, int d) :numer(n),denom(d) {}/* Convert fraction to decimal */inlinedoublevalue(void) {return((double) numer) / denom; } };/* Extraction operator for parsing fractions */istream &operator>>(istream &s, fract &f) { char c;/* Parse entire fraction; c variable parses the "/" character */cin >> f.numer >> c >> f.denom;/* Check denominator */if(f.denom == 0)throw"Invalid denominator"; }/* Compute least common multiple for two numbers */intlcm(int n1, int n2) { int a = n1, b = n2, r;/* Use Euclid's algorithm to find greatest common divisor */while(b != 0) { r = a % b; a = b; b = r; }/* Compute least common multiple (a is now the gcd) */return(n1 / a) * n2; }/* Fraction multiplication */fractoperator*(fractconst&a, fractconst&b) { fract f; f.numer = a.numer * b.numer; f.denom = a.denom * b.denom;returnf; }/* Fraction addition */fractoperator+(fractconst&a, fractconst&b) { fract f; int m =lcm(a.denom, b.denom); f.numer = (a.numer * (m / a.denom)) + (b.numer * (m / b.denom)); f.denom = m;returnf; }/* Fraction subtraction */fractoperator-(fractconst&a, fractconst&b) { fract f; int m =lcm(a.denom, b.denom); f.numer = (a.numer * (m / a.denom)) - (b.numer * (m / b.denom)); f.denom = m;returnf; }/** Holds probabilities for each peg. The array actually represents the* entire board with pegs and spaces combined. Array cells representing* spaces are just wasted, since they will never be accessed by the* program. However, representing the board in this manner makes the* overall program logic simpler.*/fract board[ROWS][COLS];/* Accumulated number of paths reaching the current ending column */int total_paths;/* Accumulated probability of reaching the current ending column */fract total_prob;/* Read in all the probabilities and initialize board array */voidparse_board(void) { int row, col;/* Iterate over all rows */for(row = 0; row < ROWS; row++) {/* Odd numbered rows start in column 1, even in column 0 */for(col = (row & 1) ? 1 : 0; col < COLS; col += 2) { fract prob;/* Parse entire fraction */cin >> prob;/* Probability of leftmost pegs on even rows must be 1 */if(col == 0 &&abs(1.0 - prob.value()) > 0.00001)throw"Invalid probability for left peg";/* Probability of rightmost pegs on even rows must be 0 */if(col == (COLS - 1) &&abs(prob.value()) > 0.00001)throw"Invalid probability for right peg";/* Assign probability to board location */board[row][col] = prob; } } }/** Recursively explore all possible paths the chip can take.** row - starts of with 0 and is incremented by one for each recursive* call as the chip fall down. The recursion stops when row == ROWS.** col - starts with the column number into which the chip is first dropped.* It gets incremented or decremented by one for each recursive to keep track* of the chip as it falls either to the left or right of each peg.** end - ending column for which we want to compute probability. If the peg* reaches the bottom (row == ROWS) and (col == end) then we add "prob"* to the running total probability.** prob - probability of reaching the currently computed path*/voidtraverse(int row, int col, int end, fract prob) {/* Stop recursing if the probability of the current path is zero */if(prob.value() < 0.00001)return;/* Stop recursing if the chip has reached the exiting row */if(row == ROWS) {/* Accumulate results if ending column is the one we need */if(col == end) { total_paths++; total_prob = total_prob + prob; }return; }/** The boundry checks below are technically unnecessary since the* probability for moving off the edge of the board is 0, therefore the* boundry condition would be caught by the (prob < 0.00001) check in the* recursive call.*//* If not in the leftmost column, recurse left */if(col > 0)traverse(row + 1, col - 1, end, prob * (fract(1, 1) - board[row][col]));/* If not in the rightmost column, recurse right */if(col < (COLS - 1))traverse(row + 1, col + 1, end, prob * board[row][col]); }/* Parse a single capital letter and return 0 for A, 2 for B, 4 for C, etc */intparse_col(void) { char c;/* Read the letter from stdin */cin >> c;/* Verify the column name is valid */if(c < 'A' || c > 'E')throw"Invalid column name";/* Convert letter to even column number */return(c - 'A') * 2; }/* Parse the path name and calculate probabilities */voidprocess_path(void) { int start, end;/* Read the starting/ending column number */start =parse_col(); end =parse_col();/* Initialize global variables used for accumulating results */total_paths = 0; total_prob =fract(0, 1);/* Print out the name of the path about to be computer */cout << (char) ('A' + (start / 2)) << "->"; cout << (char) ('A' + (end / 2)) << " " << flush;/* Calculate the probabilities */traverse(0, start, end,fract(1, 1));/* Print out the results (the << automatically rounds numbers) */cout << total_paths << " paths, "; cout << (int) (total_prob.value() * 100); cout << "% chance" << endl; }/* Main body of program */voidprocess(void) { int board_num, board_idx;/* Throw exceptions on unexpected EOF */cin.exceptions(ios::eofbit);/* Read how many boards are to be analyzed */cin >> board_num;/* Process each board separately */for(board_idx = 0; board_idx < board_num; board_idx++) { int i;/* Initialize probabilities */cout << "data set #" << board_idx + 1 << endl;parse_board();/* Parse the column names and compute the results */for(i = 0; i < 3; i++)process_path(); } }/* Run program and print out any exceptions that occur */intmain(void) {/* Run main body of code */try{process(); }/* Catch any internally generated exceptions */catch(charconst*e) { cerr << "Exception: " << e << endl; }/* Catch unexpected EOF on input */catch(ios::failureconst&ee) { cerr << "Exception: Unexpected EOF on input" << endl; }return0; }