FACUP - The FA cup
Tác giả: happyboy99x
Ngôn ngữ: C++
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
const int N = 8;
int winProb[1 << N][1 << N];
double comeProb[N + 1][1 << N];
int main() {
#ifndef ONLINE_JUDGE
freopen("FACUP.inp", "r", stdin);
#endif
ios::sync_with_stdio(false);
int n; cin >> n;
int numTeam = 1 << n;
for(int i = 0; i < numTeam; ++i) {
for(int j = 0; j < numTeam; ++j) {
cin >> winProb[i][j];
}
}
fill_n(comeProb[0], numTeam, 1);
for(int round = 0; round < n; ++round) {
for(int team = 0; team < numTeam; ++team) {
int opponentForm = (team & ~((1 << round) - 1)) ^ (1 << round);
for(int i = 0; i < 1 << round; ++i) {
int opponent = opponentForm | i;
comeProb[round + 1][team] += winProb[team][opponent] * comeProb[round][opponent];
}
comeProb[round + 1][team] *= comeProb[round][team] / 100;
}
}
// for(int round = 0; round <= n; ++round) {
// for(int team = 0; team < numTeam; ++team) {
// cerr << comeProb[round][team] << ' ';
// }
// cerr << '\n';
// }
vector<pair<double, int> > v (numTeam);
for(int i = 0; i < numTeam; ++i) {
v[i] = make_pair(-comeProb[n][i], i);
}
sort(v.begin(), v.end());
for(int i = 0; i < numTeam; ++i) {
printf("%d\n", v[i].second + 1);
}
return 0;
}