Problem:
 Score : 300 points    Problem Statement To make it difficult to withdraw money, a certain bank allows its customers to withdraw only one of the following amounts in one operation:    1 yen (the currency of Japan)    6 yen, 6^2(=36) yen, 6^3(=216) yen, ...    9 yen, 9^2(=81) yen, 9^3(=729) yen, ...    At least how many operations are required to withdraw exactly N yen in total?  It is not allowed to re-deposit the money you withdrew.      Constraints  1 \leq N \leq 100000  N is an integer.         Input Input is given from Standard Input in the following format:  N       Output If at least x operations are required to withdraw exactly N yen in total, print x .        Sample Input 1 127      Sample Output 1 4  By withdrawing 1 yen, 9 yen, 36(=6^2) yen and 81(=9^2) yen, we can withdraw 127 yen in four operations.       Sample Input 2 3      Sample Output 2 3  By withdrawing 1 yen three times, we can withdraw 3 yen in three operations.       Sample Input 3 44852      Sample Output 3 16

Solution (Python):
from bisect import bisect

N=int(input())

Lis=[1]
temp=6
while temp<=100000:
    Lis.append(temp)
    temp*=6
temp=9
while temp<=100000:
    Lis.append(temp)
    temp*=9

Lis=list(set(Lis))
Lis.sort()

DP=[100001]*(N+1)

DP[0]=0

for i in range(1,N+1):
    temp=[]
    idx=bisect(Lis,i)
    for j in range(idx):
        tem=1+DP[i-Lis[j]]
        temp.append(tem)
    DP[i]=min(temp)
print(DP[N])

Solution (Python):
n = int(input())
a = 6
b = [1]
b.append(a)
while a <= 100000:
	a *= 6
	b.append(a)
c = 9
b.append(c)
while c <= 100000:
	c *= 9
	b.append(c)
b.sort()
INF = 10**7
dp = [INF]*100001
dp[0] = 0
for i in range(100001):
	for j in b:
		if i + j > 100000:
			continue
		dp[i+j] = min(dp[i]+1, dp[i+j])
print (dp[n])

Solution (Python):
INF = 110000

n = int(input())
dp = [ INF for _ in range(n+10)]
dp[0] = 0

for i in range(n+10):
    j = 1
    while j<=i:
        dp[i] = min(dp[i],dp[i-j]+1)
        j*=6
    k = 1
    while k<=i:
        dp[i]=min(dp[i],dp[i-k]+1)
        k*=9
print(dp[n])

Solution (Python):
N=int(input())
ans=N
for i in range(N+1):
    cnt=0
    t=i
    while t>0:
        cnt+=t%6
        t//=6
    j=N-i
    while j>0:
        cnt+=j%9
        j//=9
    ans = min(ans,cnt)
print(ans)

Solution (Python):
n=int(input())
inf=10**10
dp=[inf]*(n+1)
dp[0]=0
dp[1]=1
m6=[]
m9=[]
j6=1
while j6<=n:
    m6.append(j6)
    dp[j6]=1
    j6*=6
j9=1
while j9<=n:
    m9.append(j9)
    dp[j9]=1
    j9*=9
for i in range(1,n+1):
    if dp[i]==1:
        continue
    for j in m6:
        if i-j>=0:
            dp[i]=min(dp[i],dp[i-j]+1)
    for k in m9:
        if i-k>=0:
            dp[i]=min(dp[i],dp[i-k]+1)
print(dp[n])

Solution (Python):
n=int(input())
INF=2<<60
dp=[INF]*(2*10**5)
money_list=[1]+[6**i for i in range(1, 7)]+[9**i for i in range(1, 6)]
money_list.sort()
for m in money_list:
    dp[m-1]=1
for i in range(n):
    for m in money_list:
        dp[i+m]=min(dp[i+m], dp[i]+1)
print(dp[n-1])

Solution (Python):
n=int(input())
r=n
def c(c,n):
	s=0
	while n>0:
		s+=n%c
		n//=c
	return s
for i in range(n+1):
	r=min(c(6,i)+c(9,n-i),r)
print(r)

Solution (Python):
n = int(input())
list6 = [6**i for i in range(7)]
list9 = [9**i for i in range(6)]
m = {}
def ans(n):
    if n <= 5:
        return n
    elif n in m:
        return m[n]
    else:
        m6 = max(i for i in list6 if i <= n)
        m9 = max(i for i in list9 if i <= n)
        l6 = n - m6
        l9 = n - m9
        m[n] = min(ans(l6)+1,ans(l9)+1)
        return m[n]
print(ans(n))

Solution (Python):
import bisect
 
x = int(input())
six_list = [6 ** i for i in range(7)]
nine_list = [9 ** i for i in range(6)]
 
 
def six_nine(n):
    if n == 0:
        return 0
    else:
        six = six_list[bisect.bisect_right(six_list, n) - 1]
        nine = nine_list[bisect.bisect_right(nine_list, n) - 1]
        return min(n // six + six_nine(n % six), 1 + six_nine(n - nine))
 
 
print(six_nine(x))

Solution (Python):
def main():
    
    cash = [1]
    n = int(input())
    
    for i in range(1, n):
        if 6 ** i > n:
            break
        cash.append(6 ** i)
    for i in range(1, n):
        if 9 ** i > n:
            break
        cash.append(9 ** i)
    cash.sort()
    
    ans = [float('inf')] * (n + 1)
    ans[0] = 0
    for i in range(1, n + 1):
        for j in cash:
            if i - j < 0:
                break
            else:
                ans[i] = min(ans[i], ans[i - j] + 1)
    print(ans[n])


if __name__ == "__main__":
    main()

Solution (Python):

cash = [1]
n = int(input())

for i in range(1, n):
    if 6 ** i > n:
        break
    cash.append(6 ** i)
for i in range(1, n):
    if 9 ** i > n:
        break
    cash.append(9 ** i)
cash.sort()

ans = [float('inf')] * (n + 1)
ans[0] = 0
for i in range(1, n + 1):
    for j in cash:
        if i - j < 0:
            break
        else:
            ans[i] = min(ans[i], ans[i - j] + 1)
print(ans[n])

Solution (Python):
cash = [1]
n = int(input())
ans = [float('inf')] * (n + 1)
for i in range(1, n):
    if 6 ** i > n:
        break
    cash.append(6 ** i)
for i in range(1, n):
    if 9 ** i > n:
        break
    cash.append(9 ** i)
cash.sort()
ans[0] = 0
for i in range(1, n + 1):
    for j in cash:
        if i - j < 0:
            break
        else:
            ans[i] = min(ans[i], ans[i - j] + 1)
print(ans[n])

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

ans = []
for i in range(n+1):
    cnt6 = i
    cnt9 = n - i
    ans6 = 0
    ans9 = 0
    
    while cnt6 > 0:
        sho = 6**math.floor(math.log(cnt6, 6))
        ans6 += cnt6//sho
        cnt6= cnt6%sho
        
    while cnt9 > 0:
        if cnt9 != 59049:
            sho2 = 9**math.floor(math.log(cnt9, 9))
        else:
            sho2=59049
        ans9 += cnt9//sho2
        cnt9 = cnt9%sho2
        
    ans.append(ans6+ans9)
    sho, sho2 = 0, 0
        
print(min(ans))

Solution (Python):
coins=[1]
n=int(input())
for i in range(20):
    coins.append(6**i)
for i in range(20):
    coins.append(9**i)
dp=[10**9]*(n+1)
dp[0]=0 
for c in coins:
    for j in range(n+1):
        if c<=j:
            dp[j]=min(dp[j],dp[j-c]+1)
print(dp[n])

Solution (Python):
n=int(input())
INF=10**7
w=[1,6,9,36,81,216,729,1296,6561,7776,46656,59049]
dp=[INF]*100001
dp[0]=0
for i in range(100001):
  for j in w:
    if i+j>100000:continue
    dp[i+j]=min(dp[i]+1,dp[i+j])
print(dp[n])

Solution (Python):
import sys
sys.setrecursionlimit(10**9)

n=int(input())
l=[]
for i in range(1,10):
    if 6**i>n:
        break
    l.append(6**i)
for i in range(1,10):
    if 9**i>n:
        break
    l.append(9**i)

l.sort()

if n in l:
    print(1)
    exit()

inf=float("inf")
dp=[inf]*(n+1)

def dfs(n):
    if dp[n]!=inf:
        return dp[n]
    if n<6:
        return n
    m=inf
    for d in l:
        if n-d<0:
            break
        m=min(m,dfs(n-d)+1)
    dp[n]=m
    return m

print(dfs(n))

Solution (Python):
n=int(input())
b=[1,6,36,216,1296,7776,46656]
q=[9,81,729,6561,59049]
d=[100000]*(n+1)
d[0]=0
for i in range(n):
  for j in b:
    if i+j<=n:
      d[i+j]=min(d[i+j],d[i]+1)
  for k in q:
    if i+k<=n:
      d[i+k]=min(d[i+k],d[i]+1)
print(d[n])

Solution (Python):
N = int(input())

one = [1]
six_multi = [6, 6**2, 6**3, 6**4, 6**5, 6**6]
nine_multi = [9, 9**2, 9**3, 9**4, 9**5]
deposit = one + six_multi + nine_multi

dp = [10**10 for _ in range(N+1)] 
dp[0] = 0

for i in range(0, N):
    for d in range(len(deposit)):
        if i+deposit[d] <= N:
            dp[i+deposit[d]] = min(dp[i+deposit[d]], dp[i] + 1)

print(dp[N])

Solution (Python):
import math

import numpy as np


def get_choices(n, p):
    choices = set()
    for i in range(1, n):
        powered = int(math.pow(p, i))
        if powered <= n:
            choices.add(powered)
        else:
            break
    return choices


def main(n):
    choices = {1}
    choices |= get_choices(n, 6)
    choices |= get_choices(n, 9)

    dp = np.full(shape=n + 1, fill_value=n, dtype=int)
    dp[0] = 0
    dp[1] = 1

    for i in range(1, n + 1):
        if i in choices:
            dp[i] = 1
        else:
            for choice in choices:
                pre_index = i - choice
                if pre_index > 0:
                    if dp[i] > dp[pre_index] + 1:
                        dp[i] = dp[pre_index] + 1
                else:
                    break

    return dp[-1]


if __name__ == '__main__':
    N = int(input())
    print(main(N))

Solution (Python):
n = int(input())
dp = [10**6] * (n+1)
dp[0] = 0
for i in range(1,n+1):
  c = 1
  d = 1
  dp[i] = min(dp[i],dp[i-1]+1)
  while True:
    if i - 6**c >= 0:
      dp[i] = min(dp[i],dp[i-6**c]+1)
    else:
      break
    c += 1
  while True:
    if i - 9**d >= 0:
      dp[i] = min(dp[i],dp[i-9**d]+1)
    else:
      break
    d += 1
print(dp[n])

Solution (Python):
n = int(input())
dp = [10**6] * (n+1)
dp[0] = 0
for i in range(1,n+1):
  c = 1
  d = 1
  dp[i] = min(dp[i],dp[i-1]+1)
  while True:
    if i - 6**c >= 0:
      dp[i] = min(dp[i],dp[i-6**c]+1)
    else:
      break
    c += 1
  while True:
    if i - 9**d >= 0:
      dp[i] = min(dp[i],dp[i-9**d]+1)
    else:
      break
    d += 1
print(dp[n])

Solution (Python):
from bisect import bisect_right
N = int(input())
unit = [1]
for b in [6,9]:
    u = b
    while u <= N:
        unit.append(u)
        u *= b
unit.sort()
Nu = len(unit)

def dfs(n, i, pk, ans):
    if N - n >= (ans-i)*unit[pk]:
        return ans
    sk = bisect_right(unit, N-n, 0, pk+1) - 1
    for k in range(sk, -1, -1):
        c = n + unit[k]
        if c == N:
            if i + 1 < ans:
                return i + 1
        else:
            t = dfs(c, i+1, k, ans)
            if t < ans:
                ans = t
    return ans

print(dfs(0,0,Nu-1,N))

Solution (Python):
from bisect import bisect_right
N = int(input())
unit = [1]
for b in [6,9]:
    u = b
    while u <= N:
        unit.append(u)
        u *= b
unit.sort()
Nu = len(unit)

ans = N
state_pool = [(0, 0, 0, Nu-1)]
while state_pool:
    n, i, parent, pk = state_pool.pop()
    if N - n >= (ans-i)*unit[pk]:
        continue
    elif pk > 0 and i > 0:
        state_pool.append((parent+unit[pk-1], i, parent, pk-1))

    k = bisect_right(unit, N-n, 0, pk+1) - 1
    c = n + unit[k]
    if c == N:
        if i + 1 < ans:
            ans = i + 1
    else:
        state_pool.append((c, i+1, n, k))
print(ans)

Solution (Python):
from bisect import bisect
n=int(input())
lst=[0,1]
for i in range(1,8):
    lst.append(6**i)
for i in range(1,7):
    lst.append(9**i)
lst.sort()
inf=float("inf")
dp=[[inf]*(n+1) for i in range(15)]
for i in range(15):
    dp[i][0]=0
for i in range(1,15):
    a=lst[i]
    if a>n:
        print(dp[i-1][n])
        break
    for j in range(1,a):
        dp[i][j]=dp[i-1][j]
    for j in range(a,n+1):
        dp[i][j]=min(dp[i-1][j],dp[i-1][j-a]+1,dp[i][j-a]+1)
else:
    print(dp[14][n])

Solution (Python):
a=[1,6,36,216,1296,7776,46656,9,81,729,6561,59049]
n=int(input())
dp=[0]*(n+1)
dp[0]=0
for i in range(1,n+1):
    s=[]
    for j in a:
        if i-j<0:
            continue
        s.append(dp[i-j])
    dp[i]=min(s)+1
print(dp[-1])

Solution (Python):
from bisect import bisect_right
N = int(input())
unit = [1]
for b in [6,9]:
    u = b
    while u <= N:
        unit.append(u)
        u *= b
unit.sort()
Nu = len(unit)

ans = N
state_pool = [(0, 0, Nu-1)]
while state_pool:
    n, i, pk = state_pool.pop()
    if N - n >= (ans-i)*unit[pk]:
        continue
    sk = bisect_right(unit, N-n, 0, pk+1)
    for k in range(sk):
        u = unit[k]
        c = n + u
        if c == N:
            if i + 1 < ans:
                ans = i + 1
        else:
            state_pool.append((c, i+1, k))
print(ans)

Solution (Python):
N = int(input())
memo = [N]*(N+1)
unit = [1]
for b in [6,9]:
    u = b
    while u <= N:
        unit.append(u)
        u *= b
unit.sort()
cur = set({0})
for i in range(1,N+1):
    prev = cur
    cur = set()
    for p in prev:
        for u in unit:
            c = p + u
            if c == N:
                print(i)
                exit()
            elif c > N:
                break
            elif memo[c] > i:
                cur.add(c)
                memo[c] = i

Solution (Python):
a=[1,6,36,216,1296,7776,46656,9,81,729,6561,59049]
n=int(input())
dp=[0]*(n+1)
dp[0]=0
for i in range(1,n+1):
    s=[]
    for j in a:
        if i-j<0:
            continue
        s.append(dp[i-j])
    dp[i]=min(s)+1
print(dp[-1])

Solution (Python):
import sys



def nn(val, count, aal):
	
	if aal[val] >= 0:
		return aal[val]
	
	ll=[1]
	i=1
	while 6**i <= val:
		ll.append(6**i)
		i+=1
	
	i=1
	while 9 ** i <= val:
		ll.append(9**i)
		i+=1
	
	ll=ll[::-1]
	min_v = val
	for l in ll:
		temp = nn(val-l, count+1,aal)
		min_v = min(min_v,temp)
	
	aal[val]=min_v+1
	return min_v+1
	
	
		
def main():
	N = int(input())
	al=[-1]*(N+1)
	al[0:6]=[0,1,2,3,4,5]
	
	ans=nn(N,0,al)

	print(ans)
	
	

isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		
			
	ret = main()
	if ret is not None:
		print(ret)

Solution (Python):
import sys



def nn(val, count, aal):
	
	if aal[val] >= 0:
		return aal[val]
	
	ll=[1]
	i=1
	while 6**i <= val:
		ll.append(6**i)
		i+=1
	
	i=1
	while 9 ** i <= val:
		ll.append(9**i)
		i+=1
	
	ll=ll[::-1]
	min_v = val
	for l in ll:
		temp = nn(val-l, count+1,aal)
		min_v = min(min_v,temp)
	
	aal[val]=min_v+1
	return min_v+1
	
	
		
def main():
	N = int(input())
	al=[-1]*(N+1)
	al[0:6]=[0,1,2,3,4,5]
	
	ans=nn(N,0,al)

	print(ans)
	
	

isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		
			
	ret = main()
	if ret is not None:
		print(ret)

Solution (Python):


N=int(input())

def saiki(tgt,i,count,ans):
    

    if i==0 or tgt==0:
        ans=min((tgt+count),ans)
        return ans
        
    num=tgt//temp[i]
    while num>=0:
        ans=saiki(tgt-num*temp[i],i-1,count+num,ans)
        if ans<(count+num):
            return ans
        num-=1
    return ans

temp=[1]
n=1
while N>=6**n:
    temp.append(6**n)
    n+=1
    
n=1
while N>=9**n:
    temp.append(9**n)
    n+=1

temp.sort()


print(saiki(N,len(temp)-1,0,10**9))

Solution (Python):
import math
n = int(input())
six_ls = []
nine_ls = []
def nine_plus(base):
    "base : list of int"
    kuriagari = 1
    for num in range(len(base) - 1, -1, -1):
        if base[num] + kuriagari >= 9:
            base[num] = 0
            continue
        else:
            base[num] += kuriagari
            break
    return base

def six_plus(base):
    "base : list of int"
    kuriagari = 1
    for num in range(len(base) - 1, -1, -1):
        if base[num] + kuriagari >= 6:
            base[num] = 0
            continue
        else:
            base[num] += kuriagari
            break
    return base

six_sinsu = [0 for i in range(math.floor(math.log(n, 6)) + 2)]
nine_sinsu = [0 for i in range(math.floor(math.log(n, 9)) + 2)]

for i in range(n+1):
    six_ls.append(sum(six_sinsu))
    nine_ls.append(sum(nine_sinsu))
    six_sinsu = six_plus(six_sinsu)
    nine_sinsu = nine_plus(nine_sinsu)
hoge = [a + b for a, b in zip(six_ls, nine_ls[::-1])]
print(min(hoge))

Solution (Python):
n = int(input())

ans=n
for i in range(n+1):
  c = 0
  t = i
  while t>0:
    c += t%6
    t = t//6

  s = n-i
  while s>0:
    c += s%9
    s = s//9
  ans = min(ans,c)
  
print(ans)

Solution (Python):
import math

N = int(input())
s = [6 ** i for i in range (0,7)]
q = [9 ** j for j in range (0,6)]
m = {}

def f(x):
  if x <= 5:
    return x
  elif x in m:
    return m[x]
  else:
    m_s = max(i for i in s if i <= x)
    m_q = max(j for j in q if j <= x)
    ms = x - m_s
    mq = x - m_q
    m[x] = min(f(ms)+1,f(mq)+1)
    return m[x]
print(f(N))

Solution (Python):
import sys


def slove():
    input = sys.stdin.readline
    n = int(input().rstrip('\n'))
    six_l = []
    for i in range(1, 7):
        six_l.append(pow(6, i))
    nine_l = []
    for i in range(1, 6):
        nine_l.append(pow(9, i))

    m_cnt = 10 ** 10
    for i in range(n // 6 + 1):
        t = n
        six = i
        t -= (6 * six)
        nine = t // 9
        t -= (nine * 9)
        cnt = t
        for j in range(len(six_l)):
            if six // six_l[-j-1] > 0:
                cnt += (six // six_l[-j-1])
                six %= six_l[-j-1]
        cnt += six
        for j in range(len(nine_l)):
            if nine // nine_l[-j-1] > 0:
                cnt += (nine // nine_l[-j-1])
                nine %= nine_l[-j-1]
        cnt += nine
        m_cnt = min(m_cnt, cnt)
    print(m_cnt)


if __name__ == '__main__':
    slove()

Solution (Python):
N=int(input())
ans=N
for i in range(N+1): 
    cnt=0
    t=i
    while t>0:
        cnt+=t%6
        t//=6
    s=N-i
    while s>0:
        cnt+=s%9
        s//=9
    ans=min(ans,cnt)
print(ans)

Solution (Python):
N = int(input())


sixs = []
t = 1
while t <= N:
    sixs.append(t)
    t *= 6

nines = []
t = 1
while t <= N:
    nines.append(t)
    t *= 9


ans = N


for i in range(N+1):
    cnt = 0
    a = i
    b = N - i
    for num in list(reversed(sixs)):
        
        if a == 0:
            break
        elif a <= 5:
            cnt += a
            a = 0
        else:
            if a >= num:
                
                tmp = a // num
                cnt += tmp
                a -=  num * tmp
                
            else:
                continue
    
    for num in list(reversed(nines)):
        
        if b == 0:
            break
        elif b <= 8:
            cnt += b
            b = 0
        else:
            if b >= num:
                tmp = b // num
                cnt += tmp
                b -=  num * tmp
            else:
                continue


    ans = min(ans, cnt)

print(ans)

Solution (Python):
N = int(input())


dp = []
for i in range(100010):
    dp.append(100000)

dp[0] = 0

for n in range(1, 100000 + 1):
    power = 1  
    while power <= n:
        dp[n] = min(dp[n], dp[n-power]+1)
        power *= 6

    power = 1  
    while power <= n:
        dp[n] = min(dp[n], dp[n-power]+1)
        power *= 9

print(dp[N])

Solution (Python):
import sys

sys.setrecursionlimit(2000000)

def re(r,k,l):
    if k==0:return r
    while(k<l[0]):
        l=l[1:]
    return re(r+1,k-l[0],l)





n=int(input())
i=1
l6=[]
ans=10**5
while(i<=n):
    l6.append(i)
    i*=6
i=1
l9=[]
while(i<=n):
    l9.append(i)
    i*=9
l6.sort(reverse=True)
l9.sort(reverse=True)
for i in range(n+1):
    ans=min(ans,re(0,n-i,l6)+re(0,i,l9))
print(ans)

Solution (Python):
inf = float('inf')

N = int(input())

dp = [inf] * (N+1)
dp[0] = 0

for i in range(N):
    if i+1 < N+1:
        dp[i+1] = min(dp[i+1], dp[i] + 1)
    j = 6
    while i+j < N+1:
        dp[i+j] = min(dp[i+j], dp[i] + 1)
        j *= 6
    j = 9
    while i+j < N+1:
        dp[i+j] = min(dp[i+j], dp[i] + 1)
        j *= 9
    
ans = dp[N]
print(ans)

Solution (Python):
n=int(input())
dp=[0]*(n+1)
i=1
while i <= n:
    dp[i]=float('inf')
    p=1
    while p<=i:
        dp[i]=min(dp[i],1+dp[i-p])
        p*=6
    p=1
    while p<=i:
        dp[i]=min(dp[i],1+dp[i-p])
        p*=9
    i+=1
print(dp[n])

Solution (Python):
N = int(input())
rec = [0] * (N+1)
for i in range(1,N+1):
    rec[i] = rec[i-1] + 1
    for b in [6,9]:
        u = b
        while u <= i:
            rec[i] = min(rec[i], rec[i-u]+1)
            u *= b
print(rec[N])

Solution (Python):
n = int(input())
dp = [float("Inf")]*(n+1)
for i in range(n+1):
    if i < 6:dp[i] = i
    power = 1
    while i >= 6 ** power:
        if dp[i] > dp[i-6**power]+1:dp[i] = dp[i-6**power] + 1
        power += 1
    power = 1
    while i >= 9 ** power:
        if dp[i] > dp[i-9**power]+1:dp[i] = dp[i-9**power] + 1
        power += 1
print(int(dp[n]))

Solution (Python):
n = int(input())
dp = [float("Inf")]*(n+1)
for i in range(n+1):
    if i < 6:dp[i] = i
    power = 1
    while i >= 6 ** power:
        if dp[i] > dp[i-6**power]+1:dp[i] = dp[i-6**power] + 1
        power += 1
    power = 1
    while i >= 9 ** power:
        if dp[i] > dp[i-9**power]+1:dp[i] = dp[i-9**power] + 1
        power += 1
print(int(dp[n]))

Solution (Python):
n = int(input())
dp = [float("Inf")]*(n+1)
for i in range(n+1):
    if i < 6:dp[i] = i
    power = 1
    while i >= 6 ** power:
        dp[i] = min(dp[i],dp[i-6**power]+1)
        power += 1
    power = 1
    while i >= 9 ** power:
        dp[i] = min(dp[i],dp[i-9**power]+1)
        power += 1
print(dp[n])

Solution (Python):
n=int(input())
dp=[10**10]*(n+1)
dp[0]=0
for i in range(1,n+1):
  dp[i]=dp[i-1]+1
  x=0
  while 9**(x+1)<=i:
    x+=1
  dp[i]=min(dp[i],dp[i-9**x]+1)
  x=0
  while 6**(x+1)<=i:
    x+=1
  dp[i]=min(dp[i],dp[i-6**x]+1)
print(dp[n])

Solution (Python):
'''dp[N] : N円の答え

dp[N] = min(dp[N-1] + 1,
dp[N-6] + 1, dp[N-6^2] + 1,
dp[N-9] + 1, dp[N-9^2] + 1)
'''

N = int(input())

dp = []
for j in range(100000 + 10):
    dp.append(j)

for i in range(100000 + 9):
    s = 6
    n = 9
    while i-s>=0:
        try:

        
            dp[i] = min(dp[i], dp[i-s] + 1)
            s *= 6
        except:
            print('s', i, i-s, s)
    while i-n>=0:
        dp[i] = min(dp[i], dp[i-n] + 1) 
        n *= 9

print(dp[N])

Solution (Python):
n = int(input())
six = [1]
nine = [1]
p =1 
while True:
    if 6**p<=n:
        six.append(6**p)
    else:
        break
    if 9**p <=n:
        nine.append(9**p)
    p +=1
six.sort(reverse=True)
nine.sort(reverse=True)
ans = float('inf')
for i in range(n+1):
    count =0
    r = i
    for a in six:
        quot = r//a
        r -= quot*a
        count += quot
        if r ==0:
            break
    r = n - i
    for a in nine:
        quot = r//a
        r -= quot*a
        count += quot
        if r ==0:
            break
    ans = min(ans,count)
print(ans)

Solution (Python):
N = int(input())




square_6_list = []
x = 1
while 6**x <= 10**5:
    square_6_list.append(6**x)
    x += 1

square_9_list = []
x = 1
while 9**x <= 10**5:
    square_9_list.append(9**x)
    x += 1

min_withdrow = [float("inf")]*(N+1)
min_withdrow[0] = 0
min_withdrow[1] = 1

for i in range(2, len(min_withdrow)):
    tmp_list = []
    for x in [1, 2, 3, 4, 5]:
        if i-x >= 0:
            tmp_list.append(min_withdrow[i-x] + x)
        else:
            break
    for x in square_6_list:
        if i-x >= 0:
            tmp_list.append(min_withdrow[i-x] + 1)
        else:
            break
    for x in square_9_list:
        if i-x >= 0:
            tmp_list.append(min_withdrow[i-x] + 1)
        else:
            break
    min_withdrow[i] = min(tmp_list)

print(min_withdrow[-1])

Solution (Python):
def run():
  N = int(input())
  dp = [0] * (N+1)
  dp[1] = 1
  for n in range(1, N+1):
    if n == 1: continue
    dp[n] = dp[n-1]+1
    draw_money = 6
    while True:
      if n < draw_money: break
      dp[n] = min(dp[n], dp[n-draw_money]+1)
      draw_money *= 6
    draw_money = 9
    while True:
      if n < draw_money: break
      dp[n] = min(dp[n], dp[n-draw_money]+1)
      draw_money *= 9
  print(dp[N])
  
if __name__ == '__main__':
  run()

Solution (Python):
n=int(input())
dp=[float('inf')]*(n+1)
dp[1]=1
i=0
while 9**i<=n:
    dp[9**i]=1
    i+=1
j=0
while 6**j<=n:
    dp[6**j]=1
    j+=1
for i in range(2,n+1):
    for j in range(1,8):
        if i-6**j>=1 and i-9**j>=1:
            dp[i]=min(dp[i],min(dp[i-1],dp[i-6**j],dp[i-9**j])+1)
        elif i-6**j>=1:
            dp[i]=min(dp[i],min(dp[i-1],dp[i-6**j])+1)
        else:
            dp[i]=min(dp[i],dp[i-1]+1)
print(dp[n])

Solution (Python):
import sys
imput=sys.stdin.readline
n=int(input())
dp=[float('inf')]*(n+1)
dp[1]=1
i=0
while 9**i<=n:
    dp[9**i]=1
    i+=1
j=0
while 6**j<=n:
    dp[6**j]=1
    j+=1

for i in range(2,n+1):
    for j in range(1,8):
        if i-6**j>=1 and i-9**j>=1:
            dp[i]=min(dp[i],min(dp[i-1],dp[i-6**j],dp[i-9**j])+1)
        elif i-6**j>=1:
            dp[i]=min(dp[i],min(dp[i-1],dp[i-6**j])+1)
        else:
            dp[i]=min(dp[i],dp[i-1]+1)


print(dp[n])

Solution (Python):
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)

def main():
    n = int(input().strip())
    dp = [0] * (n+1)
    
    for i in range(1, n+1):
        dp[i] = 10**10

    for b in (6, 9):
        p = 0
        while b**p <= n:
            for i in range(n+1):
                if b**p <= i:
                    dp[i] = min(dp[i], dp[i-b**p]+1)
            p += 1
    print(dp[n])
if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)

def main():
    n = int(input().strip())
    dp = [[0] * (n+1) for _ in range(15)]
    coins = [0] + [6**i for i in range(8)] + [9 ** i for i in range(1, 7)]
    for i in range(1, n+1):
        dp[0][i] = 10**10
    for i in range(1, 15):
        for j in range(n+1):
            if j - coins[i] < 0:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = min(dp[i-1][j], dp[i][j-coins[i]] + 1)
    print(dp[14][n])
if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())

inf = 1000000000
DP = [inf for _ in range(1000000)]
DP[0] = 0

for i in range(N):
    DP[i+1] = min(DP[i+1],DP[i]+1)
    j = 1
    while 6**j < 100000:
        DP[i+6**j] = min(DP[i+6**j],DP[i]+1)
        j += 1
    j = 1
    while 9**j < 100000:
        DP[i+9**j] = min(DP[i+9**j],DP[i]+1)
        j += 1
print(DP[N])

Solution (Python):
import sys
input = sys.stdin.readline

def main():
    N = int(input())
    ans = N
    for i in range(N+1):
        count = 0
        tmp = i
        while tmp > 0:
            count += tmp % 6
            tmp //= 6
        tmp = N - i
        while tmp > 0:
            count += tmp % 9
            tmp //= 9
        ans = min(ans, count)
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
n = int(input())
mn = 10**6
for m9 in range(n+1):
    cnt = 0
    m6 = n-m9
    while m9>0:
        i = 0
        while m9>=9**i:
            if 9**(i+1)<=m9:
                i+=1
            else:
                r = m9//(9**i)
                m9 -= r*(9**i)
                cnt += r
                i = 0
    while m6>0:
        i = 0
        while m6>=6**i:
            if 6**(i+1)<=m6:
                i+=1
            else:
                r = m6//6**i
                m6 -= r*6**i
                cnt += r
                i = 0
    if cnt < mn:
        mn = cnt

print(mn)

Solution (Python):
N = int(input())
dp = list(range(N+1))

i = 6
while i <= N:
    for j in range(i, N+1):
        dp[j] = min(dp[j], 1+dp[j-i])
    i = i*6
i = 9
while i <= N:
    for j in range(i, N+1):
        dp[j] = min(dp[j], 1+dp[j-i])
    i = i*9
print(dp[N])

Solution (Python):
N = int(input())
dp=list(range(N+1))

i = 6
while i <= N:
    for j in range(i,N+1):
        dp[j] = min(dp[j],1+dp[j-i])
    i = i*6
i = 9
while i <= N:
    for j in range(i,N+1):
        dp[j] = min(dp[j],1+dp[j-i])
    i = i*9

print(dp[N])

Solution (Python):
N = int(input())
ans = N
    
for i in range(N+1):
  t = i
  cc = 0
  while t > 0:
    cc += t % 6
    t = t // 6
  t = N - i
  while t > 0:
    cc += t % 9
    t = t // 9
    
  ans = min(cc,ans)

print(ans)

Solution (Python):
n = int(input())

dp = [0] * (n + 1)

for i in range(1, n + 1):
    dp[i] = dp[i - 1] + 1
    power = 6
    while power <= i:
        dp[i] = min(dp[i], dp[i - power] + 1)
        power *= 6
    power = 9
    while power <= i:
        dp[i] = min(dp[i], dp[i - power] + 1)
        power *= 9

print(dp[n])

Solution (Python):
max_n = 100000

N = int(input())

dp = [N for _ in range(N+1)]
dp[0] = 0
for n in range(1, N+1):
    for pow6 in range(n+1):
        if 6 ** pow6 <= n:
            dp[n] = min(dp[n], dp[n - 6 ** pow6] + 1)
        else:
            break

    for pow9 in range(n+1):
        if 9 ** pow9 <= n:
            dp[n] = min(dp[n], dp[n - 9 ** pow9] + 1)
        else:
            break
print(dp[N])

Solution (Python):
n=int(input())
ans=[0]*(n+1)
for i in range(1,n+1):
    ans[i] = ans[i-1]+1
    m6 = 6
    m9 = 9
    while i>=m6:
        ans[i] = min(ans[i],ans[i-m6]+1)
        m6 *= 6
    while i>=m9:
        ans[i] = min(ans[i],ans[i-m9]+1)
        m9 *= 9
print(ans[-1])

Solution (Python):

max_n = 110000

N = int(input())

dp = [N for i in range(max_n)]
dp[0] = 0
for n in range(1, N+1):
    for pow6 in range(n+1):
        if 6 ** pow6 <= n:
            dp[n] = min(dp[n], dp[n - 6 ** pow6] + 1)
        else:
            break

    for pow9 in range(n+1):
        if 9 ** pow9 <= n:
            dp[n] = min(dp[n], dp[n - 9 ** pow9] + 1)
        else:
            break


print(dp[N])

Solution (Python):
N = int(input())

def f(n):
    L = [1]
    c = 1
    while 6**c <= n:
        L.append(6**c)
        c += 1
    c = 1
    while 9**c <= n:
        L.append(9**c)
        c += 1
    return L

dp = [0 for i in range(N+1)]
dp[1] = 1

for i in range(N):
    L = f(i+1)
    temp = dp[i+1-L[0]]
    for j in range(len(L)):
        if temp > dp[i+1-L[j]]:
            temp = dp[i+1-L[j]]
    dp[i+1] = temp+1
    
print(dp[N])

Solution (Python):
import sys
sys.setrecursionlimit(10**5)

N = int(input())

def rec(N, m) :
    if N < 6 :
        return N + m
    
    
    a, b = float('inf'), float('inf')
    six = 6
    while six * 6 <= N :
        six *= 6
    if N >= six :
        a = rec(N - six, m + 1)
    
    nine = 9
    while nine * 9 <= N :
        nine *= 9
    if N >= nine :
        b = rec(N - nine, m + 1)
    
    return min(a, b)
        
print(rec(N, 0))

Solution (Python):
N = int(input())
A = [1]
for k in range(1,7):
    A.append(6**k)
for k in range(1,6):
    A.append(9**k)
dp = [[0 for _ in range(len(A))] for _ in range(N+1)]
for i in range(N+1):
    dp[i][0] = i
for j in range(len(A)):
    dp[1][j] = 1
for i in range(2,N+1):
    for j in range(1,len(A)):
        if i>=A[j]:
            dp[i][j] = min(dp[i][j-1],dp[i-A[j]][j]+1)
        else:
            dp[i][j] = dp[i][j-1]
print(dp[N][len(A)-1])

Solution (Python):
n=int(input());print(min(sum(i//9**j%9+(n-i)//6**j%6for j in range(7))for i in range(n+1)))

Solution (Python):
N = int(input())
inf = float('inf')
dp = [inf] * (N+1)
dp[0] = 0


c = [1]
t = 6
while t <= N:
    c.append(t)
    t *= 6
t = 9
while t <= N:
    c.append(t)
    t *= 9
    
def chmin(a, b):                            
    if a > b:
        return b
    else:
        return a

for i in range(1, N+1):                     
    for t in c:                             
        dp[i] = chmin(dp[i], dp[i-t]+1)     
            
print(dp[N])

Solution (Python):
s=input()
a=int(s)
list=[]
list.append(1)
list.append(6)
list.append(9)
list.append(36)
list.append(81)
list.append(216)
list.append(729)
list.append(1296)
list.append(6561)
list.append(7776)
list.append(59049)
list.append(46656)
pp=[]
def money(x,y):
  for i in range(12):
    b=x//list[i]
    if b==0:
      continue
    if i%2==1:
      if 0<b<6:
        if x%list[i]==0:
          pp.append(y+b)
        else:
          if y>20:
            break
          money(x-list[i],y+1)
    elif i%2==0:
      if i!=0:
        if 0<b<9:
          if x%list[i]==0:
            pp.append(y+b)
          else:
            if y>20:
              break
            money(x-list[i],y+1)
      else:
        if 0<b<6:
          pp.append(y+b)
money(a,0)
print(min(pp))

Solution (Python):
N=int(input())
ans=N
for i in range(N+1):
    cnt=0
    t=i
    while t>0:
        cnt+=t%6
        t//=6
    j=N-i
    while j>0:
        cnt+=j%9
        j//=9
    ans = min(ans,cnt)
print(ans)