比赛 20160419x 评测结果 AAAAAAAAAA
题目名称 贿赂 最终得分 100
用户昵称 Satoshi 运行时间 0.328 s
代码语言 C++ 内存使用 0.28 MiB
提交时间 2016-04-19 16:03:36
显示代码纯文本
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <cstring>
#define N 11
using namespace std;
typedef double ld;
ifstream in("bribe.in");
ofstream out("bribe.out");
int n,K;
ld A;
ld a[N]={0},b[N]={0},add[N]={0},win[N]={0},fail[N]={0};
bool l[N]={0};
int top=0;
ld ans=0;
void print(ld x,int y){out<<setprecision(y)<<std::fixed<<x<<endl;}
ld update()
{
	int i,tolo=0;
	ld sum=1;
	ld solo=0;
	for(i=1;i<=n;i++)
	{
		if(l[i])
		{
			sum*=win[i];
			tolo++;//总共有多少人投了支持票
		}
		else 
		{
			sum*=fail[i];
			solo+=a[i];
		}
	}
	if(tolo<=n/2)sum*=(A/(A+solo));//干掉那些人
	memset(l,0,sizeof(l));
	return sum;
}
void fuck()
{
	int i,temp,cnt=0;
	ld sum=0;
	for(i=1;i<=n;i++)
	{
		win[i]=b[i]+add[i];
		if(win[i]>10)win[i]=10;
		win[i]/=10.0;
		fail[i]=1-win[i];
		//out<<win[i]<<' '<<fail[i]<<' '<<endl;
	}
	
	for(i=0;i<(1<<n);i++)
	{
		temp=i;
		cnt=0;
		while(temp)
		{
			l[++cnt]=temp%2;
			temp=temp>>1;
		}
		sum+=update();
	}
	if(sum>ans)ans=sum;
}
void DFS(int tot,int pos)//糖果已经给了tot个人,位置指针指向pos
{
	
	if(tot>K)return ;
	if(pos==n+1)
	{
		if(tot==K)fuck();
		return ;
	}
	else
	{
		for(int i=0;i<=K-tot;i++)
		{
			if(b[pos]+i>10.0)return ;
			add[pos]=i;
			DFS(i+tot,pos+1);
			add[pos]=0;
		}
	}
}
void read()
{
	int i;
	in>>n>>K>>A;
	for(i=1;i<=n;i++)
	{
		in>>a[i]>>b[i];
		b[i]/=10.0;
	}
}
void work()
{
	DFS(0,1);
}
int main()
{
	//int start,end;
	//start=clock();
	read();
	work();
	print(ans,6);
	//end=clock();
	//out<<end-start<<endl;
	return 0;
}