| The 2026 ICPC Belarus Regional Contest |
|---|
| Закончено |
The oldest exhibit in the museum of the Foundation of Fabulous Transformations is a probabilistic machine containing $$$n$$$ light bulbs. On a usual day, it is turned off.
When it turns on during the excursions, the following happens. Within the first second, each bulb lights up independently with probability $$$\frac{1}{2}$$$. After that, at the end of each second, a subset of exactly $$$m$$$ light bulbs is chosen uniformly at random, and each light bulb from that subset is toggled between on and off states.
Unfortunately, the machine no longer works perfectly. When exactly $$$k$$$ light bulbs are on at the end of a second (it can be the first second as well), a bug in the machine is triggered and the process stops.
Find the expected number of seconds after the start until that happens.
We can show that after the first second, it is known whether the process can theoretically stop or not. For the latter case, assume that the expected number of seconds after the start for the process to stop is $$$0$$$.
The only line contains three integers $$$n$$$, $$$m$$$, $$$k$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq m \leq \min(n, 10)$$$, $$$0 \leq k \leq n$$$, $$$\left|2k - n\right| \leq \max(\frac{n}{500}, 10)$$$).
Print a real number: the expected number of seconds before the process stops, under the assumptions from the statement.
The answer will be considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$.
Formally, let your answer be $$$x$$$, and the jury's answer be $$$y$$$. Your answer is accepted if and only if $$$\frac{|x - y|}{\max{(1, |y|)}} \leq 10^{-6}$$$.
3 2 1
0.625000000000
19 5 8
6.722779050519
Consider the first example.
If $$$0$$$ or $$$2$$$ light bulbs are on initially, the process will go on forever (this has probability $$$\frac{1}{2}$$$).
If $$$1$$$ light bulb is on initially, the process stops after $$$1$$$ second (this has probability $$$\frac{3}{8}$$$).
If $$$3$$$ light bulbs are on initially, it will change to $$$1$$$ on the next second, so the process stops after $$$2$$$ seconds (this has probability $$$\frac{1}{8}$$$).
Therefore, the answer is $$$0 \cdot \frac{1}{2} + 1 \cdot \frac{3}{8} + 2 \cdot \frac{1}{8} = \frac{5}{8}$$$.
| Название |
|---|


