| Codeforces Round 788 (Div. 2) |
|---|
| Закончено |
Хоссам и его друзья владеют плоскостью, разбитой бесконечной сеткой на правильные шестиугольники, как показано на рисунке ниже. Им нравятся равносторонние треугольники, поэтому они хотят создать на плоскости $$$n$$$ равносторонних треугольников, добавив несколько прямых. Считаться будут только треугольники, внутри которых ничего нет (то есть внутри которых не проходит ни одна прямая и ни одна сторона шестиугольника).
Вы можете добавлять прямые, параллельные сторонам шестиугольников. Вам дано число $$$n$$$, какое минимальное число прямых нужно добавить, чтобы создать хотя бы $$$n$$$ равносторонних треугольников?
Добавление двух красных прямых создает два желтых треугольника. Первая строка содержит одно цело число $$$t$$$ ($$$1 \le t \le 10^5$$$) — количество наборов входных данных. Далее следуют $$$t$$$ наборов входных данных.
Каждый набор входных данных состоит из одного целого числа $$$n$$$ ($$$1 \le n \le 10^{9}$$$) — требуемого количества треугольников.
Для каждого набора выведите минимальное количество прямых, необходимое для создания $$$n$$$ или больше равносторонних треугольников.
41234567
2 2 3 83
В первом и втором примере нужны две прямые. После добавления первой не будет ни одного трекгольника независимо от места создания. После добавления второй можно одновременно создать два треугольника.
В третьем наборе входных данных нужно минимум три прямых, как показано ниже.
