Last Updated on March 28, 2022 by Ria Pathak
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
KfromXmen andYwomen 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 X men and women in
ways, where any value
can be calculated using this formula :
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 K-1 men and 1 woman.
4) So, mathematically the total number of the team becomes :
Total number of teams =
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);
}
}
}
[forminator_quiz id="858"]
This article tried to discuss Mathematics. Hope this blog helps you understand and solve the problem. To practice more problems on Mathematics you can check out MYCODE | Competitive Programming.