Description

在总决赛上,面对多次零封对手的DK战队,EDG贡献了一个精彩的BO5(五局三胜)。在观众看到被DK连扳两局 认为希望已经渺茫的时候,EDG却又连扳两局,让胜利的天平稳稳的倒向了我们这一边。观众的内心也随着比分而起伏…… 现在假设最多打 n 场,保证n是奇数,EDG现在已经赢了a场,输了b场,问EDG有多少种不同的获胜的比分过程。注意如果胜负已分,就不需要再继续打了。 如果两种比分有至少一场比赛的比分不一样,就认为是两种不同的比分。

Input

第一行输入一个数 代表输入的组数 每组输入三个数 n,a,b1\leq n,a,b \leq 19 输入保证n \geq a+b,组数不超过100组

Output

输出一个数,表示有多少种不同的可能 如果EDG不可能赢 那就说明与事实不符,那就不要输出数字,改为输出"EDG NB!" (不包含引号)

Sample

Input

1
5 1 0 

Output

6 

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