Денис отвечает за подготовку праздничного фейерверка,
посвящённого 90-летию Уральского государственного университета.
Он купил n ракет и начал думать, по какому принципу их нужно запускать.
После пары бессонных ночей Денис остановился на следующем алгоритме.
Все n ракет выстраивают на земле в одну линию. Залпы фейерверка происходят
с интервалом в десять секунд. Во время первого залпа запускаются крайняя
левая и крайняя правая ракеты. После того, как сделано уже i залпов,
выбираются все непустые отрезки между двумя соседними запущенными ракетами.
На каждом таком отрезке случайным образом равновероятно выбирается ракета. Все
выбранные ракеты запускаются во время (i + 1)-го залпа. Алгоритм
работает до тех пор, пока все ракеты не будут запущены.
Оцените, сколько в среднем секунд будет продолжаться такой фейерверк.
Исходные данные
В единственной строке записано целое число n (3 ≤ n ≤
400) — количество ракет, купленных Денисом.
Результат
Выведите математическое ожидание длительности фейерверка в секундах,
с абсолютной или относительной погрешностью не более 10−6.
Пример
исходные данные | результат |
---|
5
| 26.66666666666
|
Замечания
Сначала запустятся ракеты с номерами 1 и 5. Через 10 секунд с вероятностью
1/3 запустится ракета номер 3, в этом случае ещё через 10 секунд запустятся
ракеты 2 и 4, и салют закончится за 20 секунд. Если же во время второго залпа
запустится ракета 2 или ракета 4 (это произойдёт с вероятностью 2/3), то
салют закончится за 30 секунд.
Автор задачи: Алексей Самсонов
Источник задачи: XV Открытый командный чемпионат УрГУ по программированию