502001 - 酒店检查

【题目描述】酒店检查(detective)

侦探因为一个案件而检查酒店的N个房间。酒店的所有的房间都被紧锁,每个房间中随机锁了一把钥匙。例如当N=3时,有6个可能的分布,每一个可能性是1 / 6。为方便起见,我们从将房间号从1编号到N,房间1号的钥匙编号为1,2号房间的钥匙编号为2…,要检查所有的房间,就必须用破坏一些门。但又不想破坏太多,所以策略为:在没有钥匙的时候,可以随机破坏一扇门,取出其中的钥匙,尝试用钥匙打开另外的门(然后取出钥匙去打开另外的门,直到不能打开任何的门的时候,接着破坏另外的门)。但要注意:不允许破坏1号房间的门而只能用钥匙打开,因为有一个非常重要的人住在1号房间。 侦探最多可以破坏k(k≤n)扇门,但是第一扇门只能用钥匙打开。求所有门能被打开(被破坏,或是被钥匙打开)的概率。

输入

第一行是一个整数T (T≤200),表示测试数据的个数。 以后每行包含两个整数N和k(1<N≤20,1≤k<N)。

输出

每组测试数据输出一行,表示相应的可能性。小数点后的四位数字保存为四舍五入。

样例

输入

3
3 1 
3 2
4 2

输出

0.3333
0.6667
0.6250

提示

【样例解释】 当N=3,有6种可能:

房间1	房间2	房间3	破坏次数

1 Key 1 Key 2 Key 3 不可能

2 Key 1 Key 3 Key 2 不可能

3 Key 2 Key 1 Key 3 2

4 Key 3 Key 2 Key 1 2

5 Key 2 Key 3 Key 1 1

6 Key 3 Key 1 Key 2 1

在前2个可能性中,因为钥匙1是锁定在1房间的本身,而侦探不能破坏房间1,所以不可能打开房间1。 在第3和第4个可能性中,侦探必须摧毁2和3的房间。在最后2个可能性中,侦探只需要摧毁一个房间。

时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题