Содержание
Антон и гейзеры
Задание 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).
Руководитель
Никита Звонарев