{
    \parindent=1cm
    \begin{tabular}{l@{\extracolsep{1cm}}l}
         Идея: & Михаил Иванов\\
         Разработка: & Михаил Иванов\\
     \end{tabular}
}

Существует множество способов решения этой задачи. Одно из семейств решений выглядит следующим образом: зафиксируем два параметра $w \in \mathbb{Z}_{>0}$ и $k \in [0; 1]$. Попробуем применить функцию Коллатца к текущему числу $w$ раз. Если за это время мы достигли единицы, то применяем функцию Коллатца. Если мы применили функцию Коллатца к нечётному числу не более чем $kw$ раз, то мы также применяем функцию Коллатца (интуитивно, чем меньше мы применяем функцию Коллатца к нечётному числу, тем меньше мы умножаем его на три и тем больше делим на два, таким образом, в среднем мы быстрее уменьшаем число, отображаемое на экране). В противном случае применяем случайную функцию.

Одна из причин, по которой это решение может работать плохо, заключается в том, что оно иногда может увеличить чётное число. С вероятностью $50\%$ оно становится нечётным, и возможность его уменьшить вдвое упускается. Лучше сначала уменьшить число вдвое, а затем применить случайную функцию. Чтобы решить эту проблему, давайте объединим стратегию $(w, k)$ со стратегиями $(1, k), \ldots, (w-1, k)$: то есть, если хотя бы для одного положительного целого числа $v \le w$ в ближайшие $v$ итерациях функции Коллатца мы увеличили число не более чем $kw$ раз, то нам лучше применить Коллатца. Эта обновленная стратегия уже проходит все тесты для $w = 11$, $k = 0.37$. Чтобы получить пару хорошо работающих параметров, можно перебрать случайные пары параметров и проверить производительность каждой из них на многих случайных входных данных.

Еще одна стратегия заключается в том, чтобы попытаться построить (почти) оптимальное решение. Давайте выберем границу $N$ и создадим массив чисел с плавающей точкой $\mathrm{dp}[1..N]$, обозначающий математическое ожидание оценки оптимальной стратегии, начинающейся с каждого числа. Инициализируем его оценкой, достигнутой только при применении функции Коллатца. Затем давайте пройдем по массиву $s$ раз, каждый раз обновляя каждое значение $dp[i]$ минимумом оценки, достигнутой при применении Коллатца (и оптимальным продолжением), или средним значением по $a[3i + 1..6i]$, в зависимости от того, что меньше. Чтобы вычислить среднее значение по $a[3i + 1..6i]$, мы можем воспользоваться алгоритмом скользящей суммы (также известным как алгоритм оконной суммы). Этот алгоритм проходит тесты для $N = 10^7$, $s = 19$ (и, конечно, для многих других пар).