Miss DD and Her Probability Lessons
All submissions for this problem are available.
Mr Divyank and Miss DD are famous for their love stories. Divyank is not very good in solving probability problems. So Miss DD gave him some lessons on basic probability and to check whether he can now solve probability problems or not she gave him the following problem.
You are given a lot containing first N natural numbers with chances of taking ith number as Pi per cent and you are required to perform exactly K steps as follows:
At each step you toss an unbiased coin, if it’s a head you pick up a number from the lot and remove it from there. If the lot is empty you are given the magical number 7.
If it’s tail you don’t take any number and simply move ahead to perform the next step.
After you are done performing all the K steps, what is the probability that sum of numbers you took is even?
The first line contains a single integer T, denoting the number of testcases. The descriptions of T test cases follow.
First line of each test case contains two space separated integers K and N.
Second line contains N space separated integers representing percentage probability of taking ith number.
It is guaranteed that the sum of percentages of the given array is exactly 100 .
For each test case calculate the required probability in a new line up to 6th decimal digit.
- 1 ≤ T ≤ 10.
- 1 ≤ N ≤ 16.
- 1 ≤ K ≤ 20.
Input: 1 2 2 80 20 Output: 0.350000
|Time Limit:||5 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.