比赛 |
20111104 |
评测结果 |
AATTTTTTTT |
题目名称 |
网球赛 |
最终得分 |
20 |
用户昵称 |
QhelDIV |
运行时间 |
0.000 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2011-11-04 21:44:50 |
显示代码纯文本
#include<fstream>
using namespace std;
ifstream fin("elimination.in");
ofstream fout("elimination.out");
int n,T=1;
//P[i][j]第i个选手打败第j个选手的概率
double f[1025][1025],P[1026][1026];
//f[i][j]第i轮时j出场时的概率
void init()
{
int i,j;
fin>>n;
for(i=1;i<=n;i++)
T=T*2;
for(i=1;i<=T;i++)
for(j=1;j<=T;j++)
{
fin>>P[i][j];
P[i][j]/=100;
}
}
double sumk(int deep,int pos)
{
int i,j,D=1;double sum=0,St,En;
for(i=1;i<=deep-1;i++)
D=D*2;
for(St=1,En=T;En-St>=D;)
if(En/2<pos)
En/=2;
else
St=En/2+1;
for(i=St;i<=En;i++)
sum=sum + P[pos][i]*f[deep-1][i];
return sum;
}
void dp()
{
int i,j;
for(i=1;i<=512;i++)
{
f[1][i*2]=P[i*2][i*2-1];
f[1][i*2-1]=P[i*2-1][i*2];
}
for(i=2;i<=n;i++)
for(j=1;j<=T;j++)
f[i][j]=f[i-1][j]*sumk(i,j);
}
int main()
{
init();
dp();
int i=1,Pos;double Max=0;
for(i=1;i<=T;i++)
if(Max<f[n][i])
{
Max=f[n][i];
Pos=i;
}
fout<<Pos;
fin.close();
fout.close();
return 0;
}