比赛 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;
}