Задача . C. Уровни и регионы

Радевуш играет в компьютерную игру, которая состоит из n уровней, пронумерованных от 1 до n. Уровни разбиты на k регионов (групп), каждый регион является непустым множеством последовательных уровней.

Игровой процесс состоит в повторении следующих действий:

1. Если все уровни уже пройдены, то игра немедленно заканчивается. Иначе система определяет первый регион, в котором есть хотя бы один ещё не пройденный уровень. Обозначим этот регион за X.
2. Создаётся пул для токенов. Каждый токен будет представлять один уровень, при этом несколько токенов могут представлять один и тот же уровень.
   • Для каждого уже пройденного уровня i из региона X система добавляет в пул t_i токенов, которые будут представлять этот уровень.
   • Пусть j — это минимальный ещё не пройденный уровень (с минимальным номером) в регионе X. Система добавляет в пул t_j токенов.
3. Затем система случайно и равновероятно выбирает из пула один токен, и игрок проходит соответствующий уровень. На прохождение уровня он тратит один час, независимо от того, проходил он его до этого или нет.

Вам даны n, k и значения t₁, t₂, ..., t_n, требуется разбить уровни на регионы. Каждый уровень должен принадлежать ровно одному региону, и каждому региону должно соответствовать непустое множество последовательных уровней. Чему равно минимальное математическое ожидание времени прохождения игры?