CF1835B Lottery

$ n $ people indexed with integers from $ 1 $ to $ n $ came to take part in a lottery. Each received a ticket with an integer from $ 0 $ to $ m $ . In a lottery, one integer called target is drawn uniformly from $ 0 $ to $ m $ . $ k $ tickets (or less, if there are not enough participants) with the closest numbers to the target are declared the winners. In case of a draw, a ticket belonging to the person with a smaller index is declared a winner. Bytek decided to take part in the lottery. He knows the values on the tickets of all previous participants. He can pick whatever value he wants on his ticket, but unfortunately, as he is the last one to receive it, he is indexed with an integer $ n + 1 $ . Bytek wants to win the lottery. Thus, he wants to know what he should pick to maximize the chance of winning. He wants to know the smallest integer in case there are many such integers. Your task is to find it and calculate his chance of winning.

N/A

N/A

In the first example, Bytek wins for $ 4 $ target values (namely $ 0, 1, 2, 3 $ ) if he chooses integer $ 2 $ , which is the lowest optimal value. If he chooses $ 3 $ , he also wins in four cases, but it is not the lowest value.