Lazy Student Problem Description There is a test of Algorithms. Teacher provides a question bank consisting of N questions and guarantees all the questions in the test will be from this question bank. Due to lack of time and his laziness, Codu could only practice M questions. There are T questions in a question paper selected randomly. Passing criteria is solving at least 1 of the T problems. Codu can't solve the question he didn't practice. What is the probability that Codu will pass the test? Constraints 0 < T <= 10000 0 < N, T <= 1000 0 <= M <= 1000 M,T <= N Input Format First line contains single integer T denoting the number of test cases. First line of each test case contains 3 integers separated by space denoting N, T, and M. Output For each test case, print a single integer. If probability is p/q where p & q are co-prime, print (p*mulInv(q)) modulo 1000000007, where mulInv(x) is multiplicative inverse of x under modulo 1000000007. Timeout 1 Test Case Example 1 Input
Answers
Answer:
There is a test of Algorithms. Teacher provides a question bank consisting of N questions and guarantees all the questions in the test will be from this question bank. Due to lack of time and his laziness, Codu could only practice M questions. There are T questions in a question paper selected randomly. Passing criteria is solving at least 1 of the T problems. Codu can’t solve the question he didn’t practice. What is the probability that Codu will pass the test?
Input Format
First line contains single integer T denoting the number of test cases.
First line of each test case contains 3 integers separated by space denoting N, T, and M.
Output Format
For each test case, print a single integer.
If probability is p/q where p & q are co-prime, print (p*mulInv(q)) modulo 1000000007, where mulInv(x) is multiplicative inverse of x under modulo 1000000007.
Constraints
0 < T <= 10000
0 < N, T <= 1000
0 <= M <= 1000
M,T <= N
Sample Input and Output
Example 1
Input
1
4 2 1
Output
500000004
Solution —
#include< >
int combinations(int n, int r)
{
int itr,numerator=1,denominator=1,result;
for(itr=1; itr<=r; itr++)
{
denominator = denominator*itr;
numerator = numerator*(n-(itr-1));
}
result = numerator/denominator;
return result;
}
int calGCD(int num1,int num2)
{
int rem;
while (1)
{
rem = num1 % num2;
if(rem == 0)
return num2;
if(rem != 0)
{
num1 = num2;
num2 = rem;
}
}
}
int mulInv(int a)
{
unsigned long long int m=1000000007,itr,b;
for (itr = 1; itr 0)
{
scanf(“%llu\t%llu\t%llu”,&qb_questions,&choosen,&learnt);
unknown = qb_questions – learnt;
waysOfChoosing = combinations(qb_questions,choosen);
waysOfFailing = combinations(unknown,choosen);
p = waysOfChoosing – waysOfFailing;
q = waysOfChoosing;
gcd = calGCD(p,q);
if(gcd != 1)
{
p=p/gcd;
q=q/gcd;
}
result = (p*mulInv(q))%1000000007;
printf(“%llu”,result);
T–;
}
return 0;
}
Language used: Python 3.0
Program:
import math
n=int(input())
for i in range(n):
N,T,M = map(int,input().split(' '))
probability=(1-(math.factorial(N-M))/(math.factorial(T)*math.factorial(N-M)))
#taking in the values of p,q from probability as of p/q
p,q=probability.as_integer_ratio()
#creating the multiple inverse of q
print(pow(q,1000000007-2,1000000007))
Input:
1
4 2 1
Output:
500000004
Learn more:
1. Hockey Problem
brainly.in/question/12306355
2. Numerical belly problem
brainly.in/question/16880104