Editorial

In this problem, you have to slice a cake into n pieces using horizontal or vertical cuts.

Horizontal cuts produce different layers to the cake. If we want H layers to the cake, then we would need H-1 cuts. E.g 1 layer requires 0 cuts, 2 requires 1, 4 requires 3, etc.

Vertical cuts produce different slices to the cake. If we want C slices to the cake, then the number of cuts can be found using a conditional. If C is 1, then no cuts are required. If C slices are required, then the symmetry of the slices allows the number of cuts to be halved (c/2). Otherwise, it is c.

If you have some number of layers and slices, then the total number of pieces is HC. Since we want HC = N. We need to find factor pairs of N. This can be done by iterating i from 1 to sqrt(n).* if i is a factor of n, then (i,n/i) is a factor pair. Once we find the factor pair, we can calculate the number of cuts required if this was set as the target number of layers and slices, allowing us to calculate the number of cuts for every valid combination of layers and slices.

* sqrt(n) is allowed as at least one factor in a factor pari is less than or equal to sqrt(n)

#this function calculates the number of cuts to produce c slices.
def rotCuts(c):
    if(c%2==0):
        return c//2
    elif(c==1):
        return 0
    return c


n = int(input())

ans = n-1 #answer set as upper bound

i = 1
while (i<=n and i<= int(n**0.5)): #i<=n exit condition set to avoid weirdness with low values of n.
    if(n%i==0): # if i is a factor of n
        a = i
        b = n//i

        ans = min(ans, rotCuts(a)+b-1,a+rotCuts(b)-1) #calculate number of cuts with A slices and B layers, or A layers and B slices

    i+=1

print(ans)