Shriraj and Maze
All submissions for this problem are available.
Shriraj loves tasty food. He can go miles in search of good restaurant, even if nobody is accompanying him.
One day, Shriraj wandered off too much, and got himself trapped in a maze. In the maze there are N doors, numbered from 1 to N. Behind each door is a key to some other door. No two doors hold a key to the same door. Shriraj has been in similar situations many times, so he carries M master keys. A master key can open any door, but one master key can only be used once. Once he opens a locked door, he can get the key in it and perhaps open another locked door with that key. His strategy is to select a door, open it with a master key, take the key and open all the doors he can and then repeat with another master key.
The task for you is to find the probability that Shriraj can unlock all N doors with M master keys. You can assume that all keys have equal probability of being behind a door, and all key and door configurations are equally likely.
Input will contain multiple test cases. The first line of input denotes T, the number of Test cases. T test cases follow.
Each test case contains two space seperated integers, N and M . Each test case will be on a seperate line.
Output the probability in "A/B" form (without quotes), where A and B are positive integers without leading zeros and A/B is an irreducible fraction. See the sample case for clarity.
Probability zero should be given as 0/1.
- 1 ≤ T ≤ 20
- 1 ≤ N ≤ 20
- 0 ≤ M ≤ N
Input: 4 2 1 2 2 3 1 4 2 Output: 1/2 1/1 1/3 17/24
|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.