[YNOI2019]游戏

题目描述

在经历了漫长的烧脑之旅后,相信同学们的思维已经充分地活跃起来了。最后,让我们玩一个游戏来结束这次充满乐趣和挑战的冒险之旅! 有n个人在玩游戏,游戏规则如下: 在游戏开始之前,将这n个人按照1~n的顺序唯一编号。游戏开始后,每一轮只允许4个人进入游戏,其他人按照各自的编号组成等待队列,等待参加游戏。 游戏中每个人赢得比赛的机会是同等的,游戏举办多轮,每一轮的获胜者可以继续参加下一轮的比赛,输家将根据本轮比赛开始之前的顺序排在等待队列的末尾(如果本轮的输家中有人之前赢得过比赛,那么他将在等待队列中排在本轮所有输家的前面)。 例如,在某一轮比赛开始之前小明排在小红和小刚前面,如果在该轮比赛中小明、小红和小刚都没有赢,那么小明、小红和小刚将退出比赛排在等待队列的末尾,但是小明将会继续按照比赛开始之前的顺序排在小红和小刚前面。存在的特殊情况是,如果小刚在这轮比赛之前赢得过比赛,那么小刚将在等待序列中排在小明和小红的前面。 比赛中,如果有人连续赢了m次,那么他就是这个游戏最后的赢家。你的任务是,预测第k个人成为最终赢家的可能。

输入输出格式

输入格式


输入文件名为game.in。 每个输入文件包含多组数据。 输入文件的第一行,包含一个正整数T,代表该输入文件中所含的数据组数。 接下来是T组数据,每组数据的格式如下: 每组数据仅一行,包含3 个整数n,m,k,其中(4 ≤ n ≤ 10,0 < m ≤ 10,k ≤ n)。

输出格式


输出文件名为game.out。 输出文件包含T行,分别对应T组数据的答案,即第k个人成为最终赢家的可能(结果保留6 位小数)。

输入输出样例

输入样例 #1

3
4 1 1
5 1 5
5 2 1

输出样例 #1

0.250000
0.000000
0.217626

说明

对于30%的数据:(4 ≤ n ≤ 5,0 < m ≤ 5,k ≤ n)。 对于60%的数据:(4 ≤ n ≤ 8,0 < m ≤ 8,k ≤ n)。 对于100%的数据:(4 ≤ n ≤ 10,0 < m ≤ 10,k ≤ n)。 我不会告诉你事实上所有测试数据中 T=1。