← 返回题目列表

Codeforces · 1099/B

B. 正方形和线段

中文机器翻译题面 查看原题

小索菲亚正在上四年级。今天在几何课上她学习了线段和正方形。在回家的路上,她决定在雪地里画$$$n$$$边长为$$$1$$$的正方形。为简单起见,我们假设索菲亚生活在一个平面上,并且只能绘制长度为 $$$1$$$ 的线段,平行于坐标轴,顶点位于整数点。

为了绘制线段,Sofia 进行如下操作。如果她想绘制一条垂直线段,其两端坐标为$$$(x, y)$$$ 和$$$(x, y+1)$$$。然后 Sofia 查看是否已经存在一个绘制的线段,其末端坐标为 $$$(x', y)$$$ 和 $$$(x', y+1)$$$ 对于某些 $$$x'$$$。如果存在这样的线段,那么索菲亚会使用旧线段作为指导快速绘制一条新线段。如果没有这样的线段,那么索菲亚就得拿一把尺子,长时间地测量新的线段。当 Sofia 想要绘制水平线段时,也会发生同样的情况,但直到现在她才检查是否存在具有相同坐标 $$$x$$$、$$$x+1$$$ 和不同坐标 $$$y$$$ 的线段。

例如,如果索菲亚需要绘制一个正方形,她将必须使用尺子绘制两个线段:

之后,她可以使用前两个部分作为指导来绘制剩余的两个部分:

如果索菲亚需要绘制两个正方形,她将必须使用尺子绘制三个线段:

之后,她可以使用前三个部分作为指导来绘制剩余的四个部分:

索菲亚很着急,所以她想尽量减少需要在没有引导的情况下用尺子绘制的线段数量。帮助她找到这个最小数字。

输入

输入的唯一一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^{9}$$$),即 Sofia 想要绘制的正方形数量。

输出

打印单个整数,即 Sofia 必须在没有引导的情况下用尺子绘制的最小线段数,以便以上述方式绘制 $$$n$$$ 正方形。

示例

输入 #1

1

输出 #1

2

输入 #2

2

输出 #2

3

输入 #3

4

输出 #3

4