Harryxun/GPT-100-sft-dataset huggingface dataset:
Problem p02580 (python)

Fixed submission:
import sys
H, W, M = map(int, input().split())
hn = [0]*H
wn = [0]*W
flag = set()
for i in range(M):
  h, w = map(int, input().split())
  hn[h-1] += 1
  wn[w-1] += 1
  flag.add((h,w))
  
#hrank = sorted(hn, key=lambda t:-t[1])
#wrank = sorted(wn, key=lambda t:-t[1])

hmax = max(hn)
wmax = max(wn)

hmaxlist = {i+1 for i,h in enumerate(hn) if h == hmax}
#for h in hn:
#  if h == hmax:
#    hmaxlist.append(h)
  
wmaxlist = {i+1 for i,w in enumerate(wn) if w == wmax}
#for w in wn:
#  if w == wmax:
#    wmaxlist.append(w)
  

for i in hmaxlist:
  for j in wmaxlist:
    if (i,j) not in flag:
      print(hmax+wmax)
      sys.exit()
print(hmax+wmax-1)

Buggy submission (verdict: Runtime Error):
H, W, M = map(int, input().split())
hn = [0]*W
wn = [0]*W
flag = set()
for i in range(M):
  h, w = map(int, input().split())
  hn[h-1] += 1
  wn[w-1] += 1
  flag.add((h,w))
  
#hrank = sorted(hn, key=lambda t:-t[1])
#wrank = sorted(wn, key=lambda t:-t[1])

hmax = max(hn)
wmax = max(wn)

hmaxlist =[]
for h in hn:
  if h == hmax:
    hmaxlist.append(h)
  
wmaxlist =[]
for w in wn:
  if w == wmax:
    wmaxlist.append(w)
  
flag2 = set()
for i in hmaxlist:
  for j in wmaxlist:
    flag2.add((i,j))

if len(flag2 - flag) == 0:
  print(hmax+wmax -1)
else:
  print(hmax+wmax)
Problem p02596 (python)

Fixed submission:
k = int(input())
if k % 2 == 0:
    print(-1)
elif k in [1,7]:
  	print(1)
else:
  amari = [7]
  tmp = 7
  for i in range(k):
      tmp = (tmp * 10) % k
      if tmp != 7:
          amari.append(tmp%k)
      else:
          break
  amari = amari * ((k//len(amari)) +1)

  ans = amari[0]
  for i in range(1, k+1):
      ans += amari[i]
      if ans % k == 0:
          print(i+1)
          break
  else:
    print(-1)

Buggy submission (verdict: Runtime Error):
k = int(input())
if k % 2 == 0:
  print(-1)
nana = 0
ans = 0
print(len(k))
while True:
  nana += (10**ans) * 7
  #print(nana)
  if nana % k == 0:
    print(ans + 1)
    break
  ans += 1
Problem p02622 (python)

Fixed submission:
s = input()
t = input()
 
ans = 0
for i in range(len(s)):
    if s[i] != t[i]:
        ans += 1
print(ans)

Buggy submission (verdict: Runtime Error):
s = input()
t = input()
 
ans = 0:
for i in range(len(s)):
  if s[i] != t[i]:
    ans += 1
print(ans)

Buggy submission (verdict: Runtime Error):
s = input()
t = input()

ans = 0:
for i in range(s):
  if s[i] != t[i]:
    ans += 1
print(ans)
Problem p02623 (python)

Fixed submission:
n, m, k = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
 
a = [0]
b = [0]
for i in range(n):
  a.append(a[i]+A[i])
for j in range(m):
  b.append(b[j]+B[j])
#print(a,b)
 
ans = 0
j = m
for i in range(n+1):
  if a[i] > k:
    break
  while (k - a[i]) < b[j]:
    j -= 1
    if j == -1:
      break
  
  ans = max(ans, i+j)
     
print(ans)

Buggy submission (verdict: Runtime Error):
 
a = [0]
b = [0]
for i in range(n):
  a.append(a[i]+A[i])
for j in range(m):
  b.append(b[j]+B[j])
#print(a,b)
 
ans = 0
j = m
for i in range(n+1):
  if a[i] > k:
    break
  while (k - a[i]) < b[j]:
    j -= 1
    if j == -1:
      break
  
  ans = max(ans, i+j)
     
print(ans)

Buggy submission (verdict: Runtime Error):
h, w, k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))

ans = 0
total = 0
while total <= k:
  if len(a) != 0 and len(b) != 0:
    if a[0] < b[0]:
      total += a.pop(0)
    else:
      total += b.pop(0)
    ans += 1
  elif len(a) == 0:
    total += b.pop(0)
    ans += 1
  elif len(b) == 0:
    total += a.pop(0)
    ans += 1
  else:
    break
if total > k:
  print(ans - 1)
else:
  print(ans)

Buggy submission (verdict: Runtime Error):
h, w, k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))

ans = 0
total = 0
while total <= k:
  if a[0] < b[0]:
    total += a.pop(0)
  else:
    total += b.pop(0)
  ans += 1

if total > k:
  print(ans - 1)
else:
  print(ans)
Problem p02682 (python)

Fixed submission:
A = list(map(int, input().split()))
 
if A[0]>=A[3]:
  print(A[3])
else:
  if A[0]+A[1]>=A[3]:
    print(A[0])
  else:
    print(A[0]-A[3]+A[0]+A[1])

Buggy submission (verdict: Runtime Error):
A = list(map(int, input().split())) 

ans=0
if A[0]<A[3]:
  ans = A[0]
else:
  ans = A[3]
  print(ans)
  
print(ans-(A[3]-A[0]-A[1])
Problem p02689 (python)

Fixed submission:
N, M = (int(i) for i in input().split())
H = list(map(int,input().split()))
ans = [1]*N
for m in range(M):
    a, b = (int(i) for i in input().split())
    if H[a-1] < H[b-1]:
        ans[a-1] = 0
    elif H[a-1] > H[b-1]:
        ans[b-1] = 0
    else:
        ans[a-1] = 0
        ans[b-1] = 0
print(ans.count(1))

Buggy submission (verdict: Runtime Error):
N, K = (int(i) for i in input().split())
H = list(map(int,input().split()))
ans = [1]*N
for m in range(M):
  a, b = (int(i) for i in input().split())
  if H[a-1] < H[b-1]:
    ans[a-1] = 0
  elif H[a-1] > H[b-1]:
    ans[b-1] = 0
print(ans.count(1))
Problem p02699 (python)

Fixed submission:
s, w = map(int, input().split())
if s > w:
  print("safe")
else:
  print("unsafe")

Buggy submission (verdict: Runtime Error):
s, w = map(int, input().split())
if s > w:
  print(safe)
else:
  print(unsafe)
Problem p02729 (python)

Fixed submission:
n, m = map(int, input().split())
ans = n*(n-1)/2 + m*(m-1)/2
print(int(ans))

Buggy submission (verdict: Runtime Error):
n, m = map(int, input())
ans = n*(n-1)/2 + m*(m-1)/2
print(ans)
Problem p02832 (python)

Fixed submission:
import sys
n = int(input())
a = list(map(int,input().split()))

ans = 0
if 1 not in a:
  print(-1)
  sys.exit()
  
index = 1
for i in a:
  if i != index:
    ans+=1
  else:
    index+=1
    
print(ans)

Buggy submission (verdict: Runtime Error):
import sys
n = int(input())
a = list(map(int,input().split()))

seta = set(a)
ans = 0
if 1 not in seta:
  print(-1)
  sys.exit()
for i in range(1,n+1):
  if i in seta:
    idx = a.index(i)
  else:
    ans += len(a) 
    break 
  ans += idx
  a = a[idx+1:]
  
print(ans)

Buggy submission (verdict: Runtime Error):
import sys
n = int(input())
a = list(map(int,input().split()))

seta = set(a)
ans = 0
if 1 not in seta:
  print(-1)
  sys.exit()
for i in range(1,n+1):
  if i in seta:
    idx = a.index(i)
  else:
    ans += len(a) 
    break 
  ans += idx
  a = a[idx+1:]
  
print(ans)
Problem p02695 (python)

Fixed submission:
n, m, q = map(int, input().split())
abcd = [list(map(int, input().split())) for i in range(q)]

A = []


def dfs(num):
    if len(num) == n:
        A.append(num)
    else:
        now = num[-1]
        for i in range(now, m + 1):
            dfs(num + [i])


for i in range(1, 10):
    dfs([i])

ans = 0
for now in A:
    point = 0
    for a, b, c, d in abcd:
        if now[b-1] - now[a-1] == c:
            point += d

    ans = max(ans, point)

print(ans)

Buggy submission (verdict: Runtime Error):
n, m, q = map(int, input().split())
abcd = []
for i in range(q):
    abcd.append(list(map(int, input().split())))

A = []


def dfs(num):
    if len(str(num)) == n:
        A.append(num)
    else:
        now = int(str(num)[-1])
        for i in range(now, m + 1):
            dfs(int(str(num) + str(i)))


for i in range(1, 10):
    dfs(i)

ans = 0
for i in range(len(A)):
    now = str(A[i])
    point = 0
    for j in range(q):
        a, b, c, d = abcd[j]
        a -= 1
        b -= 1
        if int(now[b]) - int(now[a]) == c:
            point += d

    ans = max(ans, point)

print(ans)
Problem p02831 (python)

Fixed submission:
import fractions

a, b = map(int, input().split())

ans = a * b // fractions.gcd(a, b)
print(ans)

Buggy submission (verdict: Runtime Error):
import math

a, b = map(int, input().split())

ans = a * b // math.gcd(a, b)
print(ans)
Problem p03107 (python)

Fixed submission:
s = [int(x) for x in list(map(str, input()))]

x = s.count(0)
y = s.count(1)

print(min(x, y) * 2)

Buggy submission (verdict: Runtime Error):
s = list(map(str, input()))

change = 0
count = 0
i = 0

while True:
    if not s:
        break
    if i + 1 >= len(s):
        if change != 0:
            i = 0
            change = 0
        else:
            break

    if s[i] != s[i + 1]:
        del s[i: i + 2]
        count += 1
        change += 1
    else:
        i += 1

print(count * 2)
Problem p03329 (python)

Fixed submission:
n = int(input())
num = [1]

x = 6
while x < 100000:
    num.append(x)
    x *= 6

x = 9
while x < 100000:
    num.append(x)
    x *= 9

dp = [n] * 1100000
dp[0] = 0

for i in range(n):
    for j in num:
        dp[i + j] = min(dp[i + j], dp[i] + 1)

print(dp[n])

Buggy submission (verdict: Runtime Error):
n = int(input())
num = [1]

x = 6
while x < 100000:
    num.append(x)
    x *= 6

x = 9
while x < 100000:
    num.append(x)
    x *= 9

dp = [n] * 110000
dp[0] = 0

for i in range(n):
    for j in num:
        dp[i + j] = min(dp[i + j], dp[i] + 1)

print(dp[n])

Buggy submission (verdict: Runtime Error):
n = int(input())
num = [1]

x = 6
while x < 100000:
    num.append(x)
    x *= 6

x = 9
while x < 100000:
    num.append(x)
    x *= 9

dp = [n] * 110000
dp[0] = 0

for i in range(n):
    for j in num:
        dp[i + j] = min(dp[i + j], dp[i] + 1)

print(dp[n])

Buggy submission (verdict: Runtime Error):
n = int(input())
num = [1]

x = 6
while x < 100000:
    num.append(x)
    x *= 6

x = 9
while x < 100000:
    num.append(x)
    x *= 9

dp = [n] * 110000
dp[0] = 0

for i in range(n):
    for j in num:
        dp[i + j] = min(dp[i + j], dp[i] + 1)

print(dp[n])
Problem p03774 (python)

Fixed submission:
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
cd = [list(map(int, input().split())) for _ in range(m)]

for a, b in ab:
    ans = 10 ** 10
    dist = 10 ** 10
    for i in range(m):
        c, d = cd[i]
        temp = abs(a - c) + abs(b - d)
        if dist > temp:
            dist = temp
            ans = i + 1
    print(ans)

Buggy submission (verdict: Runtime Error):
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
cd = [list(map(int, input().split())) for _ in range(n)]

for a, b in ab:
    ans = 10 ** 10
    dist = 10 ** 10
    for i in range(n):
        c, d = cd[i]
        temp = abs(a - c) + abs(b - d)
        if dist > temp:
            dist = temp
            ans = i + 1
    print(ans)

Buggy submission (verdict: Runtime Error):
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
cd = [list(map(int, input().split())) for _ in range(n)]

for a, b in ab:
    ans = 10 ** 10
    dist = 10 ** 10
    for i in range(n):
        c, d = cd[i]
        temp = abs(a - c) + abs(b - d)
        if dist > temp:
            dist = temp
            ans = i + 1
    print(ans)
Problem p02572 (python)

Fixed submission:
import sys
input = sys.stdin.readline
N = int(input())
A = map(int, input().split())
S = 0
S2 = 0
M = 10**9+7
for a in A:
  S += a
  S %= M
  S2 += a*a
  S2 %= M

# (S * S - S2)/2 
ans = (S * S - S2) * pow(2, -1, M)
ans %= M
print(ans)

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
N = int(input())
A = map(int, input().split())
S = 0
S2 = 0
M = 10**9+7
for a in A:
  S += a
  S %= M
  S2 += a*a
  S2 %= M

# (S * S - S2)/2 
ans = (S * S - S2) * pow(2, -1, M)
ans %= M
print(ans)
Problem p03013 (python)

Fixed submission:
patterns = [None] * (10**5 + 10)
patterns[0] = 1
patterns[1] = 1
calcurated_until = 1
MOD = 10**9+7
def get_patterns(n):
  global calcurated_until, patterns
  if patterns[n] is None:
    for i in range(calcurated_until + 1, n + 1):
      patterns[i] = (patterns[i-1] + patterns[i-2])%MOD
    calcurated_until = n
  #print('p', n, patterns[n])
  return patterns[n]

def solve():
  N, M = map(int, input().split())
  A = [-1]
  for _ in range(M):
    A.append(int(input()))
  A.append(N+1)
  #print(A)
  
  ans = 1
  for a1, a2 in zip(A[:-1], A[1:]):
    #print(a1, a2)
    if a2 == a1+1:
      print('0')
      return
    #print('ans', ans)
    #print('get_patterns(a2 - a1 - 2)', get_patterns(a2 - a1 - 2))
    ans *= get_patterns(a2 - a1 - 2)
    #print('ans', ans)
    ans %= MOD
    #print('ans', ans)
  print(ans)
solve()

Buggy submission (verdict: Runtime Error):
patterns = [None] * 10**5
patterns[0] = 1
patterns[1] = 1
calcurated_until = 1
MOD = 10**9+7
def get_patterns(n):
  global calcurated_until, patterns
  if patterns[n] is None:
    for i in range(calcurated_until + 1, n + 1):
      patterns[i] = (patterns[i-1] + patterns[i-2])%MOD
    calcurated_until = n
  #print('p', n, patterns[n])
  return patterns[n]

def solve():
  N, M = map(int, input().split())
  A = [-1]
  for _ in range(M):
    A.append(int(input()))
  A.append(N+1)
  #print(A)
  
  ans = 1
  for a1, a2 in zip(A[:-1], A[1:]):
    #print(a1, a2)
    if a2 == a1+1:
      print('0')
      return
    #print('ans', ans)
    #print('get_patterns(a2 - a1 - 2)', get_patterns(a2 - a1 - 2))
    ans *= get_patterns(a2 - a1 - 2)
    #print('ans', ans)
    ans %= MOD
    #print('ans', ans)
  print(ans)
solve()

Buggy submission (verdict: Runtime Error):
patterns = [None] * 10**5
patterns[0] = 1
patterns[1] = 1
MOD = 10**9+7
def get_patterns(n):
  if patterns[n] is None:
    patterns[n] = (get_patterns(n-1) + get_patterns(n-2))%MOD
  #print('p', n, patterns[n])
  return patterns[n]

def solve():
  N, M = map(int, input().split())
  A = [-1]
  for _ in range(M):
    A.append(int(input()))
  A.append(N+1)
  #print(A)
  
  ans = 1
  for a1, a2 in zip(A[:-1], A[1:]):
    #print(a1, a2)
    if a2 == a1+1:
      print('0')
      return
    #print('ans', ans)
    #print('get_patterns(a2 - a1 - 2)', get_patterns(a2 - a1 - 2))
    ans *= get_patterns(a2 - a1 - 2)
    #print('ans', ans)
    ans %= MOD
    #print('ans', ans)
  print(ans)
solve()
Problem p03072 (python)

Fixed submission:
n = int(input())
h = list(map(int, input().split()))
ans = 1

for i in range(1, n):
    if max(h[:i]) <= h[i]:
        ans += 1

print(ans)

Buggy submission (verdict: Runtime Error):
n = int(input())
h = list(int(i) for i in input().split())
i = 1
ans = 1

if h[0] <= max(h[1:]):
    while i in range(n):
        if h[i-1] <= h[i]:
            ans += 1
        i += 1
print(ans)
Problem p03221 (python)

Fixed submission:
n, m = map(int, input().split())
py = [[i] + list(map(int, input().split())) for i in range(m)]
py.sort(key=lambda x:(x[1],x[2]))

city = py[0][1]
num = 0

for i in py:
    if i[1] == city:
        num += 1
    else:
        city = i[1]
        num = 1
    i.append(num)

py.sort()

for i in py:
    print('{:06}{:06}'.format(i[1], i[3]))

Buggy submission (verdict: Runtime Error):
n, m = map(int, input().split())
py = [[i] + list(map(int, input().split())) for i in range(m)]
py.sort(key=lambda x:(x[1], x[2]))

city = py[1][2]
num = 0

for i in py:
    if i[1] == city:
        num += 1
    else:
        num = 1
        city = i[1]
    i.append(num)

py.sort()

for i in py:
    print('{:06}{:06}'.format(i[1], i[3]))

Buggy submission (verdict: Runtime Error):
n, m = map(int, input().split())
py = sorted([[i] + list(map(int, input().split())) for i in range(m)], key=lambda x:(x[1], x[2]))

city = py[1][2]
num = 0

for i in py:
    if i[1] == city:
        num += 1
    else:
        num = 1
        city = i[1]
    i.append(num)

py.sort()

for i in py:
    print('{:06}{:06}'.format(i[1], i[3]))
Problem p03785 (python)

Fixed submission:
N, C, K = map(int, input().split())
T = [int(input()) for _ in range(N)]
T.sort()

bus = [T[0]]
count = 1

for i in range(1, N):
    if T[i] <= bus[0] + K and len(bus) < C:
        bus.append(T[i])
    else:
        count += 1
        bus = []
        bus.append(T[i])

print(count)

Buggy submission (verdict: Runtime Error):
N, C, K = map(int, input().split())
T = [int(input()) for _ in range(N)]
T.sort()

bus = 0
member = 1
time = T[0] + K

for i in range(1, N):
    member += 1
    if time < T[i]:
        bus += 1
        member = 1
        time = T[i] + K
    elif time > T[i] and member >= C:
        if C % member == 0:
            bus += C // member
        else:
            bus += C // member + 1
        member = 0
        time = T[i+1] + K
    else:
        pass

if member > 0:
    bus += 1

print(bus)
Problem p03821 (python)

Fixed submission:
N = int(input())
A = []
B = []
ans = 0

for i in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

for i in range(N-1, -1, -1):
    a, b = (A[i] + ans), B[i]
    if a % b != 0:
        ans += b - a % b

print(ans)

Buggy submission (verdict: Runtime Error):
N = int(input())
ab = [list(map(int, input().split())) for _ in range(N)]
ab.reverse()
count = 0

for i in range(N):
    ab[i][0] += count
    if ab[i][1] == 1:
        continue
    else:
        if ab[i][0] > ab[i][1]:
            num = ab[i][1] - ab[i][0] % ab[i][1]
        elif ab[i][0] < ab[i][1]:
            num = ab[i][0] - ab[i][1] % ab[i][0] - 1
        count += num
        ab[i][0] += num

print(count)
Problem p03986 (python)

Fixed submission:
X = input()
s = cnt = 0

for i in range(len(X)):
    if X[i] == 'S':
        s += 1
    elif s != 0:
        cnt += 2
        s -= 1

ans = len(X) - cnt
print(ans)

Buggy submission (verdict: Runtime Error):
X = input()

for j in range(len(X//2)):
    X = X.replace('ST', '')
    if 'ST' not in X:
        break

print(len(X))

Buggy submission (verdict: Runtime Error):
X = input()

for j in range(X//2):
    X = X.replace('ST', '')
    if 'ST' not in X:
        break

print(len(X))
Problem p02773 (python)

Fixed submission:
N = int(input())
S = []
for i in range(N):
    S.append(input())
S.sort()
S.append("A")
B = []
M = 1
T = 1
for i in range(N):
    if S[i] == S[i+1]:
        T += 1
    elif T < M:
        T = 1
    elif T == M:
        T = 1
        B.append(S[i])
    else:
        M = T
        T = 1
        B = [S[i]]

for i in range(len(B)):
    print(B[i])

Buggy submission (verdict: Runtime Error):
N = int(input())
S = []
for i in range(N):
    S.append(input())
S.sort()
S.append("A")
print(S)
B = []
M = 1
T = 1
for i in range(N):
    if S[i] == S[i+1]:
        T += 1
    elif T < M:
        T = 1
    elif T == M:
        T = 1
        B.append(S[i])
    else:
        M = T
        T = 1
        B = [S[i]]

for i in range(B):
    print(B[i])
Problem p02779 (python)

Fixed submission:
N = int(input())
A = list(map(int, input().split()))
A.sort()

for i in range(N-1):
    if A[i] == A[i+1]:
        print("NO")
        exit()

print("YES")

Buggy submission (verdict: Runtime Error):
N = int(input())
A = list(map(int, input().split()))

for i in range(N-1):
    for j in range(N-i):
        if A[i] == A[i+j+1]:
            print("NO")
            exit()

print("YES")
Problem p02580 (python)

Fixed submission:
from operator import itemgetter

h, w, m = (int(x) for x in input().split())
H = [0] * h
W = [0] * w
HW = []
for _ in range(m):
    h_, w_ = (int(x) - 1 for x in input().split())
    HW.append((h_, w_))
    H[h_] += 1
    W[w_] += 1
hmax = max(H)
wmax = max(W)
hindex = set()
windex = set()

HW.sort(key=itemgetter(0, 1))
for y in range(h):
    if H[y] == hmax:
        hindex.add(y)
for x in range(w):
    if W[x] == wmax:
        windex.add(x)

count = 0
for h, w in HW:
    if h in hindex and w in windex:
        count += 1

if count == len(hindex)*len(windex):
    ans = hmax + wmax - 1
else:
    ans = hmax + wmax

print(ans)

Buggy submission (verdict: Runtime Error):
h, w, m = (int(x) for x in input().split())
S = [[0] * w for _ in range(h)]
H = [0] * h
W = [0] * w
for _ in range(m):
    h_, w_ = (int(x) - 1 for x in input().split())
    S[h_][w_] = 1
    H[h_] += 1
    W[w_] += 1

hmax = max(H)
wmax = max(W)
ans = hmax + wmax - 1
for y in range(h):
    if H[y] != hmax:
        continue
    for x in range(w):
        if W[x] != wmax:
            continue
        if S[y][x] == 0:
            ans = hmax + wmax

print(ans)
Problem p02881 (python)

Fixed submission:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce
#from fractions import gcd
#from math import gcd
import sys
def I(): return int(input())
def Is(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()
def LS(): return list(input())
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(10**6)
MOD = 10**9+7
INF = float('inf')


n = I()
sqrtn = sqrt(n)
for i in reversed(range(floor(sqrtn)+1)):
    if n % i == 0:
        a = int(n/i)
        print(a+i-2)
        exit()

Buggy submission (verdict: Runtime Error):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce
#from fractions import gcd
#from math import gcd
import sys
def I(): return int(input())
def Is(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()
def LS(): return list(input())
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(10**6)
MOD = 10**9+7
INF = float('inf')



n = I()
sqrtn = sqrt(n)
for i in reversed(range(floor(sqrtn))):
    if n % i == 0:
        a = int(n/i)
        print(a+i-2)
        exit()