石油大http://exam.upc.edu.cn/problem.php?cid=1242&pid=1
问题 B: Election
时间限制: 1 Sec 内存限制: 128 MB
提交: 83 解决: 12
题目描述
After all the fundraising, campaigning and debating, the election day has finally arrived. Only two candidates remain on the ballot and you work as an aide to one of them.
Reports from the voting stations are starting to trickle in and you hope that you can soon declare a victory.
There are N voters and everyone votes for one of the two candidates (there are no spoiled ballots). In order to win, a candidate needs more than half of the votes. A certain number M≤N of ballots have been counted, and there are Vi votes for candidate i (V1+V2 = M), where V1 is the number of votes your candidate received.
Due to the historical data and results of highly scientific polls, you know that each of the remaining votes has a 50% chance to go to your candidate. That makes you think that you could announce the win before all the votes are counted. So, if the probability of winning strictly exceeds a certain threshold W, the victory is yours! We just hope you are sure of this, we don’t want any scandals...
输入
The first line of input contains a single positive integer T≤100 indicating the number of test cases. Next
T lines each contain four integers: N, V1, V2 and W as described above.
The input limits are as follows:
1≤N≤50
50≤W<100
V1,V2≥0
V1 + V2≤N
输出
For each test case print a single line containing the appropriate action:
If the probability that your candidate will win is strictly greater than W%, print
GET A CRATE OF CHAMPAGNE FROM THE BASEMENT!
If your candidate has no chance of winning, print
RECOUNT!
Otherwise, print
PATIENCE, EVERYONE!
样例输入
4
5 0 3 75
5 0 2 75
6 1 0 50
7 4 0 75样例输出
RECOUNT!
PATIENCE, EVERYONE!
PATIENCE, EVERYONE!
GET A CRATE OF CHAMPAGNE FROM THE BASEMENT!
【解析】：
题意，计算出剩余票数，投票，能使得1号获胜的概率，然后与w%比较。
以第三组示例解析：
剩余m=5票，1号得其中的3,4,5票便能获胜，所以1号获胜的概率：
p=C(m,3)*0.5^5 + C(m,4)*0.5^5 + C(m,5)*0.5^5
然后考虑到实数精度问题，过程中不进行除法，而是比较时，分子分母化简一下，使得运算过程全用long long即可
详见代码。
另，还有一处优化，如果算概率过程中，虽然p没加完，但已经大于概率w了，直接退出循环就行了。
【代码】：
#include <stdio.h>
#include <math.h>
typedef long long ll;
ll qpow(ll n,ll m){ll ans=1;while(m){if(m%2)
ans=(ans*n);m/=2;n=(n*n);}return ans;}
ll Cf[55][55];
int main()
{
//组合数打表
Cf[0][0]=1;//特殊
for(int i=1;i<=51;i++)
for(int j=0;j<=51;j++)
Cf[i][j]=(j==0)?1:(Cf[i-1][j]+Cf[i-1][j-1]);
int n,v1,v2,w,T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d%d",&n,&v1,&v2,&w);
int m=n-v1-v2;//剩余人数
int sh=n/2+1;//获胜最少票数
int t=sh-v1;//还差几票
ll p=0;
int flag=0;
for(int i=t>0?t:0;i<=m;i++)
{
p+=Cf[m][i];
//printf("%lf\n",p/pow(2,m));
if(p*100>w*qpow(2,m))
{
flag=1;break;
}
}
if(flag)
puts("GET A CRATE OF CHAMPAGNE FROM THE BASEMENT!");
else if(2*v2>=n)
puts("RECOUNT!");
else
puts("PATIENCE, EVERYONE!");
}
return 0;
}