Internet Problem Solving Contest

• Easy input data set – R1
• Hard input data set – R2

You went out to celebrate with your n − 1 friends. You all got drunk and decided that playing Russian Roulette with a paintball gun sounds like a great idea.

Problem specification

The gun is a revolver with c chambers (c ≥ n). Exactly n − 1 of those chambers now contain a paintball, all others are empty.

The game has one other parameter: a positive integer constant k.

At the beginning of the game all n players stand around a circle. We will number the players 0 through n − 1 as they’re standing in clockwise order. Player number 0 takes the gun. The game is then played by repeating the following three steps until the gun becomes empty:

1. The person who has the gun uses it on themselves. This means that they spin the cylinder to choose one of the chambers uniformly at random and then they point the gun on themselves and pull the trigger.

2. If the chosen chamber was empty, there are exactly k rounds of passing the gun. In each round the person who has the gun passes it clockwise to the next person who is still playing the game.

3. If the chamber contained a paintball, the person is hit by the paintball and loses the game. In this case, they just pass the gun to the next playing person clockwise and they leave the game.

The winner is, obviously, the only person who doesn’t get shot.

You are given the parameters n, c, and k. Compute where you should stand at the beginning of the game in order to maximize your probability of winning. Also, compute the exact value of that probability.

Input specification

The first line of the input file contains an integer t specifying the number of test cases. Each test case is preceded by a blank line.

Each case consists of a single line with the integers n, c, and k. You may assume that 1 ≤ k ≤ n ≤ c.

In the easy subproblem R1 you may assume that c ≤ 10.

In the hard subproblem R2 you may assume that c ≤ 1000.

Output specification, easy subproblem R1

For each test case, print one line containing two space-separated numbers: your position at the beginning of the game which maximises the probability of winning and the probability of winning when standing at that position.

Output the probability as a floating-point number with at least five decimal places. Answers with absolute or relative error up to 10⁻⁴ will be accepted.

You may assume that in each test case the optimal position is unique and that the probability of winning for the optimal position differs from the probability for any other position by more than 10⁻⁶.

Output specification, hard subproblem R2

For each test case, print one line containing two space-separated numbers: your position at the beginning of the game which maximises the probability of winning and a number that encodes the probability of winning when standing at that position, as defined below.

If there are multiple optimal positions, output the smallest one of them.

Let the maximum probability of winning be an irreducible fraction of the form p/q. In order to output this probability, print the number pq⁻¹ modulo (10⁹ + 9), where q⁻¹ is the modular inverse of q modulo 10⁹ + 9. It is guaranteed that the maximum probability of winning can be expressed as a fraction and that the modular inverse of q exists.

Example, easy subproblem R1

Input:

3

3 3 1

2 2 2

4 5 3

Output:

2 0.5076923077
1 1.0000000000
2 0.4105090312

In the first example, each player passes the gun to the next person clockwise. Intuitively, you should go as late as possible – stand counter-clockwise from the person who starts. This turns out to be the optimal strategy. The exact probability of winning for player 2 is 33/65.

In the second example, player number 0 keeps on using the gun until they lose the game. (After each unsuccessful shot the gun gets passed twice, which brings it back to player 0.) Hence, the probability of winning is 1 for player 1 and 0 for player 0.

In the third example, the following happens, in order:

• While there are four players, each time they pass the gun clockwise three times, it is as if they passed it counter-clockwise once. The gun essentially travels counter-clockwise around the circle until a person shoots themselves.
• The next person clockwise gets the gun. This person now keeps trying to shoot themselves until they succeed – which they eventually will.
• The remaining two people take alternating shots until one of them loses.

The probabilities of winning for players 0, 1, 2, 3 are 40/609, 100/609, 250/609, and 219/609, respectively.

Example, hard subproblem R2

For the sample input shown above the correct output for subproblem R2 looks as follows:

2 661538468
1 1
2 348111662

In the first test case the exact answer is 33/65. Since $65^{-1}\equiv 323\,076\,926 \bmod (10^9+9)$, the second number in the first line of the sample output is $(33\cdot 323\,076\,926) \bmod (10^9+9)=661\,538\,468$.