Антон и гейзеры

Задание 1

Антон – большой любитель путешествий. Прошлым летом он добрался до долины Хёйкадалюр в Исландии. В долине находятся \$N\$ гейзеров, каждый из которых извергается ровно раз в \$x_i\$ минут, \$1 \le i \le N\$. Точный момент, когда начал извергаться конкретный гейзер, Антону неизвестен, поэтому будем считать, что время с момента появления Антона в долине до извержения \$i\$-го гейзера непрерывно равномерно распределено на отрезке \$[0; x_i]\$. Гейзеры при этом извергаются независимо друг от друга (то есть, времена первых извержений после появления Антона независимы). Антона интересует, с какой вероятностью каждый из гейзеров начнёт своё извержение первым среди остальных.

Баллы

Баллы зависят от трудоемкости по \$N\$.

Любая трудоемкость: 2 курс - 15 баллов, 1 курс – 30 баллов.
Трудоемкость (по порядку) не больше \$O(N^3)\$: 2 курс – 20 баллов, 1 курс – 40 баллов.
Трудоемкость (по порядку) не больше \$O(N^2)\$: 2 курс – 30 баллов, 1 курс – 60 баллов.

• – здесь сделано чрезмерно оптимистичное предположение о том, что арифметические операции над рациональными числами выполняются за \$O(1)\$.

Подготовка

Нужно написать программу, где на вход поступает \$N\$, затем \$N\$ периодов извержения гейзеров \$x_i\$, где \$x_i\$ — рациональные (для начала можно написать реализацию с \$x_i\$ типа double). Результатом программы являются \$N\$ рациональных вероятностей. Требуется также объяснить полученное решение.

Задача предполагает ознакомление с элементарной теорией вероятностей (например, Ширяев А.Н., Вероятность-1, третье издание, Москва, МЦНМО, 2004, гл. 1 пар. 1-4, гл. 2 пар 1-4).

Руководитель

Никита Звонарев