Expected Unlocks in the Toy Box Game

A precious toy box contains L locks and a keyring with L+K keys. Exactly L of these keys can open the locks; each such key is uniquely matched with one lock, while the remaining K keys are mere decoys. The matching between keys and locks is secret – initially, any key unlocks any lock with the same probability.

Game rules:

• There are N players (including M) taking turns in a fixed cyclic order.
• In each turn the current player selects one available (unused) key and one available lock, and tries to open that lock with that key.
• If the attempt is successful, the chosen key and lock are both removed from the game. If the attempt fails, nothing is removed.
• The players have perfect knowledge of all previous attempts (both successes and failures) and therefore in every turn they use an optimal strategy – that is, they choose (from the remaining keys and locks) one combination that maximizes the probability of success. (If more than one pair gives the maximum success probability they choose uniformly among them.)
• The game ends as soon as all L locks have been opened.

Probability model:

Before any attempts are made, exactly L keys are the "correct" keys (each opening a unique lock) and the K remaining keys are useless decoys. Since the secret matching is uniformly distributed among all possibilities, for any unused key the chance that it is a correct key is L/(L+K) (or, more generally, if there are r locks remaining then the number of active (correct) keys among the unused keys is exactly r). When a player picks a key and a lock, if the chosen key is one of the r active keys then it is matched to a unique lock; therefore the chance that the selected key is the one actually matched with the chosen lock is 1/r. In consequence, no matter which available pair is chosen the success probability in that turn is

\( \frac{r}{(r+K)} \times \frac{1}{r} = \frac{1}{r+K} \).

Note that if an attempt fails neither the key nor the lock is removed, so subsequent attempts in the same state are made with the same available set. Once an attempt succeeds, both the used key and its lock are removed. Thus, if the current state has r locks remaining, the number of available keys is r+K.

Problem:

Assume every player in every turn always chooses a key–lock pair among the available ones that maximizes the success probability (which is \( 1/(r+K) \) in the current state). Let the game start with state \( (r, A) = (L, L+K) \) and with the first player (player index 0) taking the first turn. The turns continue cyclically. For each unlocking (i.e. each successful attempt) the turn in which success occurs is determined by a geometric distribution with parameter \( 1/(r+K) \). More precisely, in a state with r locks remaining (and thus a = r+K available keys), the number of attempts until a success is a geometric random variable with parameter \( 1/a \). If we number the turns within the current round starting at 0 (with the first attempt in that round made by the current starting player), then the probability that the success occurs on the attempt with offset \( i \) (where \( i \ge 0 \)) is given by

[ P(X = i) = \left(\frac{a-1}{a}\right)^i \cdot \frac{1}{a}. ]

However, because players take turns in a cycle of N and only the remainder ( i \mod N ) affects who gets the success, one may combine the probability mass over all ( i ) giving the success to the player at offset ( j ) (0-indexed) in the round. That is, if ( q = \left(\frac{a-1}{a}\right)^N ), then the probability that the player at offset ( j ) secures the success in the round is

[ P(j) = \frac{\left(\frac{a-1}{a}\right)^j \cdot \frac{1}{a}}{1 - q}, \quad j = 0, 1, \ldots, N-1. ]

After a success, the state updates to \( (r-1, r-1+K) \) and the next round starts with the player following the one who just succeeded. Overall, the game ends after exactly L successes.

Your task is to compute, given the numbers N, L and K, the expected number of locks unlocked (i.e. successful attempts) by each of the N players when they all play optimally.

inputFormat

The input consists of a single line containing three integers N, L and K (1 ≤ N ≤ 10, 1 ≤ L ≤ 50, 0 ≤ K ≤ 50), where

• N is the number of players,
• L is the number of locks, and
• K is the number of decoy keys (so that the total number of keys is L+K).

outputFormat

Output N numbers separated by spaces. The i^th number (0-indexed, with the first player considered index 0) represents the expected number of locks unlocked by that player. Answers within an absolute or relative error of 10^-6 will be accepted.

sample

2 1 1

0.666667 0.333333