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