Codeforces Beta Round 62 |
---|
Закончено |
В последнее время Петя очень увлекся физикой. Анна Викторовна, его учительница, заметив Петину тягу к знаниям дала ему увлекательную физическую головоломку — дерево полураспада.
Дерево полураспада представляет собой полное двоичное дерево высоты h. Высота двоичного дерева — максимум среди расстояний (в ребрах) от корня дерева до его листьев. В процессе изучения, Петя добавляет в его вершины электроны, а также вызывает случайный распад дерева с помощью синхрофазотрона. Случайным распадом называется процесс при котором вдоль пути от корня к случайному листку удаляются все ребра. Вероятности выбора листьев равны между собой. Естественно, так как казенное имущество портить ученикам воспрещается, после каждого такого распада Петя возвращает все удаленные ребра на место.
Распавшись, дерево разлагается на компоненты связности. Зарядом такой компоненты называется суммарное количество электронов в вершинах, что принадлежат ей. Потенциалом разрушенного дерева называется максимальный заряд среди его компонент связности. Каждый раз вызывая случайный распад дерева, Петя предварительно хочет знать каково математическое ожидание потенциала дерева после его разрушения.
Первая строка будет содержать два целых числа h и q (1 ≤ h ≤ 30, 1 ≤ q ≤ 105). Далее идут q строк в каждой из которых будет запрос одного из двух типов:
В вершину с номером v Петя добавляет e электронов (1 ≤ v ≤ 2h + 1 - 1, 0 ≤ e ≤ 104). v и e — целые числа.
Вершины в дереве нумеруются следующим образом: корень имеет номер 1, потомки вершины x имеют номера 2x и 2x + 1.
Петя провоцирует распад дерева.
Для каждого запроса decay следует вывести математическое ожидание потенциала дерева после его разрушения. Абсолютная или относительная погрешность ответа не должна превышать 10 - 4.
1 4
add 1 3
add 2 10
add 3 11
decay
13.50000000
Название |
---|