\begin{tutorial}{IQ Game}

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

Воспользуемся формулой подсчета математического ожидания неотрицательной целочисленной случайной величины $X$: $$\mathbb{E}X = \mathbb{P} (X > 0) + \mathbb{P} (X > 1) + \ldots$$ Интуитивно ее можно интерпретировать следующим образом: чтобы найти матожидание числа оставшихся раундов, посчитаем вероятность, что мы сыграем первый раунд ($\mathbb{P} (X > 0) = 1$), прибавим вероятность, что мы сыграем второй раунд ($\mathbb{P} (X > 1)$) и так до бесконечности (но в нашей задаче $\mathbb{P} (X > k) = 0$, и дальше суммировать смысла нет).

Повернем стол так, чтобы гиперблиц оказался в ячейке с номером $1$, и пронумеруем оставшиеся вопросы в порядке \textbf{против часовой стрелки}: $1 < q_2 < q_3 < \ldots$. В каких ситуациях после $m$ вопросов ни разу не выпал гиперблиц?

\begin{itemize}
\item В полуинтервал $[1, q_2)$ мы не должны попасть ни разу,
\item В полуинтервал $[1, q_3)$ мы можем попасть не более одного раза,
\item В полуинтервал $[1, q_4)$ мы можем попасть не более двух раз,
\item ...
\item В полуинтервал $[1, q_i)$ мы можем попасть не более $i-2$ раз.
\end{itemize}

Посчитать вероятность таких исходов можно, используя динамическое программирование.
Обозначим за $P_{i, j}$ вероятность события <<После $j$ раундов не выпал гиперблиц, а все выпавшие сектора принадлежали первым $i$ полуинтервалам>>. Чтобы сделать переход из такого состояния, переберем, сколько раз волчок указывал на сектор внутри $i+1$-го полуинтервала (обозначим это за $x$), и перейдем в $P_{i+1, j+x}$, при условии, что $j + x$ не превосходит $i - 1$. Вероятность перехода при этом нужно домножить на ${j + x \choose x} (\frac {q_{i+1} - q_i}n)^x$: выбрать, какие $x$ из $j + x$ попали в текущий полуинтервал, и вероятность каждого отдельного выпадания ($x$ раз).

После обработки всех полуинтервалов слева направо, на основе значений $P_{k, *}$, используя самую первую формулу из этого разбора, можно найти матожидание. Всего в решении $O(k^2)$ состояний, а каждый переход занимает $O(k)$ времени. Общее время работы~--- $O(k^3)$.

\end{tutorial}
