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. Test Case Explanation Example 1 Input 1 4 2 1 Output 500000004 Explanation The probability is ½. So output is 500000004.
Answers
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. Test Case Explanation Example 1 Input 1 4 2 1 Output 500000004 Explanation The probability is ½. So output is 500000004.
Explanation:
Sample Input and Output
Example 1
Input
1
4 2 1
Output
500000004
The probability is 1⁄2. So output is 500000004.
#include<stdio.h>
unsigned long long int combinations(unsigned long long int n,unsigned long long int r)
{
unsigned long long int itr;
unsigned long long int numerator=1,denominator=1,result;
for(itr=1;itr<=r;itr++)
{
denominator=denominator*itr;
numerator=numerator*(n-(itr-1));
}
result=numerator/denominator;
return result;
}
unsigned long long int calcgcd(unsigned long long int n1,unsigned long long int n2)
{
unsigned long long int rem;
while(1)
{
rem=n1%n2;
if(rem==0)
return n2;
if(rem!=0)
{
n1=n2;
n2=rem;
}
}
}
unsigned long long int mulInv(unsigned long long int a)
{
unsigned long long int m=1000000007,itr,b;
for(itr=1;itr<m;itr++)
{
if((itr*m+1)%a==0)
{
b=(itr*m+1)/a;
break;
}
}
return b;
}
int main()
{
int t,itr;
scanf("%d",&t);
for(itr=1;itr<=t;itr++)
{
unsigned long long int qu,l,c,u;
unsigned long long int wc,wf,p,q,gcd,result;
scanf("%llu %llu %llu",&qu,&l,&c);
u=qu-l;
wc=combinations(qu,c);
wf=combinations(u,c);
p=wc-wf;
q=wc;
gcd=calcgcd(p,q);
if(gcd!=1)
{
p=p/gcd;
q=q/gcd;
}
result=(p*mulInv(q))%1000000007;
printf("%llu\n",result);
}
return 0;
}
Lazy student problem
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