Game of Iron Thrones
Problem Statement :
You and your friends are playing Game of Iron Thrones. When you play the Game of Iron Thrones, you roll n biased dice together. You know how biased the dice are on each face.
Find the probability that you will get at least K 6's.
Input :
The first line consists of an integer t, the number of test cases. For each test case, the first line consists of two integers n - the number of dice and K - as defined above. The next n lines consists of 6 decimal numbers denoting the probability of getting the corresponding face. (face 1 to 6)
Output:
For each test case, find the probability to get at least K 6's when you roll all the n dice at once. Your solution's absolute or relative error must be strictly less than 10^-2. (i.e. your solution can make mistakes upto 0.01)
Input Constraints :
1 <= t <= 100
1 <= n <= 1000
1 <= K <= 1000
Time Limit :
3 seconds
Sample Input :
4
6 6
0 0 0 0 0 1
0 0 0 0 0.5 0.5
0 0 0 0 0 1
0 0 0 0 0 1
0 0 0 0.5 0 0.5
0 0 0 0 0 1
3 1
0.2 0.2 0.2 0.2 0.2 0
0.2 0.2 0.2 0.2 0.2 0
0 0 0 0 0 1
0.2 0.2 0.2 0.2 0.2 0
0.2 0.2 0.2 0.2 0.2 0
0 0 0 0 0 1
2 1
0.2 0.2 0.2 0.2 0 0.2
0 0 0 0.5 0.25 0.25
Sample Output :
0.25
1
0
0.4
Explanation:
Case 1 : There are 6 dice and we need at least 6 sixes. The probability to get 6 in all dice = 1*0.5*1*1*0.5*1 = 0.25.
Case 2: There are 3 dice and we need exactly one 6. No matter how many times you throw the dice, you will always get atleast one 6.
Case 3 : There are 3 dice and we need at least two 6s. For the given biased dice in which two of them never turns 6 the probability will be 0
Case 4 : Note that there can be more than K 6's. The probability in this case would be 0.2*0.25 + 0.2 * (1-0.25) + (1-0.2) * 0.25 = 0.4
Note : Avoid cout for this problem as it will print the result in scientific notation.