Very Suspicious
Contest: Codeforces Round 788 (Div. 2)
Difficulty rating: 1700
Tags: binary search, brute force, geometry, greedy, implementation, math

Sehr Sus is an infinite hexagonal grid as pictured below, controlled by MennaFadali, ZerooCool and Hosssam.

They love equilateral triangles and want to create $$$n$$$ equilateral triangles on the grid by adding some straight lines. The triangles must all be empty from the inside (in other words, no straight line or hexagon edge should pass through any of the triangles).

You are allowed to add straight lines parallel to the edges of the hexagons. Given $$$n$$$, what is the minimum number of lines you need to add to create at least $$$n$$$ equilateral triangles as described?

Adding two red lines results in two new yellow equilateral triangles.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases. Then $$$t$$$ test cases follow.

Each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^{9}$$$) — the required number of equilateral triangles.

Output format:
For each test case, print the minimum number of lines needed to have $$$n$$$ or more equilateral triangles.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first and second test cases only 2 lines are needed. After adding the first line, no equilateral triangles will be created no matter where it is added. But after adding the second line, two more triangles will be created at once.

In the third test case, the minimum needed is 3 lines as shown below.

Example input:
4
1
2
3
4567

Example output:
2
2
3
83

Editorial:
We can notice that there are $$$3$$$ different slopes in which we can draw a line, and we can also notice that drawing the lines exactly on the edges of the hexagons will result in the creation of $$$2$$$ equilateral triangles at each intersection of $$$2$$$ lines, so we can say that:
Number of equilateral triangles = 2 *( number of intersections at center of some hexagon).
Now we only need to find a way to draw the lines such that it maximizes the number of intersections. The best way to do that is to keep the number of lines on all $$$3$$$ slopes as close as possible (the proof will be explained at the bottom). One way to do so is to add the lines once at each slope then repeat.
Let's say that slopes are numbered $$$1$$$, $$$2$$$, and $$$3$$$, so we will add the lines as follows $$$1,2,3,1,2,3,$$$ and so on. The increase in the intersection will be the number of lines in the other two slopes added together. It will be as follows : $$$+0, +1, +2, +2, +3, +4, +4, +5, +6, +6, +7, +8, \ldots$$$
If we separate that into groups of 3 we will get $$$\{0,1,2\},\{2,3,4\},\{4,5,6\},\ldots$$$
The sum of the groups is $$$3,9,15,21,\ldots$$$
To get the sum of the first $$$X$$$ groups it will be $$$3X^2$$$. So, to get the number of intersections using $$$N$$$ lines we will first find the number of complete groups which is $$$\lfloor \frac{N}{3} \rfloor$$$ and then loop over the last group to find the total number of intersections.
Now that we have a way to find the number of equilateral triangles created by $$$N$$$ lines we can find the number of lines needed to get $$$X$$$ equilateral triangles by using binary search.
The proof that the best way to maximize the number of intersections is to keep the number of lines on all $$$3$$$ slopes as close as possible:
Imagine a case in which the difference between the lines in two slops is more than $$$2$$$ lines, now we can see that if we moved one line from the larger group to the smaller we will obtain more intersections because after moving, the intersections with the $$$3$$$-rd line will be the same and will not be affected and the intersection between the slopes will decrease by the size of the smaller group and increased by the size of the larger group minus $$$1$$$ so overall the intersections will increase by at least $$$1$$$ so that proves that we can't have any difference more than $$$1$$$ and the groups must be as close as possible.