FACUP - The FA cup

Tác giả: ladpro98

Ngôn ngữ: C++

#include <cstdio>
#include <algorithm>
#include <vector>
#define di pair<double, int>
const int N = 9;
const int M = 1 << N;
using namespace std;
int a[M][M];
double F[M][N];
int m, n;
vector<di> b;

int main()
{
    scanf("%d", &n); m = 1 << n;
    int i, j, k, t, pos, lim;
    for(i=1; i<=m; i++) for(j=1; j<=m; j++) scanf("%d", &a[i][j]);
    for(i=1; i<=m; i++) F[i][0] = 1;
    for(k=0; k<n; k++) for(i=1; i<=m; i++) {
        t = 1 << k;
        pos = i / t; if (i % t > 0) pos++;
        if (pos & 1) {
            lim = (pos + 1) * t;
            for(j = lim; j > (lim - t); j--)
                F[i][k+1] += F[i][k] * F[j][k] * a[i][j] / 100;
        }
        else {
            lim = (pos - 1) * t;
            for(j = lim; j > (lim - t); j--)
                F[i][k+1] += F[i][k] * F[j][k] * a[i][j] / 100;
        }
    }
    for(i=1; i<=m; i++) b.push_back(di(1 - F[i][n], i));
    sort(b.begin(), b.end());
    for(i=0; i<b.size(); i++) printf("%d\n", b[i].second);
    return 0;
}

Download