Educational Codeforces Round 24 |
---|
Закончено |
Иван разрабатывает свою собственную компьютерную игру. Сейчас Иван хочет создать все уровни игры. Но перед этим он хочет нарисовать каждый уровень на бумаге в виде графа.
Иван решил, что в графе i-го уровня должно быть ровно ni вершин, а сам граф должен быть неориентированный. Главная, по мнению Ивана, характеристика графа — количество специальных рёбер, называемых мостами. Ребро, соединяющее вершины u и v, называется мостом, если оно лежит на каждом пути из u в v (и эти вершины окажутся в разных компонентах связности, если ребро стереть). Иван хочет, чтобы в построенном для каждого уровня графе как минимум 50% всех рёбер были бы мостами. Также Иван хочет максимизировать количество рёбер в каждом графе.
Итак, задание, которое вам дал Иван, состоит в следующем: по заданным q числам n1, n2, ..., nq для каждого i определить максимальное количество рёбер в графе из ni вершин, если хотя бы 50% рёбер должны быть мостами. Обратите внимание, в графах не может быть петель или кратных рёбер.
В первой строке записано число q (1 ≤ q ≤ 100 000) — число графов, которые нужно построить Ивану.
Затем следуют q строк, в i-й из них записано число ni (1 ≤ ni ≤ 2·109) — количество вершин в i-м графе.
Обратите внимание, что во взломах вы можете использовать только q = 1.
Выведите q чисел, i-е из которых равно максимальному количеству рёбер в i-м графе.
3
3
4
6
2
3
6
В примере из условия можно построить следующие графы:
Название |
---|