#### Concepts Used:

Mathematics

#### Difficulty Level:

Hard

#### Problem Statement (Simplified):

In this problem, we have to find a total number of ways to form a team of size

`K`

from`X`

men and`Y`

women with at least 4 men and 1 woman in the team.

**See original problem statement here**

#### Test Case:

```
Input:
1
5 2 6
Output:
7
Explanation:
For example, We have to form a team of size 6(K), and there need to be at least 4 men and 1 woman out of 5(X) men and 2(Y) women. So we can form 2 teams and in total 7 ways, consisting Men and Women in the following ways :
4 Men + 2 Women ( Total 5 ways )
5 Men + 1 Women ( Total 2 ways )
```

#### Solving Approach :

1) We already know, we can select

`m`

men and`n`

women from`MARKDOWN_HASH02129bb861061d1a052c592e2dc6b383MARKDOWN`

HASHmen and women in <img src="http://latex.codecogs.com/svg.latex?^{X}C{m}\times^{Y}C{n}" border="0" /> ways, where any value <img src="http://latex.codecogs.com/svg.latex?^{n}C{r}" border="0" /> can be calculated using this formula by referring the best sites to learn programming languages:2) As we know, we need to form a team of size

`K`

where there need to be at least 4 men and 1 woman at least.

3) For the above condition, there will be`K-4`

different teams, containing different numbers of men and women in the team.

In the first team, there would be 4 men and`K-4`

women, in second-team there would be 5 men and`K-5`

women, as we reach to end, the last team consists of`MARKDOWN_HASHbf20193137085b07680e64a4ed4a7666MARKDOWN`

HASHmen and 1 woman.{i=4}^{K-1}`^{X}C

4) So, mathematically the total number of the team becomes :

Total number of teams = <img src="http://latex.codecogs.com/svg.latex?\sum{i}\times^{Y}C{K-i}" border="0" />

#### Example:

Let’s assume, We have to form a team of size

`6(K)`

and there needs to be atleast`4`

men and`1`

women out of`5(X)`

men and`2(Y)`

women. So we can form`2`

teams, consisting Men and Women in following ways :

`4`

Men +`2`

Women ( Total`5`

ways )

`5`

Men +`1`

Women ( Total`2`

ways )

Total number of ways to form a team of size 6 with`4`

Men and`2`

women :Assuming Men(

`M¹ M² M³ M⁴ M⁵`

) and Women (`W¹ M²`

) are there to select, now we have to select team of`6`

, we need`2`

women, so we’ll pick all women, and we need`4`

men, so we’ll pick`4`

men and then pair them with women. So possible ways are :

`M¹ M² M³ M⁴`

+`W¹ W²`

`M¹ M² M³ M⁵`

+`W¹ W²`

`M¹ M² M⁵ M⁴`

+`W¹ W²`

`M¹ M⁵ M³ M⁴`

+`W¹ W²`

`M⁵ M² M³ M⁴`

+`W¹ W²`

Total number of ways to form a team of size 6 with`5`

Men and`1`

women :Assuming Men(

`M¹ M² M³ M⁴ M⁵`

) and Women (`W¹ M²`

) are there to select, now we have to select team of`6`

, we need`5`

men, so we’ll pick all men, and we need`1`

woman, so we’ll pick`1`

woman and then pair her with men. So possible ways are :

`M¹ M² M³ M⁴ M⁴`

+`W¹`

`M¹ M² M³ M⁴ M⁴`

+`W¹`

Hence, in similar ways, we can find answers for different cases.

#### Solutions:

#include <stdio.h> long long nCr(int n, int r){ long long value=1; for(int i=0;i<r;i++){ value*=(n-i); value/=(i+1); } return value; } int main() { int test; scanf("%d",&test); while(test--){ int n, m, k; scanf("%d%d%d",&n,&m,&k); long long sum=0; for(int i=4; i<k; i++){ sum += nCr(n,i)*nCr(m,k-i); } printf("%lld\n",sum); } }

#include <bits/stdc++.h> using namespace std; long long nCr(int n, int r){ long long value=1; for(int i=0;i<r;i++){ value*=(n-i); value/=(i+1); } return value; } int main() { int test; cin>test; while(test--){ int n, m, k; cin>n>m>k; long long sum=0; for(int i=4; i<k; i++){ sum += nCr(n,i)*nCr(m,k-i); } cout<<sum<<endl; } }

import java.util.*; import java.io.*; public class Main { static long nCr(int n, int r){ long value=1; for(int i=0;i<r;i++){ value*=(n-i); value/=(i+1); } return value; } public static void main(String args[]) throws IOException { Scanner sc = new Scanner(System.in); int test = sc.nextInt(); while(test--!=0){ int n = sc.nextInt(), m = sc.nextInt(), k = sc.nextInt(); long sum=0; for(int i=4; i<k; i++){ sum += nCr(n,i)*nCr(m,k-i); } System.out.println(sum); } } }