#DP #Probability #UVa #Solved #OutputFormat

542 - France '98.cpp

//https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=483
#include <bits/stdc++.h>

#define ll long long
#define sz(v) ((int) ((v).size()))
#define clr(v, d) memset(v, d, sizeof(v))
#define lp(i, n) for(int i = 0; i < (int)(n); ++i)
#define rep(i, v) for(int i = 0; i < sz(v); ++i)

using namespace std;

const int OO = 1e4;
int n;
double prob[20][20];
string a[20];
double cache[20][20][20];

double calcProb(int i, int st, int en) {
    //cout << i << " " << st << "  " << en << endl;
    //getchar();
    if(st == en)
        return 1.0;
    double &ret = cache[i][st][en];
    if(ret + 1 > 1e-9)
        return ret;
    ret = 0;
    double ch1;
    if(en - st == 1) {
        ret = (i&1) ? prob[i][i-1] : prob[i][i+1];
        //cout <<"LEVEL 2: " << ret << endl;
    } else {
        int x = ((en-st)/2) + st;
        int tmpst = st, tmpen = en, tmpst2 = st, tmpen2 = en;
        if(i > x)
            tmpst = x+1, tmpen2 = x;
        else
            tmpen = x, tmpst2 = x+1;
        ch1 = calcProb(i, tmpst, tmpen);
        for(int j = tmpst2; j <= tmpen2; j++) {
            //cout << ch1 << " " << prob[i][j] << endl;
            ret += ch1 * prob[i][j] * calcProb(j, tmpst2, tmpen2);
        }
    }

    return ret;
}

int main() {
    n = 16;
    clr(cache, -1);
    lp(i, n) {
        cin>>a[i];
    }
    int x;
    lp(i, n) {
        lp(j, n) {
            cin>>x;
            prob[i][j] = x/100.0;
        }
    }
    lp(i, n) {
        cout <<setw(10) << left << a[i] << " p=" <<fixed << setprecision(2) << calcProb(i, 0, n-1)*100 << "%\n";
    }

    return 0;
}