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

Fixed submission:
# from math import log2
from math import log
from bisect import bisect_left


def log2(x):
    return log(x, 2)


def getComp(n):
    return (1 << (1 + int(log2(n)))) - n


N = int(input())
A = [int(s) for s in input().split()]
A.sort()
B = []
C = []
i = 0
while i < len(A):
    j = i
    count = 1
    while i+1 < len(A) and A[j] == A[i+1]:
        count += 1
        i += 1
    B.append(A[j])
    C.append(count)
    i += 1

count = 0
i = len(B) - 1
while i >= 0:
    comp = getComp(B[i])
    j = bisect_left(B, comp)
    if i == j and C[i] < 2:
        i -= 1
        continue
    if B[j] != comp:
        i -= 1
        continue
    if not C[i] or not C[j]:
        i -= 1
        continue
    C[i] -= 1
    C[j] -= 1
    count += 1

print(count)

Buggy submission (verdict: Runtime Error):
# from math import log2
from math import log
from bisect import bisect_left


def log2(x):
    return log(x, 2)


def getComp(n):
    return (1 << (1 + int(log2(n)))) - n


N = int(input())
A = [int(s) for s in input().split()]
A.sort()
avail = [True for _ in range(len(A))]

count = 0
for i in range(len(A) - 1, -1, -1):
    if not avail[i]:
        continue
    comp = getComp(A[i])
    j = bisect_left(A, comp)
    while True:
        if A[j] != comp:
            break
        if i == j or not avail[j]:
            j += 1
            continue
        avail[i] = False
        avail[j] = False
        count += 1
        break

print(count)

Buggy submission (verdict: Runtime Error):
from math import log2
from bisect import bisect_left


def getComp(n):
    return (1 << (1 + int(log2(n)))) - n


N = int(input())
A = [int(s) for s in input().split()]
A.sort()
avail = [True for _ in range(len(A))]

count = 0
for i in range(len(A) - 1, -1, -1):
    if not avail[i]:
        continue
    comp = getComp(A[i])
    j = bisect_left(A, comp)
    while True:
        if A[j] != comp:
            break
        if i == j or not avail[j]:
            j += 1
            continue
        avail[i] = False
        avail[j] = False
        count += 1
        break

print(count)
Problem p03253 (python)

Fixed submission:
# import sys
from math import factorial
from functools import reduce


def mmul(a, b, mod):
    return (a % mod) * (b % mod) % mod


def mfact(a, mod):
    fact = 1
    for m in range(2, a + 1):
        fact *= m % mod
        fact %= mod
    return fact


def mpow(a, b, mod):
    if b == 0:
        return 1
    if b == 1:
        return a % mod
    if b % 2 == 0:
        return mpow(a, b / 2, mod) ** 2 % mod
    return mpow(a, b // 2, mod) ** 2 * a % mod


def mdiv(a, b, mod):
    return mmul(a, mpow(b, mod - 2, mod), mod)


# (n+a)Ca = (n+a)! / n!a! mod mod for n >> a
def mnpaca(n, a, mod):
    res = 1
    for num in range(n + 1, n + a + 1):
        res *= num % mod
        res %= mod
    return mdiv(res, factorial(a), mod)

mod = 1000000007
N, M = [int(s) for s in input().split()]

prime_counts = []
i = 2
while i * i <= M:
    count = 0
    while M % i == 0:
        M /= i
        count += 1
    if count:
        prime_counts.append(count)
    i += 1
if M > 1:
    prime_counts.append(1)

res = reduce(lambda x, y: x * y, [mnpaca(N - 1, c, mod) for c in prime_counts],
             1)

print(res % mod)

Buggy submission (verdict: Runtime Error):
# import sys
from math import factorial
from functools import reduce


def mmul(a, b, mod):
    return (a % mod) * (b % mod) % mod


def mfact(a, mod):
    fact = 1
    for m in range(2, a + 1):
        fact *= m % mod
        fact %= mod
    return fact


def mpow(a, b, mod):
    if b == 0:
        return 1
    if b == 1:
        return a % mod
    if b % 2 == 0:
        return mpow(a, b / 2, mod) ** 2 % mod
    return mpow(a, b // 2, mod) ** 2 * a % mod


def mdiv(a, b, mod):
    return mmul(a, mpow(b, mod - 2, mod), mod)


# (n+a)Ca = (n+a)! / n!a! mod mod for n >> a
def mnpaca(n, a, mod):
    res = 1
    for num in range(n + 1, n + a + 1):
        res *= num % mod
        res %= mod
    return mdiv(res, factorial(a), mod)

mod = 1000000007
N, M = [int(s) for s in input().split()]

prime_counts = []
i = 2
while i * i <= M:
    count = 0
    while M % i == 0:
        M /= i
        count += 1
    if count:
        prime_counts.append(count)
    i += 1
if M > 1:
    prime_counts.append(1)

res = reduce(lambda x, y: x * y, [mnpaca(N - 1, c, mod) for c in prime_counts])

print(res % mod)
Problem p03275 (python)

Fixed submission:

from bisect import bisect_left
from math import ceil
import sys
if sys.version_info[0:2] >= (3, 3):
    from collections.abc import Sequence
else:
    from collections import Sequence


class LazySequence(Sequence):
    def __init__(self, f, n):
        self.f = f
        self.n = n

    def __len__(self):
        return self.n

    def __getitem__(self, i):
        if not (0 <= i < self.n):
            raise IndexError
        return self.f(i)


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def __len__(self):
        return self.size

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, v):
        while i <= self.size:
            self.tree[i] += v
            i += i & -i


N = int(input())
a = [0] + [int(s) for s in input().split()]
# a = [0] * (N + 1)


def count_lr(x):
    s = [0] * (N + 1)
    for i in range(1, N + 1):
        s[i] = s[i - 1] + (1 if a[i] >= x else -1)

    ss = sorted(set(s))
    ind = {v: i + 1 for i, v in enumerate(ss)}

    b = Bit(N + 10)
    count = 0
    for i in range(N + 1):
        j = ind[s[i]]
        count += b.sum(j)
        b.add(j, 1)

    return count


# i: 0, 1, ..., 10 ** 9
# x: 10 ** 9, ..., 0
counts = LazySequence(lambda i: count_lr(10 ** 9 - i), 10 ** 9 + 1)
ans = 10 ** 9 - bisect_left(counts, ceil(N * (N + 1) / 4))
print(ans)

Buggy submission (verdict: Runtime Error):

from bisect import bisect_left
from math import ceil
import collections.abc


class LazySequence(collections.abc.Sequence):
    def __init__(self, f, n):
        self.f = f
        self.n = n

    def __len__(self):
        return self.n

    def __getitem__(self, i):
        if not (0 <= i < self.n):
            raise IndexError
        return self.f(i)


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def __len__(self):
        return self.size

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, v):
        while i <= self.size:
            self.tree[i] += v
            i += i & -i


N = int(input())
a = [0] + [int(s) for s in input().split()]


def count_lr(x):
    s = [0] * (N + 1)
    for i in range(1, N + 1):
        s[i] = s[i - 1] + (1 if a[i] >= x else -1)

    ss = sorted(s)

    def f(v):
        i = bisect_left(ss, v)
        return i + 1

    b = Bit(N + 10)
    count = 0
    for i in range(N + 1):
        fi = f(s[i])
        count += b.sum(fi)
        b.add(fi, 1)

    return count


# i: 0, 1, ..., 10 ** 9 + 10
# x: 10 ** 9 + 10, ..., 0
counts = LazySequence(lambda i: count_lr(10 ** 9 + 10 - i), 10 ** 9 + 10)
ans = 10 ** 9 + 10 - bisect_left(counts, ceil(N * (N + 1) / 4))
print(ans)
Problem p03013 (python)

Fixed submission:
#!/usr/bin/env python
N, M = map(int, input().split())
m = 10**9+7
F = [0]*N
for _ in range(M):
    F[int(input())-1] = 1

a, b = 0, 1
for n in range(N):
    if F[n]:
        a, b = b, 0
    else:
        a, b = b, (a+b) % m
print(b)

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python
import sys
N, M = map(int, input().split())
A = [int(input()) for i in range(M)]
m = 10**9+7
F = [0, 1]
for i in range(2, N+1):
    F.append(F[i-1]+F[i-2])

for i, a in enumerate(A[:-1]):
    if a+1 == A[i+1]:
        print(0)
        sys.exit()

ans = 1
s = 0
for i in range(N):
    if i in A:
        ans *= F[i-s]
        ans %= m
        s = i+1
ans *= F[N-s+1]
ans %= m 
print(ans)
Problem p03053 (python)

Fixed submission:
#!/usr/bin/env python
H, W = map(int, input().split())

g = [[True] * (W+2)]
for _ in range(H):
    g.append([True] + [x == '#' for x in input()] + [True])
g.append([True] * (W+2))

l = []
for i in range(1, H+1):
    for j in range(1, W+1):
        if g[i][j]:
            l.append((i, j))

c = 0
while l:
    ll = []
    for i,j in l:
        if not g[i+1][j]:
            g[i+1][j] = True
            ll.append((i+1, j))
        if not g[i-1][j]:
            g[i-1][j] = True
            ll.append((i-1, j))
        if not g[i][j+1]:
            g[i][j+1] = True
            ll.append((i, j+1))
        if not g[i][j-1]:
            g[i][j-1] = True
            ll.append((i, j-1))
    c += 1
    l = ll

print(c-1)

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python
H, W = map(int, input().split())
A = [[s for s in input()] for i in range(H)]

l = []
for i in range(H):
        for j in range(W):
            if A[i][j] == '#':
                l.append([i,j])

c = 0
for k in range(H*W):
    c += 1
    for i in range(H):
        for j in range(W):
            if A[i][j] == '#':
                if i >= 1 and [i-1,j] not in l:
                    l.append([i-1,j])
                if j >= 1 and [i,j-1] not in l:
                    l.append([i,j-1])
                if i+1 < H and [i+1,j] not in l:
                    l.append([i+1, j])
                if j+1 < H and [i,j+1] not in l:
                    l.append([i, j+1])
    if len(l) == H*W:
        break
    for x in l:
        A[x[0]][x[1]] = '#'
print(c)
Problem p02990 (python)

Fixed submission:
import math
import sys


def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


input = sys.stdin.readline

N, K = map(int, input().strip().split(' '))
div = 1000000000 + 7

for i in range(K):
    if i > N - K:
        print(0)
    else:
        perm = comb(N - K + 1, i + 1) * comb(K - 1, i)
        print(perm % div)

Buggy submission (verdict: Runtime Error):
import math
import sys


def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


input = sys.stdin.readline

N, K = map(int, input().strip().split(' '))
div = 1000000000 + 7

for i in range(K):
    perm = comb(N - K + 1, i + 1) * comb(K - 1, i)
    print(perm % div)
Problem p03013 (python)

Fixed submission:
N,M=map(int,input().split())
a = [int(input()) for _ in range(M)]
dp = [0]*(N+1)
j = 0
dp[0] = 1
mod = 10**9+7
for i in range(1, N+1):
    if j < M and i == a[j]:
        j += 1
    elif i == 1:
        dp[i] = 1
    else:
        dp[i] = (dp[i-1]+dp[i-2]) % mod
print(dp[N])

Buggy submission (verdict: Runtime Error):
N,M=map(int,input().split())
a = [int(input()) for _ in range(M)]
dp = [0]*(N+1)
j = 0
dp[0] = 1
mod = 10**9+7
for i in range(1, N+1):
    if i == a[j]:
        j += 1
        j = min(M-1, j)
    elif i == 1:
        dp[i] = 1
    else:
        dp[i] = (dp[i-1]+dp[i-2]) % mod
print(dp[N])
Problem p03326 (python)

Fixed submission:
n,m = map(int,input().split())
xyz = []
for i in range(n):
    x,y,z = map(int,input().split())
    xyz.append((x,y,z))
k1 = [1,1,1,1,-1,-1,-1,-1]
k2 = [1,1,-1,-1,1,1,-1,-1]
k3 = [1,-1,1,-1,1,-1,1,-1]

sx,sy,sz = 0,0,0
ans_list = []
for i in range(8):
    xyz.sort(key=lambda x: x[0]*k1[i]+x[1]*k2[i]+x[2]*k3[i],reverse=True)
    for j in range(m):
        sx,sy,sz = sx+xyz[j][0],sy+xyz[j][1],sz+xyz[j][2]
    ans_list.append(abs(sx)+abs(sy)+abs(sz))
    sx,sy,sz = 0,0,0
print(max(ans_list))

Buggy submission (verdict: Runtime Error):
n,m = map(int,input().split())
x,y,z = [],[],[]
for i in range(n):
    line = list(map(int,input().split()))
    x.append(line[0])
    y.append(line[1])
    z.append(line[2])
ls = []
def dfs(sx,sy,sz,i,k):
    if k == 0:
        ls.append(abs(sx)+abs(sy)+abs(sz))
        return abs(sx)+abs(sy)+abs(sz)
    if i == n:
        return 0
    dfs(sx,sy,sz,i+1,k)
    dfs(sx+x[i],sy+y[i],sz+z[i],i+1,k-1)
dfs(0,0,0,0,m)
print(max(ls))
Problem p03013 (python)

Fixed submission:
maxNum, brokenCount= map(int, input().split())

brokenIndexSet= set([int(input()) for i in range(brokenCount)])

ans = [0]*(maxNum + 1)
ans[0] = 1

#print(ans[-1])

for i in range(1, maxNum + 1):
    if i in brokenIndexSet:
        ans[i] = 0
    else:
        ans[i] = (ans[i - 1] + ans[i - 2]) % 1000000007 

print(ans[maxNum])

Buggy submission (verdict: Runtime Error):



class MyClass:
    patternCount = 0

    def skip(self, maxNum, currentIndex):
        if currentIndex > maxNum or currentIndex in brokenIndexList:
            return
        
        if maxNum == currentIndex:
            self.patternCount += 1
            return

        self.skip(maxNum, currentIndex + 1)
        self.skip(maxNum, currentIndex + 2)

maxNum, brokenCount= map(int, input().split())

brokenIndexList = []
for i in range(brokenCount):
    brokenIndexList.append(int(input()))

if maxNum == 0:
    print(0)

c = MyClass()
c.skip(maxNum, 0)

result = c.patternCount % 1000000007
print(result)

Buggy submission (verdict: Runtime Error):



class MyClass:
    patternCount = 0

    def skip(self, maxNum, currentIndex):
        if currentIndex > maxNum or currentIndex in brokenIndexList:
            return
        
        if maxNum == currentIndex:
            self.patternCount += 1
            return

        self.skip(maxNum, currentIndex + 1)
        self.skip(maxNum, currentIndex + 2)

maxNum, brokenCount= map(int, input().split())

brokenIndexList = []
for i in range(brokenCount):
    brokenIndexList.append(int(input()))

if maxNum == 0:
    print(0)

c = MyClass()
c.skip(maxNum, 0)

print(c.patternCount)

Buggy submission (verdict: Runtime Error):
class MyClass:
    patternCount = 0

    def skip(self, maxNum, currentIndex):
        if currentIndex >= maxNum or currentIndex in brokenIndexList:
            return
        
        if maxNum -1 == currentIndex:
            self.patternCount += 1
            return

        self.skip(maxNum, currentIndex + 1)
        self.skip(maxNum, currentIndex + 2)

maxNum, brokenCount= map(int, input().split())

brokenIndexList = []
for i in range(brokenCount):
    brokenIndexList.append(int(input()))

if maxNum == 0:
    print(0)

c = MyClass()
c.skip(maxNum, -1)

print(c.patternCount)
Problem p02935 (python)

Fixed submission:
N = int(input())
A = list(map(float,input().split()))
A.sort()
tmp = A[0]
for i in range(1,N):
    tmp = (tmp+A[i])/2
print(tmp)

Buggy submission (verdict: Runtime Error):
N = int(input())
A = list(map(float,input().split()))
tmp = 0
A.sorted()
tmp = A[0]
for i in range(1,N):
    tmp = (tmp+A[i])/2
print(tmp)
Problem p03041 (python)

Fixed submission:
inputstr1 = input().split()
n = int(inputstr1[0])
k = int(inputstr1[1])
s = input()

smalls = s[k-1].lower()

print(s[:k-1] + smalls + s[k:])

Buggy submission (verdict: Runtime Error):
num = input()
num1 = int(num[0] + num[1])
num2 = int(num[2] + num[3])

if(num1 < 13) and (num1 > 0):
    if(num2 < 13) and (num2 > 0):
        print("AMBIGUOUS")
    else:
        print("MMYY")
else:
    if(num2 < 13) and (num2 > 0):
        print("YYMM")
    else:
        print("NA")
Problem p03075 (python)

Fixed submission:
antenna = [int(input()) for i in range(5)]
k = int(input())

for i in antenna:
    antenna_out = list(filter(lambda j: (i - j) > k, antenna))
    if len(antenna_out) != 0:
        print(":(")
        break
else:
    print("Yay!")

Buggy submission (verdict: Runtime Error):
num = []
n = int(input())
for i in range(5):
    num.append(int(input()))
a = min(num)
t = n // a
t += 4
if (n % a != 0):
    t += 5
else:
    
print(t)
Problem p03107 (python)

Fixed submission:
import numpy as np
s = list(input())

cnt = np.empty(2)
for i in range(len(s)):
    cnt[int(s[i]) - 0] += 1
ans = np.min(cnt) * 2
print(int(ans))

Buggy submission (verdict: Runtime Error):
import copy
s = list(input())
def check01_2(s, pos):
    p = 0
    if abs(len(s) - pos)  > 2:
        for i in range(pos, len(s), 1):
            if s[i] != s[i+1]:
                del s[i:i+2]
                if i !=0:
                    p = i-1
                return check01_2(s, p)
    return s

s2 = copy.deepcopy(s)
s2 = check01_2(s2, 0)
print(len(s) - len(s2))

Buggy submission (verdict: Runtime Error):
import copy
s = list(input())

def check01(s):
    if len(s) > 1:
        for i in range(len(s)-1):
            if s[i] != s[i+1]:
                del s[i:i+2]
                return check01(s)
    return s
s2 = copy.deepcopy(s)
s2 = check01(s2)
print(len(s) - len(s2))
Problem p02935 (python)

Fixed submission:
n = int(input())
a = list(map(int,input().split()))
a.sort()
now = a[0]
for i in range(1,n):
  now = ( now + a[i] ) / 2
print(now)

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

w = sorted(v)
ans = [] 

for i in range(1,n):
  ans.append(0)

for i in range(1,n):
  ans[i-1] = (w[i]+w[i-1])/2
  w[i] = ans[i-1]

print(ans[-1])
Problem p02951 (python)

Fixed submission:
a,b,c = map(int, input().split())
 
if b+c > a :
  print(c-(a-b))
  
else:
  print(0)

Buggy submission (verdict: Runtime Error):
n = int(input())
count = 0
 
for i in range(1,n+1):
  if len(int(i))%2 == 1:
    count += 1
 
print(count)

Buggy submission (verdict: Runtime Error):
n = int(input())
count = 0
 
for i in range(1,n+1):
  if len(int(i))//2 == 1:
    count += 1
 
print(count)

Buggy submission (verdict: Runtime Error):
n = int(input())
count = 0
 
for i in n:
  if len(i)%2 != 0:
    count += 1
 
print(count)

Buggy submission (verdict: Runtime Error):
A = int(input())
B = int(input())
C = int(input())

if B+C > A :
  print(C-(A-B))
  
else:
  print(0)
Problem p03011 (python)

Fixed submission:
p, q, r = map(int, input().split())
print(min(p+q, p+r, q+r))

Buggy submission (verdict: Runtime Error):
p,q,r = map(int, input().split())

print(min(p+q,q+r,r+p)
Problem p03041 (python)

Fixed submission:
n,k = map(int, input().split())
s = str(input()) 

print(s[:k-1]+s[k-1].lower()+s[k:])

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

k_lower = s[:k-1]+s[k-1].lower()+s[k:]
print(k_lower)

Buggy submission (verdict: Runtime Error):
n,k = map(str, input().split())
s = str(input()) 

k_lower = s[:k-1]+s[k-1].lower()+s[k:]
print(k_lower)

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

k_lower = s[:k-1]+s[k-1].lower()+s[k:]
print(k_lower)

Buggy submission (verdict: Runtime Error):
n,k = map(str, input().split())
s = str(input()) 

k_lower = s.lower(k-1)
print(k_lower)
Problem p03242 (python)

Fixed submission:
n = input()
ans = 0
for i in range(3):
  if n[i] == '1':
    ans += 10**(2-i) * 9
  else:
    ans += 10**(2-i) * 1
print(ans)

Buggy submission (verdict: Runtime Error):
n = list(input())

for i in n:
  if n[i] == 1:
    n[i]=9
  elif n[i] == 9:
    n[i]=1
print(''.join(n))

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

for i in n:
  if n[i] == 1:
    n[i]=9
  elif n[i] == 9:
    n[i]=1
print(''.join(n))
Problem p03315 (python)

Fixed submission:
s = input()
cnt = 0
 
for i in s:
  if i == '+':
    cnt = cnt +1
  elif i == '-':
    cnt = cnt-1
 
print(cnt)

Buggy submission (verdict: Runtime Error):
s = input()
cnt = 0
 
for i in s:
  if i = '+':
    cnt = cnt +1
  elif i = '-':
    cnt = cnt-1
 
print(cnt)

Buggy submission (verdict: Runtime Error):
s = list(int(input()))
cnt = 0
 
for i in s:
  if i = +:
    cnt = cnt +1
  elif i = -:
    cnt = cnt-1
 
print(cnt)

Buggy submission (verdict: Runtime Error):
s = list(input())
cnt = 0

for i in s:
  if i = '+':
    cnt = cnt +1
  if i = '-':
    cnt = cnt-1

print(cnt)
Problem p02959 (python)

Fixed submission:
n = int(input())
A= list(map(int, input().split()))
B= list(map(int, input().split()))
r = 0
for i, b in enumerate(B):
    if b <= A[i]:
        r += b
    else:
        b -= A[i]
        r += A[i]
        if b <= A[i+1]:
            A[i+1] -= b
            r += b
        else:
            r += A[i+1]
            A[i+1]=0
            
print(r)

Buggy submission (verdict: Runtime Error):
for i, b in enumerate(B):
    if b <= A[i]:
        r += b
    else:
        b -= A[i]
        r += A[i]
        if b <= A[i+1]:
            A[i+1] -= b
            r += b
        else:
            r += A[i+1]
            A[i+1]=0
            
print(r)
Problem p03012 (python)

Fixed submission:
N = int(input())
W = list(map(int, input().split())) 
min_diff = 1000
for i in range(N):
    s1 = sum(W[0:i+1])
    s2 = sum(W) - s1
    if min_diff > abs(s1-s2):
        min_diff = abs(s1-s2)
print(min_diff)

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

min_diff = 1000
tot_wt = sum(W)
for i in range(2**N):
    i_bit = list(map(int, list(np.binary_repr(i, N))))
    s1= np.dot(i_bit, W)
    s2 = tot_wt - s1
    if min_diff > abs(s1-s2):
        min_diff = abs(s1-s2)
        print(min_diff, i_bit)
Problem p02935 (python)

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

v.sort()

res = v[0]

for i in range(1,N):
    res = (res + v[i]) / 2 

print(res)

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

v.sort()

res = v[0]

for i in range(i,N):
    res = (res + v[i]) / 2 

print(res)
Problem p03329 (python)

Fixed submission:
#!/usr/bin/env python


def get_all_values(N, v):
    all_values = []

    current = v
    while current <= N:
        all_values.append(current)
        current *= v

    return all_values


def get_min_number(memo, all_values, N):
    if N in memo:
        return memo[N]

    if N in all_values:
        return 1
    elif N < 6:
        return N
    else:
        min_number = min(
            [get_min_number(memo, all_values, N - v) + 1 for v in all_values if N - v > 0]
        )
        memo[N] = min_number
        return min_number


def solve(N):
    # Get all values and sort in descent order
    all_values = [1] + get_all_values(N, 6) + get_all_values(N, 9)
    sorted_all_values = list(reversed(sorted(all_values)))

    # Recursively get minimum number
    memo = {}
    ans = get_min_number(memo, sorted_all_values, N)

    return ans


def main():
    # Input
    N = int(input())

    # Solve
    ans = solve(N)

    # Answer
    print(ans)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python
from typing import List, Dict


def get_all_values(N: int, v: int) -> List[int]:
    all_values = []

    current = v
    while current < N:
        all_values.append(current)
        current *= v

    return all_values


def get_min_number(memo: Dict[int, int], all_values: List[int], N: int) -> int:
    if N in memo:
        return memo[N]

    if N in all_values:
        return 1
    elif N < 6:
        return N
    else:
        min_number: int = min(
            [get_min_number(memo, all_values, N - v) + 1 for v in all_values if N - v >= 0]
        )
        memo[N] = min_number
        return min_number


def solve(N: int) -> int:
    # Get all values and sort in descent order
    all_values: List[int] = [1] + get_all_values(N, 6) + get_all_values(N, 9)
    sorted_all_values: List[int] = list(reversed(sorted(all_values)))

    # Recursively get minimum number
    memo: Dict[int, int] = {}
    ans = get_min_number(memo, sorted_all_values, N)

    return ans


def main():
    # Input
    N = int(input())

    # Solve
    ans = solve(N)

    # Answer
    print(ans)


if __name__ == "__main__":
    main()