UVA 542

#define ll long long
#include <bits/stdc++.h>
using namespace std;

const int OO = 1e9;
const double EPS = 1e-9;

map<pair<int,int>,set<int>> opp;
double p[16][16];
string names[16];
double mem[16][4];

double solve(int idx, int rd) {
    if(mem[idx][rd] != -1) {
        return mem[idx][rd];
    }
    if(rd == 0) {
        return p[idx][*(opp[{idx,0}].begin())];
    }
    double &ret = mem[idx][rd];
    ret = 0;
    for(int e : opp[{idx,rd}]) {
        ret += p[idx][e] * solve(e,rd-1);
    }
    ret *= solve(idx,rd-1);
    return ret;
}

int rd_idx(int x) {
    int ret = 0;
    while(x > 2) {
        x /= 2;
        ret++;
    }
    return ret;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cout.precision(2);
    cout << fixed;
    for(int i = 0; i < 16; i++) {
        for(int j = 0; j < 4; j++) {
            mem[i][j] = -1;
        }
    }
    for(int i = 0; i < 16; i++) {
        cin >> names[i];
    }
    for(int i = 0; i < 16; i++) {
        for(int j = 0; j < 16; j++) {
            cin >> p[i][j];

            p[i][j] /= 100.0;
        }
    }
    for(int i = 0; i < 16; i++) {
        for(int j = 2; j <= 16; j *= 2) {
            int l = i/j;
            for(int k = l*j; k < (l+1)*j; k++) {
                bool flag = (k != i);
                for(int o = j/2; o > 1; o /= 2) {
                    int rd = rd_idx(o);
                    if(opp[{i,rd}].find(k) != opp[{i,rd}].end()) {
                        flag = false;
                        break;
                    }
                }
                if(flag) {

                    opp[{i,rd_idx(j)}].insert(k);
                }
            }
        }
    }
    for(int i = 0; i < 16; i++) {
        cout << names[i] << string(10-names[i].length(),' ') << " p=" << solve(i,3)*100.0 << "%\n";
    }

    return 0;
}