

Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
高橋君は無限に広い掛け算表の上にいます。
掛け算表のマス (i,j) には整数 i \times j が書かれており、高橋君は最初 (1,1) にいます。
高橋君は 1 回の移動で (i,j) から (i+1,j) か (i,j+1) のどちらかにのみ移ることができます。
整数 N が与えられるので、N が書かれているマスに到達するまでに必要な移動回数の最小値を求めてください。
制約
- 2 \leq N \leq 10^{12}
- N は整数である。
入力
入力は以下の形式で標準入力から与えられる。
N
出力
整数 N が書かれているマスに到達するまでに必要な移動回数の最小値を出力せよ。
入力例 1
10
出力例 1
5
5 回の移動で (2,5) に到達することができます。5 回未満の移動では 10 が書かれたマスに到達することは出来ません。
入力例 2
50
出力例 2
13
13 回の移動で (5,10) に到達できます。
入力例 3
10000000019
出力例 3
10000000018
入出力とも非常に大きな値になる可能性があります。
Score : 300 points
Problem Statement
Takahashi is standing on a multiplication table with infinitely many rows and columns.
The square (i,j) contains the integer i \times j. Initially, Takahashi is standing at (1,1).
In one move, he can move from (i,j) to either (i+1,j) or (i,j+1).
Given an integer N, find the minimum number of moves needed to reach a square that contains N.
Constraints
- 2 \leq N \leq 10^{12}
- N is an integer.
Input
Input is given from Standard Input in the following format:
N
Output
Print the minimum number of moves needed to reach a square that contains the integer N.
Sample Input 1
10
Sample Output 1
5
(2,5) can be reached in five moves. We cannot reach a square that contains 10 in less than five moves.
Sample Input 2
50
Sample Output 2
13
(5, 10) can be reached in 13 moves.
Sample Input 3
10000000019
Sample Output 3
10000000018
Both input and output may be enormous.