Задача 610
Римские цифры II

Случайный генератор выдает последовательность символов, выбранных из множества {I, V, X, L, C, D, M, #}. Каждый элемент последовательности определяется путем случайного выбора одного из этих символов независимо от других элементов последовательности. В каждом шаге все семь букв имеют одинаковую вероятность быть выбранными, равную 14%, но символ # имеет вероятность выбора всего лишь 2%.

Мы записываем последовательность букв слева направо в том порядке, в каком они сгенерированы, и останавливаемся при первом появлении символа # (его сам при этом не записывая). Однако, мы оговариваем, что записанное нами должно всегда (когда непустое) являться корректной записью числа римскими цифрами в минимальной форме. Если добавление следующей буквы противоречит этому, мы ее пропускаем и пробуем снова со следующим сгенерированным символом.

Пожалуйста, внимательно прочитайте "О римских цифрах", чтобы узнать конкретные правила, определяющие "корректную запись числа римскими цифрами" и "минимальную форму". Например, последовательность (единственная), представляющая число 49 - это XLIX. Субтрактивная комбинация IL некорректна из-за правила (ii), а комбинация XXXXIX - корректна, но не минимальна. Правила никак не ограничивают количество появлений символа M, поэтому все целые числа имеют корректное представление. Эти правила также использовались в Задаче 89, и мы предлагаем вам сначала решить ее.

Найдите ожидаемое значение числа, представленного тем, что мы записали до остановки (если ничего не было записано, то считайте это число за ноль). Дайте ваш ответ округленным до 8 знака после десятичной точки.

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net