比赛 20160419x 评测结果 AAAAAAAAAA
题目名称 贿赂 最终得分 100
用户昵称 Fmuckss 运行时间 0.771 s
代码语言 C++ 内存使用 0.28 MiB
提交时间 2016-04-19 16:30:20
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

int l[11];
int v[11];
bool vote[11];
int n, k;
double A;
double res, ans;

void get_now(int now, int cnt) {
	if(now == n+1) {
		double p = 1;
		double su = 1;
		double tot = 0;
		for(int i = 1; i <= n; i++) {
			if(vote[i]) p *= ((double)v[i]/(double)100);
			else p *= ((double)(100-v[i])/(double)100);
		}
		if(cnt <= (n >> 1) ) {
			for(int i = 1; i <= n; i++) {
				if(!vote[i]) tot += l[i];
			}
			p *= (A/(A+tot));
		}
		res += p;
		return;
	}
	vote[now] = true;
	get_now(now+1, cnt+1);
	vote[now] = false;
	get_now(now+1, cnt);
}

void dfs(int now, int tot) {
	if(tot == 0) {
		res = 0;
		get_now(1, 0);
		ans = max(ans, res);
		return;
	}
	for(int i = now; i <= n; i++) {
		v[i] += 10;
		if(v[i] <= 100) dfs(i, tot-1);
		v[i] -= 10;
	}
}

void read() {
	scanf("%d %d %lf", &n, &k, &A);
	for(int i = 1; i <= n; i++) {
		scanf("%d %d", &l[i], &v[i]);
	}
}

void solve() {
	dfs(1, k);
	printf("%.6lf\n", ans);
}

int main() {
	freopen("bribe.in", "r", stdin);
	freopen("bribe.out", "w", stdout);
	read();
	solve();
	return 0;
}