solution

$\operatorname{ans} = \min_{x + y \le n} (n - x - y + |x - y|)$であるが、$x,y$の片方を決めればもう片方の見るべき値は定まるので、片側だけ全探索。 $O(N)$。

implementation

#!/usr/bin/env python3
n = int(input())
ans = float('inf')
for y in range(1,n+1):
    x = n // y
    ans = min(ans, n - x * y + abs(x - y))
print(ans)