All submissions for this problem are available.
To celebrate the success of the latest edition of his famous book, Cormen wants to distribute candies among kids. Some critics argue that this is his way of apologizing to the thousands of students across the globe who struggle with the intricacies in his books on a daily basis; but for the sake of the question, it shall suffice to assume that he is distributing candies only for celebration purposes.
He has N distinct candies with him, numbered from 1 to N. Cormen selects NC2+N kids, and allots each of them a continuous range of candies that he might ask for. No two kids are allotted the same range. Now he asks every kid whether or not he wants his share of candies. Unlike the majority of us, these kids are not candy-lovers and they might or might not ask for their share of candies, each with probability ½.
Cormen can give a particular candy to exactly one kid. Every kid who asks his share of candies
must be given the entire range of candies allotted to him, or none at all. Cormen wants to
maximise the number of happy kids, and thus, among all the kids who asked for candies, he will
give candies to the maximum number of kids possible, satisfying the above constraints. Cormen
wants to know what is the probability that K kids are given their share of candies.
- First line contains T, the number of Test cases.
- Each test case contains 2 integers: N and K.
- For every test case, output the required probability rounded to exactly 9 digits after the
- 1 ≤ T ≤ 10000
- 1 ≤ N ≤ 100
- 0 ≤ K ≤ 100
Input: 2 1 1 2 1 Output: 0.500000000 0.625000000
|Time Limit:||1 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.