Парадокс Монти Холла — одна из известных задач теории вероятностей, решение которой, на первый взгляд, противоречит здравому смыслу.
Представьте, что вы стали участником игры, в которой вам нужно выбрать одну из трёх дверей. За одной из дверей находится автомобиль, за двумя другими дверями — козы. Вы выбираете одну из дверей, например, номер 1, после этого ведущий, который знает, где находится автомобиль, а где — козы, открывает одну из оставшихся дверей, например, номер 3, за которой находится коза. После этого он спрашивает вас — не желаете ли вы изменить свой выбор и выбрать дверь номер 2? Увеличатся ли ваши шансы выиграть автомобиль, если вы примете предложение ведущего и измените свой выбор?
С одной стороны, после того, как ведущий открыл дверь, осталось две закрытых двери - и вы можете ошибочно предположить, что вероятность автомобиля за каждой — . Объяснение простое — изначально вероятность нахождения автомобиля за каждой из дверей — , и она осталась такой после того, как ведущий открыл одну из оставшихся дверей. Соответственно при таком раскладе автомобиль находится за выбранной вами дверью с вероятностью и за оставшейся с вероятностью .
Приведем еще более наглядный пример: у вас есть тысяча дверей, вам разрешено выбрать одну, после чего ведущий открывает 998 из 999 оставшихся дверей. Вероятность того, что автомобиль за вашей дверью — . Соответственно, вероятность, что автомобиль находится за одной из оставшихся 999 равна . А т.к. из оставшихся ведущий нам оставил лишь одну дверь, то именно на нее приходится эта вероятность.
Теперь перейдем к нашей задаче, перед вами n дверей - вам разрешено открыть k из них, после этого ведущий обязательно откроет m (m < n - k) из оставшихся дверей, после чего предложит поменять любое количество выбранных дверей. Какая вероятность вашего выигрыша при оптимальной стратегии?
В единственной строке даны три числа n, k, m (1 ≤ n, k, m ≤ 105, k + m < n).
В единственной строке выведите вероятность своей победы при оптимальном выборе. Абсолютная или относительная погрешность не должна превышать 10 - 6.
## Входные Данные
В единственной строке даны три числа n, k, m (1 ≤ n, k, m ≤ 105, k + m < n).
## Выходные Данные
В единственной строке выведите вероятность своей победы при оптимальном выборе. Абсолютная или относительная погрешность не должна превышать 10 - 6.
## Примеры
Входные данные3 1 1Выходные данные0.6666666666666667Входные данные1000 1 998Выходные данные0.999Входные данные5000 2345 1234Выходные данные0.7158
[samples]
**Definitions**
Let $ n, k, m \in \mathbb{Z}^+ $ such that $ 1 \leq k, m \leq 10^5 $, $ k + m < n $.
**Setup**
- There are $ n $ doors, behind exactly one of which is a car; the rest hide goats.
- The player initially selects $ k $ distinct doors.
- The host, who knows the location of the car, opens exactly $ m $ of the remaining $ n - k $ doors, all revealing goats.
- The player may then switch any number of their initially chosen doors to any of the unopened, unselected doors (i.e., the $ n - k - m $ remaining closed doors).
**Objective**
Compute the maximum probability of selecting the door with the car under the optimal switching strategy.
**Optimal Strategy**
The optimal strategy is to switch all $ k $ initial choices to the remaining $ n - k - m $ unopened doors, uniformly at random.
**Probability**
Let $ P $ be the probability of winning under optimal play:
$$
P = \frac{k}{n} \cdot 0 + \left(1 - \frac{k}{n}\right) \cdot \frac{k}{n - k - m}
= \left(1 - \frac{k}{n}\right) \cdot \frac{k}{n - k - m}
$$
Simplify:
$$
P = \frac{n - k}{n} \cdot \frac{k}{n - k - m}
= \frac{k(n - k)}{n(n - k - m)}
$$
**Output**
$$
\boxed{\frac{k(n - k)}{n(n - k - m)}}
$$