Squares and Segments
Contest: Codeforces Round 530 (Div. 2)
Difficulty rating: 1100
Tags: binary search, constructive algorithms, math

Little Sofia is in fourth grade. Today in the geometry lesson she learned about segments and squares. On the way home, she decided to draw $$$n$$$ squares in the snow with a side length of $$$1$$$. For simplicity, we assume that Sofia lives on a plane and can draw only segments of length $$$1$$$, parallel to the coordinate axes, with vertices at integer points.

In order to draw a segment, Sofia proceeds as follows. If she wants to draw a vertical segment with the coordinates of the ends $$$(x, y)$$$ and $$$(x, y+1)$$$. Then Sofia looks if there is already a drawn segment with the coordinates of the ends $$$(x', y)$$$ and $$$(x', y+1)$$$ for some $$$x'$$$. If such a segment exists, then Sofia quickly draws a new segment, using the old one as a guideline. If there is no such segment, then Sofia has to take a ruler and measure a new segment for a long time. Same thing happens when Sofia wants to draw a horizontal segment, but only now she checks for the existence of a segment with the same coordinates $$$x$$$, $$$x+1$$$ and the differing coordinate $$$y$$$.

For example, if Sofia needs to draw one square, she will have to draw two segments using a ruler:

After that, she can draw the remaining two segments, using the first two as a guide:

If Sofia needs to draw two squares, she will have to draw three segments using a ruler:

After that, she can draw the remaining four segments, using the first three as a guide:

Sofia is in a hurry, so she wants to minimize the number of segments that she will have to draw with a ruler without a guide. Help her find this minimum number.

Input format:
The only line of input contains a single integer $$$n$$$ ($$$1 \le n \le 10^{9}$$$), the number of squares that Sofia wants to draw.

Output format:
Print single integer, the minimum number of segments that Sofia will have to draw with a ruler without a guide in order to draw $$$n$$$ squares in the manner described above.

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

Example input:
1

Example output:
2

Example input:
2

Example output:
3

Editorial:
Consider any resulting configuration of the squares. We can safely assume that a set of non-empty rows and non-empty columns are connected (otherwise just move the disconnected part a bit closer to any other). Clearly, in every column and every row we can «for free» extend it to have all the squares in the bounding box — minimum rectangle containing the resulting figure. From this we can conclude that we can search for the optimal answer among the rectangles.
The answer for a rectangle $$$a \times b$$$ equals $$$a+b$$$ (just draw the first row and the first column), so we need to find two values $$$a$$$ and $$$b$$$ such that $$$a \times b \ge n$$$ and $$$a + b$$$ is minimum possible. It's easy to see that the answer is not optimal if $$$|a-b| \ge 2$$$: by moving the numbers towards each other we get the same sum, but greater product. This observation leads to the following solution: if $$$s=[\sqrt n]$$$, then the answer is either a rectangle $$$s \times s$$$, or a rectangle $$$s \times (s+1)$$$, or a rectangle $$$(s+1) \times (s+1)$$$ (because of the rounding). We just need to check which one is better.