Problem:


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.



Sample input:
10


Sample output:
5

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
import math

def solve(N: int):
    INF = 10000000000000
    result = INF
    for a in range(1, int( math.sqrt(N) )):
        if N % a:
            continue
        result = min(result, a + int( N / a ) - 2)
    print(result)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors
s=int(input())
x=make_divisors(s)
m=[]
for a in x:
    for b in x:
        if a*b==s and a<b:
            k=a+b
            m.append(k)
print(min(m)-2)

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
def main():
    N = int(input())
    ans = N-1
    max_sq = int(math.sqrt(N)+1)
    for i in range(1, max_sq):
        if N % i != 0:
            continue
        j = N / i
        ans = min(ans, i+j-2)
    print(ans)
main()

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
def main():
    N = int(input())
    ans = N-1
    max_sq = int(N**0.5)
    for i in range(1, max_sq):
        if N % i == 0:
            j = N // i
            ans = min(ans, i+j-2)
    print(ans)
main()

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
def main():
    N = int(input())
    ans = N-1
    max_sq = int(N**0.5)
    for i in range(1, max_sq):
        if N % i == 0:
            j = N / i
            ans = min(ans, i+j-2)
    print(ans)
main()

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def main():
    N = I()
    ans = N
    max_sq = int(round(math.sqrt(N))) + 1
    for i in range(1, max_sq):
        if N % i == 0:
            j = N / i
            ans = min(ans, i+j-2)
    print(ans)
main()

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

def main():
    N = I()
    ans = inf
    max_sq = int(round(math.sqrt(N))) + 1
    for i in range(1, max_sq):
        if N % i != 0:
            continue
        j = N / i
        ans = min(ans, i+j-2)
    print(ans)
main()

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def main():
    N = I()
    ans = inf
    max_sq = int(round(math.sqrt(N))) + 1
    for i in range(1, max_sq):
        if N % i != 0:
            continue
        j = N / i
        ans = min(ans, i+j-2)
    print(ans)
main()

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def main():
    N = I()
    ans = inf
    max_sq = int(round(math.sqrt(N))) + 1
    for i in range(1, max_sq):
        if N % i != 0:
            continue
        j = N / i
        ans = min(ans, i+j-2)
    print(ans)

main()

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def main():
    N = I()
    ans = N - 1
    max_sq = int(math.sqrt(N)) + 1
    for i in range(1, max_sq):
        if N % i != 0:
            continue
        j = N / i
        ans = min(ans, i+j-2)
    print(ans)

main()

Submission status: Wrong Answer

Solution code:
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

x = int(input())
u = prime_factorize(x)
u.sort()
a = 1
b = 1
for i in u[0::2]:
    a = a * i
for i in u[1::2]:
    b = b * i
print(a + b - 2)

Submission status: Wrong Answer

Solution code:
from math import sqrt


N = int(input())
res = N
for x in range(1, int(sqrt(N))):
    if N % x == 0:
        y = N // x
        res = min(res, x + y - 2)

print(res)

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter

sys.setrecursionlimit = 10 ** 6
N = int(input())


def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


def dfs(i, x):
    global N
    global res
    if i != len(prime_keys):
        p = prime_keys[i]
        for num in range(prime[p] + 1):
            x *= (p ** num)
            y = N // x
            res = min(res, x + y - 2)
            dfs(i + 1, x)


prime = Counter(prime_factorize(N))
prime_keys = list(prime.keys())
res = N * 2
dfs(0, 1)
print(res)

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter

sys.setrecursionlimit = 10 ** 6
N = int(input())


def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


def dfs(i, x):
    global N
    global res
    if i == len(prime_keys):
        return N
    else:
        p = prime_keys[i]
        for num in range(prime[p] + 1):
            x *= (p ** num)
            y = N // x
            res = min(res, x + y - 2)
            dfs(i + 1, x)


prime = Counter(prime_factorize(N))
prime_keys = list(prime.keys())
res = N
dfs(0, 1)
print(res)

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter

sys.setrecursionlimit = 10 ** 6
N = int(input())


def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


def dfs(i, x):
    global N
    global res
    if i == len(prime_keys):
        return
    else:
        p = prime_keys[i]
        for num in range(prime[p] + 1):
            x *= (p ** num)
            y = N // x
            res = min(res, x + y - 2)
            dfs(i + 1, x)


prime = Counter(prime_factorize(N))
prime_keys = list(prime.keys())
res = N
dfs(0, 1)
print(res)

Submission status: Wrong Answer

Solution code:
N = int(input())


def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


prime = prime_factorize(N)
res = N
x = 1
for p in prime:
    x *= p
    y = N // x
    d = (x - 1) + (y - 1)
    res = min(d, res)
print(res)

Submission status: Wrong Answer

Solution code:
import math
n = int(input())

factor = []
tmp = int(math.sqrt(n))+1
for num in range(2,tmp):
    while n%num == 0:
        n //= num
        factor.append(num)

if not factor:
    print(n-1)
else:
    factor.append(n)
    factor.sort()
    k1 = 1
    k2 = 1
    for i in factor[0::2]:
        k1 *= i
    for i in factor[1::2]:
        k2 *= i
    print(k1+k2-2)

Submission status: Wrong Answer

Solution code:
n = int(input())
x = 1
res = n
while x * x <= n:
  if n % x == 0:
    res = min(res, x + n // x)
    x += 1
print(res)

Submission status: Wrong Answer

Solution code:
import math
A = int(input())
B = int(math.sqrt(A))
count = 0
for i in reversed(range(1,B)):
	if count == 0:
		if A % i == 0:
			print(int(i+A/i-2))
			count += 1

Submission status: Wrong Answer

Solution code:
n = int(input())
for i in range(-int(-n**0.5//1),0,-1):
  if n%i==0:
    a=i
    b=n//i
print(a+b-2)

Submission status: Wrong Answer

Solution code:
#ABC-144-C
N = int(input())
root_N = N ** 0.5
ans = 10 ** 9

for i in range(1, int(root_N)+1):
    if N % i == 0:
        j = N / i
        ans = min(ans, i+j-2)

print(int(ans))

Submission status: Wrong Answer

Solution code:
import math

N = int(input())

res = 10 ** 11
for i in range(1, int(math.sqrt(N))):
    if N%i == 0:
        res = min(res, N // i + i)

print(res-2)

Submission status: Wrong Answer

Solution code:
def prime_factor(n):
    i = 2
    table = []
    while i * i <= n:
        while n % i == 0:
            n //= i
            table.append(i)
        i += 1
    if n > 1:
        table.append(n)
    return table

N = int(input())

table = prime_factor(N)
table.sort()

tmp1 = 1
tmp2 = N  

for i in range(len(table)):
    tmp1 *= table[i]
    tmp2 /= table[i]

    if tmp1 == tmp2:
        break
    elif tmp1 > tmp2:
        tmp1 /= table[i]
        tmp2 *= table[i]
print(int(tmp1) + int(tmp2) - 2)

Submission status: Wrong Answer

Solution code:
def prime_factor(n):
    i = 2
    table = []
    while i * i <= n:
        while n % i == 0:
            n //= i
            table.append(i)
        i += 1
    if n > 1:
        table.append(n)
    return table

N = int(input())

table = prime_factor(N)
table.sort()

tmp1 = 1
tmp2 = N  

for i in range(len(table)):
    tmp1 *= table[i]
    tmp2 /= table[i]

    if tmp1 >= tmp2:
        break
    
print(tmp1 + int(tmp2) - 2)

Submission status: Wrong Answer

Solution code:
def prime_factor(n):
    i = 2
    table = []
    while i * i <= n:
        while n % i == 0:
            n //= i
            table.append(i)
        i += 1
    if n > 1:
        table.append(n)
    return table

N = int(input())

table = prime_factor(N)

if len(table)%2 == 0:
    tmp1 = 1
    tmp2 = 1
    for i in range(len(table)//2):
        tmp1 *= table[i]
        tmp2 *= table[i+len(table)//2]

    print(tmp1 + tmp2 - 2)

else:
    tmp1 = 1
    tmp2 = 1
    for i in range(len(table)//2):
        tmp1 *= table[i]
        tmp2 *= table[i+len(table)//2+1]

    tmp1 *= table[len(table)//2]
    print(tmp1 + tmp2 - 2)

Submission status: Wrong Answer

Solution code:
from math import sqrt
n=int(input())

ans=0
for i in range(1,int(sqrt(n))):
  if n%i==0: ans = min(ans,i+n//i-2)

print(ans)

Submission status: Wrong Answer

Solution code:
from math import sqrt
n=int(input())

ans=0
for i in range(1,int(sqrt(n))):
  if n%i==0: ans = i+n//i-2

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())

res = float('inf')
for x in range(1, int(n**0.5) + 1):
    if n % x == 0:
        res = min(res, x-1 + n/x -1)
print(res)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
s = 0
N = int(input())
for i in range(1, 10**6):
    if N%i == 0 and i > s and i != N:
        s = i
print(s+(N//s)-2)

Submission status: Wrong Answer

Solution code:
N = int(input())

# factoring
# lv = []
cost = float("INF")
for v in range(1, N):
    if v * v >= N:
        break
    if int(N / v) == N / v:
        ctmp = v - 1 + (N // v) - 1
        cost = min(cost, ctmp)
        # lv.append((v, N // v))

print(cost)

Submission status: Wrong Answer

Solution code:
from math import sqrt

n = int(input())

ans = float('inf')
for i in range(1, int(sqrt(n))):
    if n % i == 0:
        ans = min(ans, i + n//i - 2)
print(ans)

Submission status: Wrong Answer

Solution code:
# imports
import math

def main():
    N = int(input())
    rt_N = math.ceil(math.sqrt(N))
    
    mn_ij = 10**12
    for i in range(1, rt_N):
        if N % i == 0:
            j = N // i

            mn_ij = min(mn_ij, i+j)
        
        mn_ij = min(mn_ij, i+j)

    # print(list(map(len,[ st, facs]) ))
    print(int(mn_ij-2))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
################################################
# Start Below

# imports
    
def factors(n):
    gaps = [1,2,2,4,2,4,2,4,6,2,6]
    length, cycle = 11, 3
    f, fs, nxt = 2, [], 0
    while f * f <= n:
        while n % f == 0:
            fs.append(f)
            n /= f
        f += gaps[nxt]
        nxt += 1
        if nxt == length:
            nxt = cycle
    if n > 1: fs.append(n)
    return fs

import itertools
from itertools import combinations, chain
import copy 

# def powerset(L):
#   pset = set()
#   for n in range(len(L) + 1):
#     for sset in itertools.combinations(L, n):
#       pset.add(sset)
#   return pset
def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))
    
def list_diff(first, second):
        first = copy.copy(first)
        for s in second:
            first.remove(s)
        return first

def prod(lst):
    ret = 1
    for a in lst:
        ret *= a
    return ret

def sup(x):
    return [sorted(x[:i]+x[i+s:]) for i in range(len(x)) for s in range(len(x))]

def main():
    N = int(input())
    facs = factors(N) 
    # st = powerset(facs)
    st=sup(facs)
    # print(facs, st)

    mn_ij = 10**12
    for i in st:
        i = prod(i)
        # j = list_diff(facs, i)
        # i, j = prod(i), prod(j)
        j = N / i
        assert i*j==N
        
        mn_ij = min(mn_ij, i+j)

    # print(list(map(len,[ st, facs]) ))
    print(int(mn_ij-2))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
################################################
# Start Below

# imports
    
def factors(n):
    gaps = [1,2,2,4,2,4,2,4,6,2,6]
    length, cycle = 11, 3
    f, fs, nxt = 2, [], 0
    while f * f <= n:
        while n % f == 0:
            fs.append(f)
            n /= f
        f += gaps[nxt]
        nxt += 1
        if nxt == length:
            nxt = cycle
    if n > 1: fs.append(n)
    return fs

import itertools
from itertools import combinations, chain
import copy 

# def powerset(L):
#   pset = set()
#   for n in range(len(L) + 1):
#     for sset in itertools.combinations(L, n):
#       pset.add(sset)
#   return pset
def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))
    
def list_diff(first, second):
        first = copy.copy(first)
        for s in second:
            first.remove(s)
        return first

def prod(lst):
    ret = 1
    for a in lst:
        ret *= a
    return ret

def sup(x):
    return [sorted(x[:i]+x[i+s:]) for i in range(len(x)) for s in range(len(x))]

def main():
    N = int(input())
    facs = factors(N) 
    # st = powerset(facs)
    st=sup(facs)
    # print(facs, st)

    mn_ij = 10**32
    for i in st+[[]]:
        i = prod(i)
        # j = list_diff(facs, i)
        # i, j = prod(i), prod(j)
        j = N / i
        # print(i,j)
        mn_ij = min(mn_ij, i+j)

    # print(list(map(len,[ st, facs]) ))
    print(int(mn_ij-2))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
################################################
# Start Below

# imports
    
def factors(n):
    gaps = [1,2,2,4,2,4,2,4,6,2,6]
    length, cycle = 11, 3
    f, fs, nxt = 2, [], 0
    while f * f <= n:
        while n % f == 0:
            fs.append(f)
            n /= f
        f += gaps[nxt]
        nxt += 1
        if nxt == length:
            nxt = cycle
    if n > 1: fs.append(n)
    return fs

import itertools
from itertools import combinations, chain
import copy 

# def powerset(L):
#   pset = set()
#   for n in range(len(L) + 1):
#     for sset in itertools.combinations(L, n):
#       pset.add(sset)
#   return pset
def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))
    
def list_diff(first, second):
        first = copy.copy(first)
        for s in second:
            first.remove(s)
        return first

def prod(lst):
    ret = 1
    for a in lst:
        ret *= a
    return ret

def sup(x):
    return [sorted(x[:i]+x[i+s:]) for i in range(len(x)) for s in range(len(x))]

def main():
    N = int(input())
    facs = factors(N) 
    # st = powerset(facs)
    st=sup(facs)
    # print(facs, st)

    mn_ij = 10**12
    for i in st+[[]]:
        i = prod(i)
        # j = list_diff(facs, i)
        # i, j = prod(i), prod(j)
        j = N / i
        # print(i,j)
        mn_ij = min(mn_ij, i+j)

    # print(list(map(len,[ st, facs]) ))
    print(int(mn_ij-2))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def factors(n):
    gaps = [1,2,2,4,2,4,2,4,6,2,6]
    length, cycle = 11, 3
    f, fs, nxt = 2, [], 0
    while f * f <= n:
        while n % f == 0:
            fs.append(f)
            n /= f
        f += gaps[nxt]
        nxt += 1
        if nxt == length:
            nxt = cycle
    if n > 1: fs.append(n)
    return fs

import itertools
from itertools import combinations, chain
import copy 

# def powerset(L):
#   pset = set()
#   for n in range(len(L) + 1):
#     for sset in itertools.combinations(L, n):
#       pset.add(sset)
#   return pset
def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))
    
def list_diff(first, second):
        first = copy.copy(first)
        for s in second:
            first.remove(s)
        return first

def prod(lst):
    ret = 1
    for a in lst:
        ret *= a
    return ret

def sup(x):
    return [sorted(x[:i]+x[i+s:]) for i in range(len(x)) for s in range(len(x))]

def main():
    N = int(input())
    facs = factors(N) 
    # st = powerset(facs)
    st=sup(facs)
    print(facs, st)

    mn_ij = 10**12
    for i in st+[[]]:
        i = prod(i)
        # j = list_diff(facs, i)
        # i, j = prod(i), prod(j)
        j = N / i
        print(i,j)
        mn_ij = min(mn_ij, i+j)

    # print(list(map(len,[ st, facs]) ))
    print(int(mn_ij-2))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
    
def factors(n):
    gaps = [1,2,2,4,2,4,2,4,6,2,6]
    length, cycle = 11, 3
    f, fs, nxt = 2, [], 0
    while f * f <= n:
        while n % f == 0:
            fs.append(f)
            n /= f
        f += gaps[nxt]
        nxt += 1
        if nxt == length:
            nxt = cycle
    if n > 1: fs.append(n)
    return fs

import itertools
from itertools import combinations, chain
import copy 

# def powerset(L):
#   pset = set()
#   for n in range(len(L) + 1):
#     for sset in itertools.combinations(L, n):
#       pset.add(sset)
#   return pset
def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))
    
def list_diff(first, second):
        first = copy.copy(first)
        for s in second:
            first.remove(s)
        return first

def prod(lst):
    ret = 1
    for a in lst:
        ret *= a
    return ret

def sup(x):
    return [sorted(x[:i]+x[i+s:]) for i in range(len(x)) for s in range(len(x))]

def main():
    N = int(input())
    facs = factors(N) 
    # st = powerset(facs)
    st=sup(facs)
    # print(facs, st)

    mn_ij = 10**12
    for i in st:
        i = prod(i)
        # j = list_diff(facs, i)
        # i, j = prod(i), prod(j)
        j = N / i

        mn_ij = min(mn_ij, i+j)

    # print(list(map(len,[ st, facs]) ))
    print(int(mn_ij-2))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def factors(n):
    gaps = [1,2,2,4,2,4,2,4,6,2,6]
    length, cycle = 11, 3
    f, fs, nxt = 2, [], 0
    while f * f <= n:
        while n % f == 0:
            fs.append(f)
            n /= f
        f += gaps[nxt]
        nxt += 1
        if nxt == length:
            nxt = cycle
    if n > 1: fs.append(n)
    return fs

import itertools
from itertools import combinations, chain
import copy 

# def powerset(L):
#   pset = set()
#   for n in range(len(L) + 1):
#     for sset in itertools.combinations(L, n):
#       pset.add(sset)
#   return pset
def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))
    
def list_diff(first, second):
        first = copy.copy(first)
        for s in second:
            first.remove(s)
        return first

def prod(lst):
    ret = 1
    for a in lst:
        ret *= a
    return ret

def sup(x):
    return [sorted(x[:i]+x[i+s:]) for i in range(len(x)) for s in range(len(x))]

def main():
    N = int(input())
    facs = factors(N)
    # st = powerset(facs)
    st=sup(facs)

    mn_ij = 10**12
    for i in st:
        i = list(i)
        j = list_diff(facs, i)
        i, j = prod(i), prod(j)

        mn_ij = min(mn_ij, i+j)

    # print(list(map(len,[ st, facs]) ))
    print(int(mn_ij-2))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n= int(input())
tmp = float('inf')
for i in range(1,100001):
	if n % i == 0:
		tmp =min(tmp,i + n/i -2)

print(int(tmp))

Submission status: Wrong Answer

Solution code:
def prime_factorize(_n):
    a = []
    while _n % 2 == 0:
        a.append(2)
        _n //= 2
    f = 3
    while f * f <= _n:
        if _n % f == 0:
            a.append(f)
            _n //= f
        else:
            f += 2
    if _n != 1:
        a.append(_n)
    return a


n = int(input())

factorize = prime_factorize(n)
tmp = []

a = 1
for idx, i in enumerate(factorize):
    a *= i
    b = 1
    for j in factorize[idx + 1:]:
        b *= j
    tmp.append(a + b)
print(min(tmp) - 2)

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
N = int(input())

Abs = int(np.sqrt(N))
if Abs ** 2 == N:
    print((Abs - 1) * 2)
else:
    p = Abs
    q = Abs + 1
    while p > 0 and q < N:
        if p * q == N:
            print(p + q - 2)
            sys.exit(0)
        else:
            p -= 1
            q += 1
print(N - 1)

Submission status: Wrong Answer

Solution code:
import math
n=int(input())

to=int(math.sqrt(n))
a=n*2
for i in range(1,to+1):
    if n%i==0:
        a=min(a,n//i+i)
        print(a)
print(a-2)

Submission status: Wrong Answer

Solution code:
N = int(input())
x = N
y = N
ansx = N
ansy = N
ans = []
n = int(N**0.5)
if N**0.5 == int(N**0.5):
    print(int(N**0.5)*2-2)
else:
    for i in range(n+1):
        if N%(i+1) == 0:
            ans.append(i+1)
    ans.append(N)
    if(ans[1]==N):
        print(N-1)
    else:
        for i in range(len(ans)):
            if ansx > ans[i]:
                if ansy > N//ans[i]:
                    ansx = ans[i]
                    ansy =int(N//ans[i])
        print(ansx + ansy -2)

Submission status: Wrong Answer

Solution code:
N = int(input())
x = N
y = N
ansx = N
ansy = N
ans = []
n = int(N**0.5)
if N**0.5 == int(N**0.5):
    print(int(N**0.5))
else:
    for i in range(n+1):
        if N%(i+1) == 0:
            ans.append(i+1)
    ans.append(N)
    if(ans[1]==N):
        print(N-1)
    else:
        for i in range(len(ans)):
            if ansx > ans[i]:
                if ansy > N//ans[i]:
                    ansx = ans[i]
                    ansy =int(N//ans[i])
        print(ansx + ansy -2)

Submission status: Wrong Answer

Solution code:
N = int(input())
x = N
y = N
ansx = N
ansy = N
ans = []
n = int(N**0.5)
for i in range(n+1):
    if N%(i+1) == 0:
        ans.append(i+1)
ans.append(N)
if(ans[1]==N):
    print(N-1)
else:
    for i in range(len(ans)):
        if ansx > ans[i]:
            if ansy > N//ans[i]:
                ansx = ans[i]
                ansy =int(N//ans[i])
    print(ansx + ansy -2)

Submission status: Wrong Answer

Solution code:


def divisor(n): #nの約数を全て求める
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table

def out(N, table):
    r = 0
    for i in table:
        a = i
        b = N / i
        if r > (a-1)+(b-1) or r == 0:
            r = (a-1)+(b-1)
    return r


N = int(input())
table = divisor(N)
r = out(N, table)
print(r)

Submission status: Wrong Answer

Solution code:


def divisor(n): #nの約数を全て求める
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table

def out(N, table):
    r = 0
    for i in table:
        a = i
        b = N / i
        if r > (a+b) or r == 0:
            r = (a+b)
    return r


N = int(input())
table = divisor(N)
r = out(N, table)
print(r)

Submission status: Wrong Answer

Solution code:
n=int(input())
ans=n-1
if(n%2==0):
  ans=int(n/2)
e=int(n**(1/2))+1
for i in range(3,e,2):
  if(n%i==0):
    ans=min(ans,i+int(n/i)-2)
print(ans)

Submission status: Wrong Answer

Solution code:
import math,sys
n = int(input())
a = 1
ans = n -1
i = 2
m = int(math.sqrt(n))
while(i<m+1):
  if n%i==0:
    a*=i
    n = n//i
    m = int(math.sqrt(n))
    tmp = a + n -2
    i = 1
    if tmp < ans:
      ans = tmp
  i+=1
    
print(ans)

Submission status: Wrong Answer

Solution code:
N = float(input())
import numpy as np
d = 1
for i in range(2,int(np.floor(N**0.5))):
	if N%i==0:
		d = i
print(int(d+N/d-2))

Submission status: Wrong Answer

Solution code:
N = int(input())
a = N
for i in range(1,int(N+1/2)):
  b = N/i + i
  if N % i == 0 and b < a:
    a = b
print(int(a)-2)

Submission status: Wrong Answer

Solution code:
N = int(input())
result = int(10e13)

for i in range(1,int(pow(N,0.5))):
    if N%i!=0: continue
    else: result = min(N//i+i,result)
print(result-2)

Submission status: Wrong Answer

Solution code:
N = int(input())
result = int(10e13)

for i in range(1,int(N/2)):
    if N%i!=0: continue
    else: result = min(N//i+i,result)
print(result-2)

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
sq_n = int(math.sqrt(n))
s_lis = []
e_lis = []
for i in range(1, sq_n + 1):
    if n % i == 0:
        s_lis.append(i)
        e_lis.append(n // i)
min_len = n + 1 - 2
for s, e in zip(s_lis, e_lis):
    print(s, e)
    min_len = min(min_len, s + e - 2)
print(min_len)

Submission status: Wrong Answer

Solution code:
import math
n=int(input())
temp=n+1
for i in range(int(math.sqrt(n))+1,0,-1):
  if n%i==0:
    print(i,n//i,i+n//i-2)
    exit()

Submission status: Wrong Answer

Solution code:
import math
n=int(input())
temp=n+1
for i in range(int(math.sqrt(n)),0,-1):
  if n%i==0:
    print(i,n//i,i+n//i-2)
    exit()

Submission status: Wrong Answer

Solution code:
import math
import sys

n = int(input())

ans = sys.maxsize
for i in range(1,math.ceil(math.sqrt(n))):
  if n % i == 0:
    ans = min(ans, i + n//i -2)
  
print(ans)

Submission status: Wrong Answer

Solution code:
a=input()
a=int(a)
c=1
b=round(a**0.5)+2
for n in range(1,b):
    if a%n==0:
        c=n
d=a/c
print(d+c-2)

Submission status: Wrong Answer

Solution code:
a=input()
a=int(a)
c=1
b=round(a*0.5)+2
for n in range(1,b):
    if a%n==0:
        c=n
d=a/c
print(d+c-2)

Submission status: Wrong Answer

Solution code:
import math
def get(n):
    a=math.sqrt(n)
    #print(a,'a')
    i,j=int(a),int(a)
    if a%1==0:
        return 2*a-2
    z=True
    while i>=1 and z:
        if n%i==0:
            z=False
        else:
            i-=1
    #print(i,'i')
    z=True
    k=n//i
    return k-1+i-1
n=int(input())
print(get(n))

Submission status: Wrong Answer

Solution code:
import math

N = int(input())

n = math.floor(math.sqrt(N))
lens = [N-1]
for a in range(2, n):
  if N % a == 0:
    lens.append(a+N//a-2)

print(min(lens))