FACUP - The FA cup
Tác giả: khuc_tuan
Ngôn ngữ: C++
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
int n, N;
int a[1025][1025];
pair<double, int> ds[1025];
vector<double> calc( int left, int right) {
vector<double> res;
if(left==right) {
res.push_back(1);
return res;
}
int mid = (left+right) / 2;
vector<double> r1 = calc( left, mid);
vector<double> r2 = calc( mid+1, right);
for(int i=left;i<=mid;++i) {
double t = 0;
for(int j=mid+1;j<=right;++j)
t += r2[j-mid-1] * a[i][j] / 100.0;
res.push_back( t * r1[i-left] );
}
for(int i=mid+1;i<=right;++i) {
double t = 0;
for(int j=left;j<=mid;++j)
t += r1[j-left] * a[i][j] / 100.0;
res.push_back( t * r2[i-mid-1] );
}
return res;
}
bool cmp(pair< double, int > p1, pair<double, int> p2) {
if(p1.first==p2.first) return p1.second < p2.second;
return p1.first > p2.first;
}
int main() {
scanf("%d", &n);
N = 1<<n;
for(int i=0;i<N;++i) for(int j=0;j<N;++j) scanf("%d", a[i]+j);
vector<double> res = calc( 0, N-1);
for(int i=0;i<N;++i) ds[i] = make_pair( res[i], i+1);
sort( ds, ds + N, cmp);
for(int i=0;i<N;++i) printf("%d\n", ds[i].second);
//system("pause");
return 0;
}