记录编号	77806	评测结果	AAAAAAAAAA
题目名称	网球赛	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.234 s
提交时间	2013-11-02 18:13:17	内存使用	8.41 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iomanip>
#include<cstring>
#include<vector>
using namespace std;
const int SIZEP=1025;
const int SIZEN=11;
int n;
int nump;
double winrate[SIZEP][SIZEP]={0};
double exip[SIZEP][SIZEN]={0};
int pow2[]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096};
void init(void){
	scanf("%d",&n);
	nump=pow2[n];
	int i,j;
	for(i=1;i<=nump;i++){
		for(j=1;j<=nump;j++){
			scanf("%lf",&winrate[i][j]);
			winrate[i][j]/=100;
		}
	}
	for(i=1;i<=nump;i++) exip[i][0]=1;
}
void dp(void){
	int i,j,k;
	int ablenum;
	int start,end,mid;
	for(k=0;k<n;k++){
		ablenum=pow2[k+1];
		for(i=1;i<=nump;i++){
			start=((i-1)/ablenum)*ablenum+1;
			end=start+ablenum-1;
			mid=(start+end)>>1;
			if(i<=mid) start=mid+1;
			else end=mid;
			for(j=start;j<=end;j++){
				exip[i][k+1]+=exip[j][k]*winrate[i][j];
			}
			exip[i][k+1]*=exip[i][k];
		}
	}
}
void answer(void){
	double ansp=0;
	int ans=0;
	int i;
	for(i=1;i<=nump;i++){
		if(exip[i][n]>ansp){
			ansp=exip[i][n];
			ans=i;
		}
	}
	printf("%d\n",ans);
}
int main(){
	freopen("elimination.in","r",stdin);
	freopen("elimination.out","w",stdout);
	init();
	dp();
	answer();
	return 0;
}