Условие

У Ани есть 20 пронумерованных кубиков разных номиналов (от d4 до d20). Грани кубиков имеют неравномерную вероятность выпадения очков. Аня начинает с кубика 1, бросает его, записывает выпавшее число очков, а затем берёт кубик с номером, соответствующим выпавшему числу, и бросает его, прибавляет очки к ранее записанным, затем берёт следующий кубик… Пока сумма очков не станет равной или превысит 128. Какова вероятность, что Аня таким образом сможет набрать ровно 128 очков?

Какова вероятность, что Аня таким образом сможет набрать ровно 128 очков?

Формат входных данных

20 строк, в каждой – произвольное количество вещественных чисел через пробел – распределение вероятностей выпадения для граней соответствующего кубика. Гарантируется, что сумма вероятностей для каждого кубика равна 1 с точностью до машинного нуля.

Формат выходных данных

Единственное вещественное число.

Для решения этой задачи у вашей команды есть 20 попыток.

Видео-разбор

 

Разбор

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

Правильным подходом будет аналитический подсчет вероятностей, с движением от конца к началу. Если мы уже набрали 128, то мы выйграли, вероятность успеха - единица. Если больше 128, то ноль. Для всех остальных сумм считаем вероятность успеха при данной конфигурации очков и кубика. Смотрим на все грани и взвешиваем вероятности исходов. Заполняя таблицу от больших сумм к меньшим идем рассчитываем вероятности вплоть до нулевой суммы

В таком подходе важно учитывать, что вероятности при вычислениях становятся крайне маленькими, и для избежания погрешности лучше использовать числа с произвольной точностью.

Последнее изменение: среда, 13 мая 2026, 09:52