Задача №114284. Максимизируй!
Дано множество S из натуральных чисел, изначально пустое. С ним производятся операции двух типов:
- Добавить в S натуральное число, не меньшее всех уже лежащих в множестве элементов.
-
Найти непустое подмножество
s
множества
S
такое, что значение
максимально. Здесь
max
(
s
)
обозначает максимум среди всех элементов
s
,
— среднее арифметическое всех элементов
s
. Вывести величину
.
В первой строке задано единственное натуральное число Q ( 1 ≤ Q ≤ 5·10 5 ) — количество операций. В каждой из следующих Q строк следует описание очередной операции. Для операций типа 1 в строке будут записаны два числа вида 1 и x , где x ( 1 ≤ x ≤ 10 9 ) — число, которое нужно добавить в S . Гарантируется, что x будет не меньше любого элемента S на данный момент. Для операции типа 2 в соответствующей строке будет записано ровно одно число 2 .
Гарантируется, что первая операция будет иметь тип 1 , то есть множество S не будет пустым при поступлении операций типа 2 .
Выведите ответ на каждую операцию второго типа в том порядке, в котором эти операции шли во входных данных. Каждое число должно располагаться на отдельной строке и содержать минимум шесть верных значащих цифр.
Решения, правильно работающие для Q ≤ 1400 , будут набирать не менее 30 баллов.
Решения, правильно работающие для Q ≤ 20000 , будут набирать не менее 44 баллов.
6 1 3 2 1 4 2 1 8 2
0.0000000000 0.5000000000 3.0000000000
4 1 1 1 4 1 5 2
2.0000000000