# JudgeGirl #235

## Pachinko

Basically there are `i+1` pins on the i-th row, and different amount of balls fall down to each side, called bucket. Calculate the probability that a ball falls into each N+1 bucket. **N <= 15**

For the above example:
2/15 = 1/3 * 2/5, 7/10 = 1/3\*5/3 + 3/2\*4/3

**Hint:** In order to prevent arithmetic overflow, you should reduce the denominator and numerator of each fractional number you use.

## Keys

### 1. The Fraction Structure

It is pretty straight forward that we implement a fraction struct, otherwise it's quite hideous to store a fraction.

typedef long long ll;
typedef struct {
    ll up, down; // ll so we don't overflow
                 // up is num, down is denum
} Frac;

### 2. gcd()

It is also obvious that we need a `gcd()` function in order to reduce the fraction. [About the Euclidean algorithm](https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/the-euclidean-algorithm).

ll gcd(ll a, ll b) {
    ll temp;
    while (b != 0) {
        temp = a % b;
        a = b;
        b = temp;
    }
    return a;
}

### 3. The Pins Array

We need to find a way to store all the fraction the problem gives us.
The way we store them is that the j-th pin on the i-th row will be `pins[i][j]`.
The problem says that N is no more than 15, so an array of `pins[20][20]` is more than enough. (there will only be 16 pins on the 15th row)

Also notice that we only need to store one fraction `p` in each pin, we can get the other one by `1 - p`.

ll left, right;
for (int i = 0; i < n; i++) {
    for (int j = 0; j <= i; j++) { // the i-th row has i pins
        scanf("%lld %lld", &left, &right);
        right = left + right;
        ll g = gcd(left, right);
        left /= g, right /= g;
        pins[i][j].up = left, pins[i][j].down = right;
    }
}

**Note:** reduce the fraction first, then store.

### 4. The Buckets

To understand the problem better, we can draw a simple graph:


So we construct another array of `dp[20][20]` as the buckets, and we set `dp[0][0]` to one (fractional 1).
Then we notice that the `pins[i][j]` will always falls into `dp[i+1][j]`, and 1 - `pins[i][j]` always falls into `dp[i+1][j+1]`.

// set dp to all fractional zero so when we do addition it won't fuck up.
for (int i = 0; i < M; i++) 
    for (int j = 0; j < M; j++) 
        {dp[i][j].up = 0, dp[i][j].down = 1;}

// set first bucket to fraction one.
dp[0][0].up = 1, dp[0][0].down = 1;
for (int i = 0; i < n; i++) {
    for (int j = 0; j <= i; j++) {
        // muliply last bucket with pins[i][j]
        ll lastup = dp[i][j].up, lastdown = dp[i][j].down;
        ll thisup = pins[i][j].up, thisdown = pins[i][j].down;
        thisup *= lastup, thisdown *= lastdown;
        ll g = gcd(thisup, thisdown);
        thisup /= g, thisdown /= g;
        // add result to this bucket
        ll a = dp[i+1][j].up * thisdown + dp[i+1][j].down * thisup, b = dp[i+1][j].down * thisdown;
        g = gcd(a, b);
        a /= g, b /= g;
        dp[i+1][j].up = a, dp[i+1][j].down = b;
        // following are same but with 1 - pins[i][j]
        // multiply
        thisup = pins[i][j].down - pins[i][j].up, thisdown = pins[i][j].down;
        thisup *= lastup, thisdown *= lastdown;
        g = gcd(thisup, thisdown);
        thisup /= g, thisdown /= g;
        // add
        a = dp[i+1][j+1].up * thisdown + dp[i+1][j+1].down * thisup, b = dp[i+1][j+1].down * thisdown;
        g = gcd(a, b);
        a /= g, b /= g;
        dp[i+1][j+1].up = a, dp[i+1][j+1].down = b;
    }
}

Finally, the last row we did is `n - 1`, so `dp[n]` will have our answer.

## Code

#include <stdio.h>

#define M 20

typedef long long ll;

ll gcd(ll a, ll b) {
    ll temp;
    while (b != 0) {
        temp = a % b;
        a = b;
        b = temp;
    }
    return a;
}

typedef struct {
    ll up, down;
} Frac;

Frac pins[M][M], dp[M][M];

int main() {
    int n;
    scanf("%d", &n);

    ll left, right;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            scanf("%lld %lld", &left, &right);
            right = left + right;
            ll g = gcd(left, right);
            left /= g, right /= g;
            pins[i][j].up = left, pins[i][j].down = right;
        }
    }

    for (int i = 0; i < M; i++) for (int j = 0; j < M; j++) {dp[i][j].up = 0, dp[i][j].down = 1;}
    dp[0][0].up = 1, dp[0][0].down = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            // mul
            ll lastup = dp[i][j].up, lastdown = dp[i][j].down;
            ll thisup = pins[i][j].up, thisdown = pins[i][j].down;
            thisup *= lastup, thisdown *= lastdown;
            ll g = gcd(thisup, thisdown);
            thisup /= g, thisdown /= g;
            // add
            ll a = dp[i+1][j].up * thisdown + dp[i+1][j].down * thisup, b = dp[i+1][j].down * thisdown;
            g = gcd(a, b);
            a /= g, b /= g;
            dp[i+1][j].up = a, dp[i+1][j].down = b;
            // mul
            thisup = pins[i][j].down - pins[i][j].up, thisdown = pins[i][j].down;
            thisup *= lastup, thisdown *= lastdown;
            g = gcd(thisup, thisdown);
            thisup /= g, thisdown /= g;
            // add
            a = dp[i+1][j+1].up * thisdown + dp[i+1][j+1].down * thisup, b = dp[i+1][j+1].down * thisdown;
            g = gcd(a, b);
            a /= g, b /= g;
            dp[i+1][j+1].up = a, dp[i+1][j+1].down = b;
        }
    }

    for (int i = 0; i <= n; i++) printf("%lld/%lld\n", dp[n][i].up, dp[n][i].down);



    return 0;
}