Problem: PAPER GENERATION
Problem Description
Ravi needs to set Question papers fairly for his students for an exam. He has three categories of Questions i.e. Simple, Medium, Complex. Each Question paper has one or more simple, medium, complex questions.
For each paper, he needs to choose precisely s out of a set of x simple, precisely m out of a set of y medium and precisely c out of a set of z complex questions.
These questions are labelled A, B, C and so on, with the first x being simple, the next y being medium and the last z being hard.
Write a program that prints the number of possible combination of Question papers
Ravi decides to impose following constraints while selecting the question papers:
Two given questions can't come together in any Question paper
One of the given Question can come in only one Question paper
Remaining Questions can come any number of Question papers
Find how many Question papers can be generated after imposing the constraints.
Constraints
s,m,c > = 1
x > = s, y > = m, z > = c
1 < (s + m + c) < =26
Input Format
The First line contains x, the number of simple questions.
The Second line contains s, the number of simple questions to choose from x.
The Third line contains y, the number of medium questions.
The Fourth line contains m, the number of medium questions to choose from y.
The Fifth line contains z, the number of complex questions.
The Sixth line contains c, the number of complex questions to choose from z.
The Seventh line contains the question pair that cannot be the part of the same Question paper, delimited by single space.
The Eighth line contains the Question that should be asked only in one of the Question Papers.
Output
The First line contains total number of Question papers possible without any constraints.
The Second line contains total number of Question papers after imposing all the constraints.
Time Limit
1
Explanation
Example 1
Input
3
2
4
3
3
2
A D
G
Output
36
4
Explanation:
From the input we know that there are 3 simple, 4 medium and 3 complex questions.
First x as per the alphabetical order are simple questions, next y are medium questions and remaining z are complex questions. The total number of Question papers that can be generated without imposing constraints is 36.
As Questions A and D cannot be cannot be in the same Question Paper and Question G can exist only in one of the Question paper, the maximum number of Question papers that can be generated after imposing constraints is 4.
And one of the possible set of 4 question papers is:
ABEFGHI
BCDEFHI
BCDEFHJ
BCDEFIJ
Example 2
Input
3
2
3
2
3
2
A C
D
Output
27
7
Explanation:
From the input we know that there are 3 simple, 3 medium and 3 complex questions.
First x as per the alphabetical order are simple Questions,next y are medium Questions and remaining z are complex Questions. The total number of Question papers that can be generated without imposing constraints is 27.
As Questions A and C cannot be cannot be in the same Question Paper and Question D can exist only in one of the Question paper, the maximum number of Question papers that can be generated after imposing constraints is 7.
And one of the possible sets of 7 question papers is:
ABDEGH
ABEFGI
ABEFHI
BCEFGH
BCEFGI
BCEFHI
Solution:
def ncr(n, r):
return fac(n)/(fac(n-r)*fac(r))
def fac(F):
ans = 1 while F > 0:
ans= ans * F
F = F - 1;
return ans
s = int(input("Enter no. Of Simple Questions:"))
if(s < 1):
print("The Value Of Simple Questions Is always >= 1.")
exit(0)
sc = int(input("Enter no. of Simple Questions to choose from s:"))
if(sc > s and sc < 1):
print("The Value Of Choose Simple Questions Is always >= 1 and <= Simple Questions.")
exit(0)
m = int(input("Enter no. Of Medium Questions:"))
if(m < 1):
print("The Value Of Medium Questions Is always >= 1.")
exit(0)
mc = int(input("Enter no. of Medium Questions to choose from m:"))
if(mc > m and mc <1):
print("The Value of Choose Medium Questions Is always >= 1 and <= Medium Questions.")
exit(0)
c = int(input("Enter no. Of Complex Questions:"))
smc = s+m+c
if(c < 1):
print("The Value Of Complex Questions Is always >= 1.")
exit(0)
elif(smc > 26):
print("The Sum Of Simple, Medium and Complex Questions are always <= 26")
exit(0)
cc = int(input("Enter no. of Complex Questions to choose from c:"))
if(cc > c and cc < 1):
print("The Value Of Choose Complex Questions Is always >= 1 and <= Complex Questions.")
exit(0)
ch = 'A'st = []
st.insert(0, ch)
for i in range(1,smc):
ch = chr(ord(ch)+1)
st.insert(i, ch)
i+=1
che=0
a1 = list(map(str,input("Enter Two Questions(separated by single space)
(use only Alphabets):").split(" ")))
for char in a1:
if char.isalpha() == True:
continue else:
print("String contains only alphabets!!Give Input Again!!")
exit(0)
for i in range(0,smc):
if(a1[0] == st[i]):
che+=1 elif(a1[1] == st[i]):
che+=1
if che != 2:
print("This Question Paper is not in the list of Question Paper")
exit(0)
check=0a2 = (input("Enter Question which can come in only one question paper:"))[0]
a3 = a2.upper()
if a3.isalpha() == False:
print("String contains only alphabet!!Give Input Again!!")
exit(0)
for i in range(0,smc):
if(a3 == st[i]):
check=1 break;
if check == 0:
print("This Question Paper is not in the list of Question Paper")
exit(0)
ans = int(ncr(s,sc)*ncr(m,mc)*ncr(c,cc))
print("The total number of Question papers that can be generated without imposing
constraints is ", ans)
x=0
y=0
z=0
output = int(ord(a1[0])-ord('A'))+1
if output <= s:
x+=1elif output <= (s+m):
y+=1else:
z+=1
output = int(ord(a1[1])-ord('A'))+1if output <= s:
x+=1elif output <= (s+m):
y+=1else:
z+=1
ans = int(ans - (ncr(s-x,sc-x)*ncr(m-y,mc-y)*ncr(c-z,cc-z)))
output= int(ord(a3)-ord('A'))+1if output <= s:
x+=1 ans = int(ans - (ncr(s - 1, sc - 1) * ncr(m, mc) * ncr(c, cc)))
elif output <= (s+m):
y+=1 ans = int(ans - (ncr(s, sc) * ncr(m-1, mc-1) * ncr(c, cc)))
else:
z+=1 ans = int(ans - (ncr(s, sc) * ncr(m, mc) * ncr(c-1, cc-1)))
ans = int(ans + 1 + ncr(s-x,sc-x)*ncr(m-y,mc-y)*ncr(c-z,cc-z))
print(" the maximum number of Question papers that can be generated after imposing
constraints is", ans)
Comments