\begin{tutorial}{Lucky Number Theory}

{
    \parindent=1cm
    \begin{tabular}{l@{\extracolsep{1cm}}l}
         Идея: & Артем Васильев \\
         Разработка: & Артем Васильев \\
     \end{tabular}
}

Начнем решать задачу со случая $d = 1$. Заметим, что стратегия зависит только от дробной части $S$ (обозначается $\{ S \}$): все действия для $S$ и $S + 1$ можно делать одинаково, и результат всегда будет отличаться на единицу. 

Важное наблюдение: вне зависимости от текущего распределения $S$, после броска, новое значение $\{ S' \}$ будет иметь равномерное распределение от 0 до 1.

Благодаря этому наблюдению, мы можем предполагать, что на каждом шаге значение $\{ S \}$ равномерно распределено от 0 до 1, что позволяет использовать динамическое программирование. Обозначим за $f_{n, k}$ матожидание оптимальной стратегии, если осталось $n$ бросков, $k$ возможностей вывести, в предположении, что в начале $\{ S \}$ распределено равномерно от 0 до 1.

Обозначим $\{ S \} = x$. В зависимости от $x$, есть два случая: бросить еще раз, либо вывести билеты и бросить еще раз. В первом случае матожидание числа билетов равно $x + f_{n-1, k}$: вероятность того, что после броска целая часть $S$ увеличится, равна $S$, и мы переходим в состояние с $n-1$ броском. Во втором случае матожидание равно $1 + f_{n-1,k-1}$: мы гарантированно получаем один билет сейчас, и переходим в состояние $(n - 1, k - 1)$. Все переходы корректны из-за наблюдения выше: несмотря на то, что мы используем $x$ для принятия решения, после броска, $\{ S \}$ все еще будет распределено равномерно от 0 до 1.

Так как $x$ распределено равномерно от 0 до 1, нужно взять максимум из двух случаев, и проинтегрировать по $x$ от 0 до 1: $f_{n, k} = \int\limits_0^1 \max(x + f_{n-1, k}, 1 + f_{n-1,k-1}) dx$. Если обозначить $A = f_{n-1,k}$, $B = 1 + f_{n-1,k-1}$, то для $x \ge B - A$ максимум достигается в первом случае, а для $x < B - A$~--- во втором. Опустив промежуточные вычисления, получаем формулу для ДП: $f_{n, k} = A + \frac 12 + \frac 12 (B - A)^2$, которую можно вычислить за $O(n^2)$ сразу для всех возможных пар $(n, k)$. Итоговый ответ на задачу равен $f_{n - 1, k - 1} + 1$, учитывая первый бросок и последний вывод, который дает +1 к ответу.

Наконец, случай $d > 1$. Заметим, что сгенерировать случайное вещественное число в интервале $(0, d)$ это то же самое, что сгенерировать случайное вещественное число от 0 до 1, а заметим прибавить случайное \textit{целое} число от 0 до $d - 1$ включительно. Добавление случайного целого числа никак не влияет на стратегию, только на ответ: на каждый бросок в среднем прибавится $\frac 1d (0 + 1 + \ldots + d-1) = \frac {d-1}2$ билетов. Ответ на задачу равен решению для $d = 1$ плюс $\frac {d-1}{2} n$.

\end{tutorial}
