P5415 [YNOI2019] Game

After a long brain-burning journey, your minds should now be fully active. Finally, let us play a game to end this adventure full of fun and challenges. There are $n$ people playing a game. The rules are as follows. Before the game starts, the $n$ people are uniquely numbered from $1$ to $n$. After the game starts, in each round only $4$ people are allowed to play, and all others form a waiting queue in the order of their numbers, waiting to join the game. In the game, everyone has an equal chance to win. The game is held over multiple rounds. In each round, the winner may continue to participate in the next round, while the losers will be placed at the end of the waiting queue according to their order before the start of this round (if any of the losers in this round won the previous round, then that person will be placed in the waiting queue in front of all losers of this round). For example, before a certain round starts, Xiaoming is ahead of Xiaohong and Xiaogang. If in that round Xiaoming, Xiaohong, and Xiaogang all do not win, then they will leave the game and be placed at the end of the waiting queue, and Xiaoming will still be ahead of Xiaohong and Xiaogang according to their order before the round starts. A special case is that if Xiaogang won the previous round before this round, then Xiaogang will be placed ahead of Xiaoming and Xiaohong in the waiting queue. During the game, if someone wins consecutively for $m$ times, then they are the final winner of the game. Your task is to predict the probability that person $k$ becomes the final winner.

**The input contains multiple test cases.** The first line contains a positive integer $T$, representing the number of test cases in the input file. Next come $T$ test cases, each in the following format. Each test case consists of one line containing three integers $n, m, k$.

Output $T$ lines, corresponding to the answers for the $T$ test cases, i.e. the probability that person $k$ becomes the final winner (rounded to $6$ decimal places).

#### Constraints - For $30\%$ of the testdata: $n \le 5$, $m \le 5$. - For $60\%$ of the testdata: $n \le 8$, $m \le 8$. - For $100\%$ of the testdata: $4 \le n \le 10$, $0 < m \le 10$, $1 \le k \le n$, and except for the samples, $T = 1$. Translated by ChatGPT 5