407666: GYM102868 D Light-Green

Light-Green was priming the shields when she realized that the current hexagonal shields are not optimal to protect the ship. She decides to arrange the shields into an $$$n \times n$$$ square grid arrangement with a shield in each of the cells of the grid. Additionally, each of the shields can be installed in one of two ways, either facing left or facing right.

Now, say that we have an $$$n \times n$$$ matrix $$$S$$$ where $$$S_{i,j}$$$ (for $$$1 \leq i, j \leq n$$$) equals 'L' if the shield at that position in the matrix is facing left or 'R' if it is facing right. Now, Light-Green has derived that the optimal shield arrangement must have the following properties:

• For every $$$S_{i,j}$$$ that equals 'R', none of the squares $$$S_{i + 1,j}$$$, $$$S_{i - 1,j}$$$, $$$S_{i,j - 1}$$$, and $$$S_{i,j + 1}$$$ can equal 'R'.
• $$$S$$$ must be both horizontally and vertically symmetrical or more formally, it must be true that $$$S_{i,j} = S_{n - i + 1, j}$$$ and $$$S_{i,j} = S_{i, n - j + 1}$$$ for every possible pair $$$i,j$$$ (where $$$1 \leq i,j \leq n$$$).
• There are exactly $$$k$$$ squares in the matrix which are equal to 'R'.

Now, priming the shields takes time so Light-Green wants to prime as few shields as possible. Given an integer $$$k$$$, figure out the smallest positive integer $$$n$$$ such that there exists an $$$n \times n$$$ matrix satisfying the optimal properties that were listed above.

The single line of input will contain a single integer $$$k$$$ ($$$1 \leq k \leq 10^{12}$$$), representing the number of entries in the matrix which are equal to 'R'.

Output a single integer, representing the smallest positive integer $$$n$$$ such that there exists an $$$n \times n$$$ matrix satisfying the optimal properties.

4

3

12

5

In the first example, you can construct a $$$3 \times 3$$$ matrix with $$$\{1,0,1\}$$$ in the first row, $$$\{0, 0, 0\}$$$ in the second row, and $$$\{1, 0, 1\}$$$ in the third row and this satisfies all the conditions (and there is no $$$1 \times 1$$$ or $$$2 \times 2$$$ matrix which can fit the conditions) so $$$3$$$ is our answer.