Codeforces Beta Round #95 (Div. 2) C 组合数学

C. The World is a Theatre

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

There are n boys and m girls attending a theatre club. To set a play "The Big Bang Theory", they need to choose a group containing exactly t actors containing no less than 4 boys and no less than one girl. How many ways are there to choose a group? Of course, the variants that only differ in the composition of the troupe are considered different.

Perform all calculations in the 64-bit type: long long for С/С++, int64 for Delphi and long for Java.

Input

The only line of the input data contains three integers n, m, t (4 ≤ n ≤ 30, 1 ≤ m ≤ 30, 5 ≤ t ≤ n + m).

Output

Find the required number of ways.

Please do not use the %lld specificator to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d specificator.

Examples

Input

5 2 5

Output

Input

4 3 5

Output

3

题意：n个男生 m个女生 选t个人 男生最少4个 女生最少1个 问有多少种选择方式

题解：组合数学 数据范围很小 求组合数 直接公式线性处理或者杨辉三角处理 C(n,m)=n!/m!(n-m)! 
  注意在男生为4,女生为1的基础上暴力求。枚举男生的人数i=（4~t-1）ΣC(n,i)*C(m,t-i)

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #define ll long long

 using namespace std;

 ll n,m,t;

 ll ans;

 ll combine1(ll n,ll m) //计算组合数C(n,m)

 {

     ll sum=; //线性计算

     for(ll i=,j=n;i<=m;i++,j--)

         sum=sum*j/i;

     return sum;

 }

 int main()

 {

     scanf("%I64d %I64d %I64d",&n,&m,&t);

     for(int i=;i<=t-;i++)

     {

         ans=ans+combine1(n,i)*combine1(m,t-i);

     }

     printf("%I64d\n",ans);

 }

巴特西

Codeforces Beta Round #95 (Div. 2) C 组合数学

最新文章

热门文章