Description
在总决赛上,面对多次零封对手的DK战队,EDG贡献了一个精彩的BO5(五局三胜)。在观众看到被DK连扳两局 认为希望已经渺茫的时候,EDG却又连扳两局,让胜利的天平稳稳的倒向了我们这一边。观众的内心也随着比分而起伏…… 现在假设最多打 场,保证是奇数,EDG现在已经赢了a场,输了b场,问EDG有多少种不同的获胜的比分过程。注意如果胜负已分,就不需要再继续打了。 如果两种比分有至少一场比赛的比分不一样,就认为是两种不同的比分。
Input
第一行输入一个数 代表输入的组数 每组输入三个数 , 输入保证,组数不超过100组
Output
输出一个数,表示有多少种不同的可能 如果EDG不可能赢 那就说明与事实不符,那就不要输出数字,改为输出"EDG NB!" (不包含引号)
Sample
Input
Output
Hint
如果用1代表赢,0代表输 所有可能为
111
1011
1101
10011
10101
11001
注意打完的几场比赛顺序就已经固定了
时间限制:1000ms
内存限制:65536KiB
dfs解法:
#include<bits/stdc++.h> using namespace std; long long s=0; void dfs(int a,int b,int n) { if(a>n/2) { s++; return; } if(b>n/2) return; dfs(a+1,b,n); dfs(a,b+1,n); } int main() { long long t; cin>>t; long long i,a,b,n; for(i=1;i<=t;i++) { cin>>n>>a>>b; s=0; dfs(a,b,n); if(s!=0) cout<<s<<endl; else cout<<"EDG NB!"<<endl; } }
二进制规律解法:感谢舍友
#include<bits/stdc++.h> using namespace std; int main(){ long long a,b,n,i,cnt,count=0,r,T,t,k; cin>>t; for(k=0;k<t;k++){ cin>>n>>a>>b; count=0; for(i=0;i<pow(2,n-a-b);i++){ cnt=a; r=i; while(r){ T=r%2; if(T==1) cnt++; r/=2; } if(cnt==n/2+1){ r=i; count++; } } if(count==0) cout<<"EDG NB!"<<endl; else cout<<count<<endl; } }