比赛 |
20160419x |
评测结果 |
AAAAAAAAAA |
题目名称 |
贿赂 |
最终得分 |
100 |
用户昵称 |
mikumikumi |
运行时间 |
0.659 s |
代码语言 |
C++ |
内存使用 |
0.25 MiB |
提交时间 |
2016-04-19 15:48:36 |
显示代码纯文本
#include<cstdio>
#include<iostream>
using namespace std;
const int SIZEN=10;
double ans=0;
int N,K;
double A;
double a[SIZEN],b[SIZEN];
void read()
{
scanf("%d%d%lf",&N,&K,&A);
for(int i=1;i<=N;i++) scanf("%lf%lf",&a[i],&b[i]);
}
bool flag[SIZEN]={0};
void dfs2(int x,int cnt)
{
//cout<<x<<endl;
if(x>N)
{
//for(int i=1;i<=N;i++) cout<<flag[i]<<" ";
//cout<<endl;
double now=1.0;
for(int i=1;i<=N;i++)
{
if(flag[i]) now*=b[i]/100.0;
else now*=(100.0-b[i])/100.0;
}
if(cnt<=N/2)
{
double B=0;
for(int i=1;i<=N;i++)
{
if(!flag[i]) B+=a[i];
}
now*=A/(A+B);
}
//printf("%.6lf\n",now);
ans+=now;
return;
}
flag[x]=1;
dfs2(x+1,cnt+1);
flag[x]=0;
dfs2(x+1,cnt);
}
double tem=0;
void dfs1(int x,int pos)
{
if(x>K)
{
//for(int i=1;i<=N;i++) printf("%lf ",b[i]);
//cout<<endl;
dfs2(1,0);
tem=max(ans,tem);
ans=0;
//memset(flag,0,sizeof(flag));
//printf("%.6lf\n",ans);
return;
}
if(pos>N) return;
for(int i=pos;i<=N;i++)
{
if(b[i]==100) continue;
b[i]+=10;
dfs1(x+1,i);
b[i]-=10;
}
}
void work()
{
//for(int i=1;i<=N;i++) printf("%lf ",b[i]);
//cout<<endl;
dfs1(1,1);
printf("%.6lf\n",tem);
}
int main()
{
freopen("bribe.in","r",stdin);
freopen("bribe.out","w",stdout);
read();
work();
return 0;
}