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:
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr

N = int(input())

prime_N = factorization(N)
prime_N = sorted(prime_N, reverse=True, key=lambda x: x[0])
A = 1
B = 1
for i in range(len(prime_N)):
    for j in range(prime_N[i][1]):
        if A*prime_N[i][0] <= B*prime_N[i][0]:
            A *= prime_N[i][0]
        else:
            B *= prime_N[i][0]

print(A + B - 2)

Submission status: Wrong Answer

Solution code:
n = int(input())

lcd = []

while n % 2 == 0:
    lcd.append(2)
    n //= 2

f = 3
while f * f <= n:
    if n % f == 0:
        lcd.append(f)
        n //= f
    else:
        f += 2
if n != 1:
    lcd.append(n)

lcd.sort()

# print(lcd)

k = 1
j = 1

if len(lcd) % 2 == 1:
    lcd.append(1)

for i in range(0, len(lcd), 2):
    k *= lcd[i]
    j *= lcd[i+1]

print(max(k - 1, 0)+max(j-1, 0))

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())
temp = 1

n = prime_factorize(n)

n.sort()
last = n.pop(-1)
for i in n:
    temp = temp * i
print((last-1)+ (temp-1))

Submission status: Wrong Answer

Solution code:
N = int(input())
yaku = 1

import math

    



if N % 2 == 0:
	yaku = 2
	
for i in range(3,int(math.sqrt(N))+1 ,2):
	if N % i == 0:
		yaku = i
		

yaku2 = int(N/yaku)

print(int(yaku2+yaku - 2))

Submission status: Wrong Answer

Solution code:
import math

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)

    # divisors.sort()
    return divisors

n = int(input())
l = make_divisors(n)
ans = 999999999999999999
for i in range(0,len(l)-1, 2):
  a = l[i]
  b = l[i+1]
  ans = min(ans,(a+b-2))
  
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
x = [1,2,3,4,5,6,7,8,9]
b = []
for a in x:
    if n%a == 0:
        y = n // a
        b.append(y)
b_min = min(b)
a = n // b_min
sum = a+b_min-2
print(sum)

Submission status: Wrong Answer

Solution code:
import sys
import os
import math
import itertools

def factorize(n):
    b = 2
    fct = []
    fct.append(1)
    while b * b <= n:
        while n % b == 0:
            n //= b
            fct.append(b)
        b = b + 1
    if n > 1:
        fct.append(n)
    return fct

N = int(input())
listN = factorize(N)
x = 0
y = 0

mini = 10**12
if len(listN) == 1:
    x = N
    y = 1
else:
    for i in range(1,len(listN)):
        tmp = list(itertools.combinations(listN,i))
        for j in range(len(tmp)):
            x0,y0 = 1,1
            for k in range(len(tmp[j])):
                x0 *= tmp[j][k]
                y0 = N//x0
                print(x0,y0)
                if mini > abs(x0-y0):
                    mini = abs(x0-y0)
                    x = x0
                    y = y0

print(x-1+y-1)

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

L = sorted(prime_factorize(N))
#print(L)
#print(len(L))
while len(L) > 2:
    #print(L)
    min1 = L.pop(0)
    min2 = L.pop(0)
    L.append(min1*min2)
    L=sorted(L)
if len(L)==1:
    print(sum(L)-1)
else:
    print(sum(L)-2)

Submission status: Wrong Answer

Solution code:
import math

n = int(input())
r = int(math.sqrt(n))

if n == 2:
    print(0)
    exit()
if n == 3:
    print(1)
    exit()
for i in range(1, r+1)[::-1]:
    if n % i == 0:
        print(i + int(n/i) - 2)
        exit()

Submission status: Wrong Answer

Solution code:
import sys
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

elms = prime_factorize(n)
if len(elms) == 1:
  print(elms[0]-1)
  sys.exit()
else:
  a = elms.pop(0)
  b = elms.pop(0)
  while len(elms)>0:
    if a>b:
      b *= elms.pop(0)
    else:
      a *= elms.pop(0)

print(a+b-2)

Submission status: Wrong Answer

Solution code:
n = int(input())
count = True
tmp = 1
output = n - 1

while count:
    for i in range(2, n):
        if n % i == 0:
            tmp *= i
            n //= i
            output = (n - 1) + (tmp - 1)
            if (n - 1) + (tmp - 1) > output:
                count = False
            break

        count = False

print(output)

Submission status: Wrong Answer

Solution code:
N = int(input())

def prime_factorization(n):
    factor = []
    f = 2
    while f ** 2 <= n:
        if n % f == 0:
            factor.append(f)
            n //= f
        else:
            f += 1
    if n > 1:
        factor.append(n)
    return factor

p = prime_factorization(N)
from itertools import combinations as cb
from functools import reduce
from operator import mul

s = N+1
for i in range(max(1,len(p)//2-2), len(p)//2+1):
    for j in cb(p, i):
        A = reduce(mul, j)
        B = N//A
        s = min(s, A+B)

print(s-2)

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)

    # divisors.sort()
    return divisors
  
n = int(input())
d = make_divisors(n)
a = []
for i in range(len(d)-1):
  for j in range(i+1, len(d)):
    if d[i] * d[j] == n:
      a.append([d[i], d[j]])
m = n
ind = 0
for i in a:
  if abs(i[0]-i[1]) < m:
    m = abs(i[0]-i[1])
    ind = a.index(i)
if min(a[ind]) == 1 and max(a[ind]) == 1:
  print(a[ind][0]+a[ind][1])
elif min(a[ind]) == 1:
  print(a[ind][0]+a[ind][1]-1)
else:
  print(a[ind][0]+a[ind][1]-2)

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)

    # divisors.sort()
    return divisors

N = int(input())

n = make_divisors(N)
n.sort()
mannaka_ = int(len(n)/2)
mannaka = mannaka_ - 1
#print(n)
if len(n)%2 == 0:
    print((n[mannaka_]-1)+ (n[mannaka]-1))
else:
    print((n[mannaka_+1]-1)+ (n[mannaka]-1))

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
import itertools

def prime_factor(n):
    ass = np.array([1], dtype="int64")
    for i in range(2,int(n**0.5)+1):
        while n % i==0:
            ass = np.append(ass, i)
            n = n//i
    if n != 1:
        ass = np.append(ass, n)
    return ass

def main():
    input = sys.stdin.readline
    N = np.int64(input())
    ass = prime_factor(N)
    num = len(ass)
    if num == 2:
        ans = ass[0] - 1 + ass[1] - 1
    else:
        ans = N
        a = np.array(list(itertools.combinations_with_replacement(np.array([True, False]), num)))
        num_a = len(a)
        for j in range(num_a//2 - 1):
            j += 1
            u = np.prod(ass[a[j]])
            v = np.prod(ass[~a[j]])
            if ans >= u - 1 + v - 1:
                ans = u - 1 + v - 1

    print(ans)

if __name__ == '__main__':
    main()

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
pf = prime_factorize(N)
pf.sort(reverse=True)

# print(pf)

# pfを大きい順に交互に選んでそれぞれかけあわせる。（AとB）
# A+B-2が答え
A = 1
B = 1
for i in pf[0::2]:
  A *= i
  
for i in pf[1::2]:
  B *= i

ans = A + B - 2

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
def factorization(n):
	arr = []
	tmp = n
	for i in range(2, int(-(-n**0.5//1))+1):
		if tmp%i==0:
			cnt=0
			while tmp%i==0:
                		cnt+=1
                		tmp //= i
			for k in range(cnt):
            			arr.append(i)
	if tmp!=1:
		arr.append(tmp)
	if arr==[]:
		arr.append(n)
	return arr

n = int(input())

fac = factorization(n)
if len(fac) == 1:
	print(fac[0]-1)
	exit()
a=1
b=1
dfac=deque(fac)
c=0
for i in range(len(fac)):
	if a <= b:
		if c % 2 == 0:
			a *= dfac.popleft()
		else:
			a *= dfac.pop()
	else:
		if c % 2 == 0:
			b *= dfac.popleft()
		else:
			b *= dfac.pop()
print("%d" % (a+b-2))

Submission status: Wrong Answer

Solution code:
N = int(input())


def divisor(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 solve(N):
    list_N = divisor(N)
    ans = N - 1
    for i in list_N:
        ans_tmp = ((N / i) - 1) + (i - 1)
        if ans > ans_tmp:
            ans = ans_tmp

    return ans


print(solve(N))

Submission status: Wrong Answer

Solution code:
import itertools
import functools
import operator
import math
from bisect import bisect_right as br
from bisect import insort_right as ir

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 prod_dfs(a, p, n):
    if p * n >= sqr:
        return p
    tmp = 0
    prev = 0
    for i, next_ in enumerate(a):
        if prev == next_:
            continue
        prev = next_
        tmp = max(prod_dfs(a[:i] + a[i+1:], p * n, next_), tmp)
    return tmp

def prod_dfs_(a):
    tmp = 0
    for i, next_ in enumerate(a):
        tmp = max(prod_dfs(a[:i] + a[i+1:], 1, next_), tmp)
    return tmp

prod = functools.partial(functools.reduce, operator.mul)

a = prime_factorize(N)
sqr = int(math.sqrt(N))

if len(a) == 1:
    print(N - 1)
elif len(a) == 2:
    print(a[0] + a[1] - 2)
else:
    p = prod_dfs_(a)
    print(N // p + p - 2)

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
ans=prime_factorize(n)

while len(ans)>=3:
    ans.append(ans[0]*ans[1])
    ans.pop(0)
    ans.pop(1)

if len(ans)==1:
    count=ans[0]-1
else:
    count=ans[0]-1+ans[1]-1

print(count)

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

X = prime_factorize(N)
#print(X)
Y = []
c = 1
for j in X:
    c = c*j
    #if not c == N:
    Y.append(c)
#print(Y)

res = 1000000000000
for i in Y:
    b = int(N/i)
    if res > i + b:
        res = i + b

print(res-2)

Submission status: Wrong Answer

Solution code:
import math
 
N = int(input())
 
k = int(math.ceil(math.sqrt(N)))
  
for i in range(1,k)[::-1]:
  if N%i==0:
      print(int(N/i)+i-2)
      exit()

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
i = 1
min = 9000000000000
for _ in range(1, int(math.sqrt(N)+1)):
  if N % i == 0:
    j = N/i
    sum = j + i
    if sum < min:
      min = sum
      ans = i-1+j-1
    else:
      break
  i += 1
print(ans)

Submission status: Wrong Answer

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

for i in range(int(math.sqrt(n)), 0, -1):
  if n % i:
    next
  else:
    print(i+n//i-2)
    break
print(len(range(int(math.sqrt(n)), n+1)))

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

soinsu = prime_factorize(n)


soinsu.sort()
if len(soinsu) ==1:
    print(soinsu[0]-1)
    
else:
    right = soinsu[-1]
    left = soinsu[-2]


    for i in range(len(soinsu)-2):
        if i == 0:
            right *= soinsu[i]
        elif i % 2 == 0:
            right *= soinsu[i]
        elif i % 2 != 0:
            left *= soinsu[i]
    ans = right + left -2
    minimum = abs(left-right)

    right = soinsu[-1]
    left = soinsu[-2]

    for i in range(len(soinsu)-2):
        if i == 0:
            left *= soinsu[i]
        elif i % 2 == 0:
            left *= soinsu[i]
        elif i % 2 != 0:
            right *= soinsu[i]

    if abs(left-right) < minimum:
        print(left + right -2)
    else:
        print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
x = [1,2,3,4,5,6,7,8,9]
b = []
for a in x:
    if n%a == 0:
        y = n//a
        b.append(y)
b_min = min(b)
a = n//b_min
sum = a+b_min-2
print(sum)

Submission status: Wrong Answer

Solution code:
a = int(input())

b = []
for i in range(2,int(-(-a**0.5//1))+1):
    if a % i ==0:
        b.append(i)
        a = a/i
        while a%i==0:
            b.append(i)
            a = a/i
if a != 1:
    b.append(a)
if b == []:
    b.append(a)

if len(b)==1:
    print(int(b[0]-1))
elif len(b)==2:
    print(int(b[0]+b[1]-2))
else:
    r = b[-1]
    s = b[-2]
    for j in range(2,len(b)):
        i = -1-j
        if r>s:
            s = s*b[i]
        else:
            r = r * b[i]
    print(int(r+s-2))

Submission status: Wrong Answer

Solution code:
n = int(input())
mi = 1000
mi1 = 0
mi2 = 0
for i in range(1,int(n/2)+1):
	q = n // i
	mod = n % i
	if mod == 0:
		if mi > abs(q - i):
			mi = abs(q-1)
			mi1 = i
			mi2 = q
print(mi1+mi2-2)