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_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from math import ceil, floor
from sys import setrecursionlimit

import heapq
import itertools
import operator


inf = float('inf')



N = 0


def set_inputs():
    global N
    N = get_int()
    return


def main():
    setrecursionlimit(100000)
    set_inputs()
    
    dp = [0] * (N + 1)
    ops = [
        1,
        6 ** 1, 6 ** 2, 6 ** 3, 6 ** 4, 6 ** 5, 6 ** 6,
        9 ** 1, 9 ** 2, 9 ** 3, 9 ** 4, 9 ** 5
    ]
    for i in range(1, N + 1):
        dp[i] = min(dp[i-j] for j in ops if i - j >= 0) + 1
    print(dp[N])
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


def get_str():
    return input().strip()


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def get_data(n, types):
    if len(types) == 1:
        return [types[0](input()) for _ in range(n)]
    return zip(*(
        [t(x) for t, x in zip(types, input().split())]
        for _ in range(n)
    ))


if __name__ == '__main__':
    main()

Solution (Python):
possible=[1,6,9,6**2,6**3,6**4,6**5,6**6,9**2,9**3,9**4,9**5]
dp=[10**18]*(10**5+1)
dp[0]=0
n=int(input())
for i in range(1,n+1):
  for j in possible:
    if i-j>=0:
      dp[i]=min(dp[i],1+dp[i-j])
print(dp[n])

Solution (Python):
n=int(input())
ls=[1]

for i in range(1,7):
  ls.append(6**i)
  ls.append(9**i)
dp = [float('inf') for i in range(n+2)]
dp[0] = 0


for i in range(1,n+1):
  for j in ls:
    if i-j>=0:
      dp[i] = min(dp[i-1]+1, dp[i-j]+1,dp[i])
    else:
      dp[i] = min(dp[i-1]+1,dp[i])
print(dp[n])

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

ls=set([1])
i=1
while 6**i<=100000:
  ls.add(6**i)
  i+=1
i=1
while 9**i<=100000:
  ls.add(9**i)
  i+=1

dp = [float("inf") for i in range(n+2)]
dp[0] = 0
ls=list(ls)

for i in range(n+2):
  
  for j in range(len(ls)):
    if i+ls[j]<=n:
      dp[i+ls[j]] = min(dp[i]+1, dp[i+ls[j]-1]+1,dp[i+ls[j]])
print(dp[n])

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

ls=set([1])
i=1
while 6**i<=100000:
  ls.add(6**i)
  i+=1
i=1
while 9**i<=100000:
  ls.add(9**i)
  i+=1

dp = [float("inf") for i in range(n+2)]
dp[0] = 0


for i in range(n+1):
  
  for j in ls:
    if i + j <= n:
      dp[i+j] = min(dp[i+j], dp[i]+1)
print(dp[n])

Solution (Python):
n = int(input())
coins = [1]
t = 6 
while t <= n:
    coins.append(t)
    t *= 6

t = 9
while t <= n:
    coins.append(t)
    t *= 9

coins.sort()

dp = [ float("inf") for _ in range(n+10) ]
dp[0] = 0

for i in range(n+1):
    for c in coins:
        if i + c > n:
            continue
        dp[i+c] = min(dp[i+c], dp[i]+1)

print(dp[n])

Solution (Python):
N= int(input())
_l = [1, 6, 6**2, 6**3, 6**4, 6**5, 6**6, 6**7, 9, 9**2, 9**3, 9**4, 9**5, 9**6]
_l.sort()


answer=[0]*(N+1)

for i in range(1, N+1):
  answer[i] = min([answer[i-l] +1 if i-l>=0 else 1000000 for l in _l])

print(answer[N])

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

Solution (Python):
n = int(input())
dp = [float("inf")]*(n+1)
dp[0] = 0
for i in range(n):
	j = 0
	while i+6**j <= n:
		dp[i+6**j] = min(dp[i+6**j],dp[i]+1)
		j += 1
	k = 0
	while i+9**k <= n:
		dp[i+9**k] = min(dp[i+9**k],dp[i]+1)
		k += 1
print(dp[n])

Solution (Python):
import sys
sys.setrecursionlimit(1000000)

n = int(input())

get = []
for i in range(10):
  npow6 = 6**(i+1)
  npow9 = 9**(i+1)
  if npow6 <= 100000:
    get.append(npow6)
  if npow9 <= 100000:
    get.append(npow9)
  
get = sorted(get)

memo = [-1] * 110000
for i in range(6):
  memo[i] = i
  
def dfs(money):
  if memo[money] != -1:
    return memo[money]
  ret = 110000
  for g in get:
    if g > money:
      continue
    ret0 = dfs(money-g) + 1
    ret = min(ret, ret0)
  memo[money] = ret
  return ret

print(dfs(n))

Solution (Python):
def solve(n):
 dp = [9999999]*100005
 dp[0] = 0
 for i in range(1,n+1):
  dp[i] = min(dp[i],dp[i-1]+1)
  tmp = 6
  
  while (i-tmp >= 0):
    dp[i] = min(dp[i],dp[i-tmp]+1)
    tmp *= 6
  tmp2 = 9
  while (i-tmp2 >= 0):
    dp[i] = min(dp[i],dp[i-tmp2]+1)
    tmp2 *= 9
 print(dp[n])

n = int(input())
solve(n)

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

ans = N
for i in range(N+1):
    cc = 0
    t = i
    while t > 0:
        cc += t%6
        t //= 6
    t = N-i
    while t > 0:
        cc += t%9
        t //= 9
    if ans > cc: ans = cc
print(ans)

Solution (Python):
def main():
    x = int(input())
    dp = [0 for _ in range(x+1)]

    for i in range(1,x+1):

        dp[i] = 1 + dp[i-1]

        sup = 0
        while 1:
            if i - 6**sup < 0:
                break
            tmp = 1 + dp[i-6**sup]
            dp[i] = min(dp[i],tmp)
            sup += 1

        sup = 0
        while 1:
            if i - 9**sup < 0:
                break
            tmp = 1 + dp[i-9**sup]
            dp[i] = min(dp[i],tmp)
            sup += 1

    print(dp[x])

if __name__ == "__main__":
    main()

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

dp = [0] * (n + 1)

for i in range(1, n + 1):
    dp_min = dp[i - 1]
    p = 6
    q = 9
    while p <= i:
        if dp[i - p] < dp_min:
            dp_min = dp[i - p]
        p *= 6
    while q <= i:
        if dp[i - q] < dp_min:
            dp_min = dp[i - q]
        q *= 9
    dp[i] = dp_min + 1
        
print(dp[n])

Solution (Python):


def solve():
	N = int(input())
	INF = 100000

	
	dp = [INF] * (N+10)
	dp[0] = 0
	for n in range(1, N+1):
		
		dp[n] = min(dp[n], dp[n-1]+1)

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



if __name__ == "__main__":
	solve()

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

def ans(x):
    dp = [i for i in range(x+1)]
    yenlist = [6,9]
    for i in yenlist:
        k = 1
        while i**k <= x:
            q = i**k
            for j in range(x+1-q):
                dp[j+q] = min(dp[j]+1,dp[j+q]) 
            k += 1
    return dp[x]

answer = ans(n)
print(answer)

Solution (Python):
N = int(input())
dp = [0 for i in range(N+1)]
dp[1] = 1
roku = 0
kyu = 0
for i in range(2, N+1):
    if i == 6**(roku+1):
        roku += 1
    if i == 9**(kyu+1):
        kyu += 1
    kouho = [1]
    for j in range(roku):
        kouho.append(6**(j+1))
    for j in range(kyu):
        kouho.append(9**(j+1))
    size = len(kouho)

    small = 1000000
    for j in range(size):
        if dp[i - kouho[j]] + 1 < small:
            small = dp[i - kouho[j]] + 1
    dp[i] = small
print(str(dp[N]))

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

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

lst = []
for i in range(7):
    lst.append(6**i)
for i in range(1, 6):
    lst.append(9**i)

dp = [0]*100001
for i in range(1, n+1):
    candi = []
    for j in lst:
        if i >= j:
            candi.append(dp[i-j]+1)
    dp[i] = min(candi)
print(dp[i])

Solution (Python):
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

"""
N = 6**i + 9**j
とする。

"""

N = I()

smalls = []
bigs = []
for i in range(10**5):
    small = 6**i
    big = 9**i

    if small <= N:
        smalls.append(small)
    if big <= N:
        bigs.append(big)
    if small > N:
        break

smalls = sorted(smalls, reverse=True)
bigs = sorted(bigs, reverse=True)


result = 10**13
for i in range(0, N+1):
    
    
    small_n = i
    big_n = N - i

    small_idx = 0
    big_idx = 0

    small_count, big_count = 0, 0
    while small_n != 0:
        if smalls[small_idx] > small_n:
            small_idx += 1
            continue
        small_n -= smalls[small_idx]
        small_count += 1

    while big_n != 0:
        if bigs[big_idx] > big_n:
            big_idx += 1
            continue
        big_n -= bigs[big_idx]
        big_count += 1
    
    result = min(result, small_count+big_count)

print(result)

Solution (Python):
a=int(input())
dp=[float('inf') for i in range(100000+10)]
dp[0]=0
for i in range(1,100000+1):
    dp[i]=dp[i-1]+1
    for k in [6,9]:
        for j in range(1,7):
            if k**j <=i :
                dp[i]=min(dp[i],dp[i-k**j]+1)
print(dp[a])

Solution (Python):
import math

def A():
    x, a, b = [int(x) for x in input().split()]
    if abs(x-a) < abs(x-b):
        print('A')
    else:
        print('B')
def B():
    S = input()
    alphabet = [False for x in range(26)]
    for char in S:
        i = ord(char) - ord('a')
        alphabet[i] = True
    printed = False
    for i in range(len(alphabet)):
        if alphabet[i] == False:
            print(chr(ord('a')+i))
            printed = True
            break
    if printed == False:
        print("None")
def C():
    num = sorted([1] + [pow(6, x+1) for x in range(6)] + [pow(9, x+1) for x in range(5)])
    n = int(input())
    stack = [(n, 0)]
    memo = {}
    _min = 999999

    cost = {}

    while len(stack) > 0:
        node = stack.pop()
        for k in num:
            if node[0] >= k:
                ans = (node[0] - k, node[1] + 1)
                if ans[0] == 0:
                    _min = min(_min, ans[1])
                else:
                    if str(ans[0]) in memo and memo[str(ans[0])] <= ans[1]:
                        pass
                    else:
                        stack.append(ans)
                        memo[str(ans[0])] = ans[1]
    print(_min)

def E():
    n, m = [int(x) for x in input().split()]
    P = [[] for i in range(n)]
    for j in range(m):
        p, y = [int(x) for x in input().split()]
        P[p-1].append([y, ('000000'+str(p))[-6:], j])

    for i in range(n):
        P[i] = sorted(P[i], key=lambda x:x[0])
        for j in range(len(P[i])):
            P[i][j][1] += (('000000'+str(j+1))[-6:])
    P = [e for inner_list in P for e in inner_list]
    P = sorted(P, key=lambda x:x[2])
    for p in P:
        print(p[1])
C()

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")


def A():
    return


def B():
    return


def C():
    n = II()
    dp = [inf for i in range(n + 1)]
    ans = [1]
    x = 6
    while x <= n:
        ans.append(x)
        x = x * 6
    x = 9
    while x <= n:
        ans.append(x)
        x = x * 9
    ans.sort()
    for i in ans:
        dp[i] = 1
    for i in range(1, n + 1):
        if not i in ans:
            a = bisect.bisect_left(ans, i)
            for k in range(a):
                
                dp[i] = min(dp[i - ans[k]] + 1, dp[i])
    print(dp[n])

    return


def D():
    return


def E():
    return


def F():
    return


def G():
    return


def H():
    return


if __name__ == '__main__':
    C()

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007


def A():
    return


def B():
    return


def C():
    n = I()
    ans = float("inf")
    for i in range(n+1):
        m = 0
        k = i
        while k > 0:
            m += k%6
            k //= 6
        k = n-i
        while k > 0:
            m += k%9
            k //= 9
        ans = min(ans,m)
    print(ans)

def D():
    return


def E():
    return


def F():
    return


def G():
    return


def H():
    return


if __name__ == "__main__":
    C()

Solution (Python):

N = int(input())
dp = {}
for n in range(N+1):
    if n == 0:
        dp[0] = 0
    else:
        res = n
        pow6 = 1
        while n - pow6 >= 0:
            res = min(res, dp[n-pow6] +1)
            pow6 *= 6
        pow9 = 1
        while n -pow9 >= 0:
            res = min(res, dp[n-pow9] +1)
            pow9 *= 9
        dp[n] = res
print(dp[N])

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

def memorize(f):
    table = {}
    def func(*args):
        if not args in table:
            table[args] = f(*args)
        return table[args]
    return func

@memorize
def memDFS(n):
    if n==0:
        return 0
    else:
        res = n
        pow6 = 1
        while(pow6<=n):
            res = min(res, memDFS(n-pow6)+1)
            pow6 *= 6
        pow9 = 1
        while(pow9<=n):
            res = min(res, memDFS(n-pow9)+1)
            pow9 *= 9
        return res

N = int(input())
print(memDFS(N))

Solution (Python):
n=int(input())
dp=[i for i in range(n+1)]
lw=[6,9]
for w in lw:
    k=1
    while w**k<=n:
        q=w**k
        for j in range(n+1-q):
            dp[j+q]=min(dp[j]+1,dp[j+q])
        k+=1
print(dp[n])

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

for i in range(1, N+1):
    pow6 = []
    pow9 = []
    for j in range(i):
        if 6**j > i:
            break
        pow6.append(6**j)
    for k in range(i):
        if 9**k > i:
            break
        pow9.append(9**k)
    L = set(pow6 + pow9)
    
    for l in L:
        if i-l < 0:
            break
        dp[i] = min(dp[i], dp[i-l]+1)

print(dp[N])

Solution (Python):
import sys
sys.setrecursionlimit(100000)

def rec(n):
    if n == 0:
        memo[n] = 0
        return memo[n]
    if memo[n] != -1:
        return memo[n]
    res = n
    pow6 = []
    pow9 = []
    for i in range(n):
        if 6 ** i > n:
            break
        pow6.append(6 ** i)
    
    for j in range(1, n):
        if 9 ** j > n:
            break
        pow9.append(9 ** j)
    L = set(pow6 + pow9)
    
    for k in L:
        res = min(res, rec(n - k)+1)
        
    memo[n] = res
    return memo[n]
    

N = int(input())
memo = [-1] * (N+1)
print(rec(N))

Solution (Python):
def read():
    return raw_input()


def write(message):
    import sys
    print message
    sys.stdout.flush()


if __name__ == '__main__':
    n = int(read())

    allowed = [1, ]
    spow = 6
    while spow <= n:
        allowed.append(spow)
        spow *= 6
    npow = 9
    while npow <= n:
        allowed.append(npow)
        npow *= 9

    allowed = allowed[::-1]
    res = {a: 1 for a in allowed}

    def min_ops(N):
        global res
        global allowed
        if N in res:
            return res[N]

        for a in allowed:
            if N - a > 0:
                if N not in res or min_ops(N-a) + 1 < res[N]:
                    res[N] = min_ops(N-a) + 1
        return res[N]

    write(min_ops(n))

Solution (Python):
N = int(input())
MAX_N = 100000
dp = [MAX_N for _ in range(N + 1)]


dp[0] = 0
for num in [6, 9]:
    for i in range(N):
        if dp[i] == MAX_N:
            continue
        for j in range(1, 7): 
            idx = i + pow(num, j)
            if idx > N:
                break
            dp[idx] = min(dp[idx], dp[i] + 1)


min_cost = MAX_N
min_idx = max(-1, N - 1000) 
for i in range(N, min_idx, -1):
    if dp[i] < MAX_N:
        remain = N - i
        cost = remain + dp[i]
        if min_cost > cost:
            min_cost = cost
print(min_cost)

Solution (Python):
N = int(input())
sixes = [6 ** i for i in range(1, 7)]
nines = [9 ** i for i in range(1, 6)]
coin = [1] + sixes + nines
INF = 10**6
dp = [INF] * 100010
dp[0] = 0  
for money in range(1, N + 1):
    dp[money] = min([dp[money-i] + 1 for i in coin if i <= money])
print(dp[N])

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


sixes = [6 ** i for i in range(1, 7)]
nines = [9 ** i for i in range(1, 6)]
coin = [1] + sixes + nines
INF = 10**6
dp = [INF] * 100010
dp[0] = 0  
for money in range(1, N + 1):
    dp_candidate = []
    for coin_ in coin:
        if money < coin_:
            continue
        else:
            dp_candidate.append(dp[money-coin_] + 1)
    dp[money] = min(dp_candidate)
print(dp[N])

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

coins = [9**5,6**6,6**5,9**4,6**4,9**3,6**3,9**2,6**2,9,6,1]

res = n

dp = [-1]*(n+1)
dp[0] = 0
min_coins = [-1]*(n+1)
for i in range(1,n+1):
    min_c = n+1 
    c = 0
    for coin in coins:
        if coin <= i:
            
            if dp[i-coin] != -1 and 1 + dp[i-coin]<min_c:
                min_c = 1+dp[i-coin]
                c = coin
    if min_c == n+1:
        dp[i] = -1
    else:
        dp[i] = min_c
        min_coins[i] = c
print(dp[n])
'''
money = n
for i in range(dp[n]):
    print(min_coins[money])
    money-=min_coins[money]
'''

Solution (Python):

n = int(input())
pre_list = [1,6,9,36,81,216,729,1296,6561,7776,46656,59049]
 

dp = [n]*(n+1)

dp[0] = 0
 
 

for i in range(1,n+1):

	for j in pre_list:
		if i - j >= 0:
			dp[i] = min(dp[i],dp[i-j]+1)
 
print(dp[n])

Solution (Python):
n = int(input())
dp = [n] * (n + 1)
dp[0] = 0
a = [1, 6**1, 6**2, 6**3, 6**4, 6**5, 6**6, 9**1, 9**2, 9**3, 9**4, 9**5]
for i in range(1, n + 1):
    for j in a:
        if i - j >= 0:
            dp[i] = min(dp[i], dp[i - j] + 1)
print(dp[n])

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

pre_list=[1, 6, 9, 36, 81, 216, 729, 1296, 6561, 7776, 46656, 59049]
dp = [-1]*(n+1)
dp[0] = 0
dp[1] = 1

for i in range(2,n+1):
    a = []
    a.append(dp[i-1]+1)
    for j in pre_list:
        if i-j >= 0:
            a.append(dp[i-j]+1)
        else:
            break

    dp[i] = min(a)

print(dp[-1])

Solution (Python):
from math import ceil, log


def solve(string):
    n = int(string)
    max_number = 10**5
    can_operate = [1] + [6**(i + 1) for i in range(ceil(log(max_number, 6)))
                        ] + [9**(i + 1) for i in range(ceil(log(max_number, 9)))]
    can_operate = sorted(can_operate)
    dp = [0]
    for _ in range(n + 0):
        tmp = n
        for o in can_operate:
            index = len(dp) - o
            if index < 0:
                break
            tmp = min(tmp, dp[index] + 1)
        dp.append(tmp)
    return str(dp[-1])


if __name__ == '__main__':
    print(solve(input()))

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


def main():
    ans = N

    for i in range(N + 1):
        num = 0
        cur = i

        while 0 < cur:
            num += cur % 6
            cur //= 6

        cur = N - i

        while 0 < cur:
            num += cur % 9
            cur //= 9

        if num < ans:
            ans = num

    print(ans)
    return


main()

Solution (Python):
N = int(input())
dp = [0]
six = 0
nine = 0
co = 0
for i in range(N+1):
    if i % (6**(six)) == 0:
        if 6**six > 9**nine:
            co = i
        six += 1
    if i % (9**(nine)) == 0:
        if 6**six < 9**nine:
            co = i
        nine += 1
    if i == 0:
        continue
    dpi = min(dp[i-1],dp[i-6**(six-1)],dp[i-9**(nine-1)])
    dp.append(dpi+1)
print(dp[N])

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

Solution (Python):
N=int(input())
weights=[1]
pow6=6
while N>=pow6:
    weights.append(pow6)
    pow6*=6
pow9=9
while N>=pow9:
    weights.append(pow9)
    pow9*=9
dp=[1<<28]*(N+1)
dp[0]=0
for i in range(len(weights)):
    for j in range(weights[i],N+1):
        dp[j]=min(dp[j],dp[j-weights[i]]+1)
print(dp[N])

Solution (Python):
n=int(input())
ans=10**9
for i in range(n+1):
    tmp=i
    res=0
    while tmp:
        res+=tmp%6
        tmp//=6
    tmp=n-i
    while tmp:
        res+=tmp%9
        tmp//=9
    ans=min(ans, res)
print(ans)

Solution (Python):
N=int(input())
dp=[N]*(N+1)
dp[0]=0
for i in range(N):
    pow6=1
    while i+pow6<=N:
        dp[i+pow6]=min(dp[i+pow6],dp[i]+1)
        pow6*=6
    pow9=1
    while i+pow9<=N:
        dp[i+pow9]=min(dp[i+pow9],dp[i]+1)
        pow9*=9
print(dp[N])

Solution (Python):
N=int(input())
dp=[N]*(N+1)
dp[0]=0
for i in range(1,N+1):
    dp[i]=min(dp[i],dp[i-1]+1)
    pow6 = 1
    while i>=pow6:
        dp[i]=min(dp[i],dp[i-pow6]+1)
        pow6*=6
    pow9 = 1
    while i>=pow9:
        dp[i]=min(dp[i],dp[i-pow9]+1)
        pow9*=9
print(dp[N])

Solution (Python):
def strange_bank(N: int) -> int:
    prices = [1] + \
        [9 ** i for i in range(1, 6)] + \
        [6 ** i for i in range(1, 7)]
    dp = [float('inf')] * (N + 1)
    dp[N] = 0

    for n in range(N, 0, -1):
        for p in prices:
            if p <= N:
                dp[n-p] = min(dp[n] + 1, dp[n-p])

    return dp[0]


if __name__ == "__main__":
    N = int(input())
    ans = strange_bank(N)
    print(ans)

Solution (Python):
from itertools import count, takewhile
N = int(input())

def dfs(n, d={}):
  if(n < 6):
    return n
  if(n in d):
    return d[n]
  mn = max(takewhile(lambda x: x<=n, (9**i for i in count())))
  ms = max(takewhile(lambda x: x<=n, (6**i for i in count())))
  d[n] = min(dfs(n-mn), dfs(n-ms))+1
  return d[n]

print(dfs(N))

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

ans = 1e9
for i in range(N+1):
  cnt = 0
  tmp = i
  while tmp > 0:
    cnt += tmp%6
    tmp //= 6
  tmp = N-i
  while tmp > 0:
    cnt += tmp%9
    tmp //= 9
  ans = min(ans, cnt)
print(ans)

Solution (Python):
import collections

c9 = []
c6 = []
for i in range(7):
    c9.append(9 ** i)
    c6.append(6 ** i)

inf = 1 << 60
N = int(input())
q = collections.deque()
q.append((N,0))
ans = inf
try:
    while True:
        v = q.popleft()
        if v[1] >= ans:
            continue
        for i in range(6,0,-1):
            if v[0] >= c9[i]:
                v2 = (v[0] - c9[i], v[1] + 1)
                q.append(v2)
                break
        for i in range(6,0,-1):
            if v[0] >= c6[i]:
                v2 = (v[0] - c6[i], v[1] + 1)
                q.append(v2)
                break
        if v[0] < 6:
            v2 = (0, v[1] + v[0])
            ans = min(ans, v2[1])

except IndexError:
    pass

print(ans)

Solution (Python):
N = int(input())
all = [1]
all.extend([9 ** i for i in range(1, 6)])
all.extend([6 ** i for i in range(1, 7)])
all.sort()
INF = 10 ** 12
dp = [INF] * (N + 1)
dp[0] = 0
def func_dp(n, k):
    if n - k >= 0:
        return dp[n - k]
    return INF
for i in range(1, N + 1):
    dp[i] = 1 + min([func_dp(i, j) for j in all])
print(dp[N])

Solution (Python):
N = int(input())
dp = [0]*100001
L = [1,6,36,216,1296,7776,46656,9,81,729,6561,59049]
for i in range(100001):
    for j in range(len(L)):
        if 1 <= i+L[j] <= 100000:
            if dp[i+L[j]] == 0:
                dp[i+L[j]] = dp[i]+1
            else:
                dp[i+L[j]] = min(dp[i]+1,dp[i+L[j]]) 
print(dp[N])

Solution (Python):
N = int(input())
S = [1, 6, 9, 36, 81, 216, 729, 1296, 6561, 7776, 46656, 59049]
X = [-1] * (N+1)
X[0] = 0
for i in range(1, N+1):
    mi = X[i-1] + 1
    for s in S:
        if s <= i:
            mi = min(mi, X[i-s] + 1)
    X[i] = mi

print(X[N])

Solution (Python):
n = int(input())
ws = [1]
ws += [6**i for i in range(1, 8)]
ws += [9**i for i in range(1, 6)]
ws = sorted(set(ws))

INF = 10**5
dp = [INF] * (n+1)
dp[0] = 0
for i in range(n+1):
    for w in ws:
        if i + w <= n:
            dp[i+w] = min(dp[i]+1, dp[i+w])
print(dp[-1])

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

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

sixes=[6**(i) for i in range(1,7)]
nines=[9**(i) for i in range(1,6)]

for i in range(1,N+1):
  dp[i]=dp[i-1]+1
  
  for s in sixes:
    if i-s>=0:
      dp[i]=min(dp[i],dp[i-s]+1)
    else:
      break
      
  for n in nines:
    if i-n>=0:
      dp[i]=min(dp[i],dp[i-n]+1)
    else:
      break

print(dp[N])

Solution (Python):
N = int(input())
INF = 10 ** 9

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

print(dp[N])

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

nine = [9**i for i in range(7, 0, -1)]
six = [6**i for i in range(8, 0, -1)]
tmp = {}

def f(n):
  if(n < 6):
    return n
  if(n in tmp):
    return tmp[n]
  
  m = 1e9+7
  if(n >= 9):
    mn = max(x for x in nine if x <= n)
    if(n%mn == 0):
      m = min(m, n//mn)
    else:
      m = min(m, f(n-mn)+1)
  ms = max(x for x in six if x <= n)
  if(n%ms == 0):
    m = min(m, n//ms)
  tmp[n] = min(m, f(n-ms)+1)
  return tmp[n]
print(f(N))

Solution (Python):
n = int(input())
lis = [1, 6, 36, 216, 1296, 7776, 46656,9, 81, 729, 6561, 59049]
lis.sort(reverse=True)
dp = [10 ** 10 for i in range(n+1)]
dp[0] = 0
for i in range(n):
  for num in lis:
    try:
      dp[i+num] = min(dp[i+num],dp[i]+1)
    except:
      continue
print(dp[n])

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

for i in range(n + 1):
  cc = 0
  t = i  
  while t > 0:
    cc += t % 6
    t //= 6
  t = n - i  
  while t > 0:
    cc += t % 9
    t //= 9
  if res > cc:
    res = cc
print(res)

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

list_1 = [1]
list_6 = [6**(i+1) for i in range(6)]
list_9 = [9**(i+1) for i in range(5)]
list_169 = list_1+list_6+list_9

list_169 = sorted(list_169, reverse=True)


N_sub = N
d_count = 0
for i in range(len(list_169)):
    while list_169[i] <= N_sub:
        N_sub -= list_169[i]
        d_count += 1


dp = [[100000 for j in range(13)] for i in range(N+1)]

def N_mai(N_sub, index, s_count):
    global d_count
    if N_sub == 0:
        return 0
    elif dp[N_sub][index] != 100000:
        return dp[N_sub][index]
    else:
        if list_169[index] == 1:
            count = N_sub
        elif N_sub >= list_169[index]:
            count = min(N_mai(N_sub - list_169[index], index, s_count+1)+1,
                        N_mai(N_sub - list_169[index], index+1, s_count+1)+1, 
                        N_mai(N_sub, index+1, s_count))
        else:
            count = N_mai(N_sub, index+1, s_count)

        dp[N_sub][index] = count
        return count

print(min(d_count, N_mai(N, 0, 0)))

Solution (Python):
n = int(input())
amounts = [1, 6, 9, 36, 81, 216, 729, 1296, 6561, 7776, 46656, 59049]

INF = 10 ** 6
dp = [INF] * (n + 1)
dp[0] = 0
dp[1] = 1
for i in range(2, n + 1):
  for a in amounts:
    r = i - a
    if r >= 0:
      dp[i] = min(dp[i], dp[r] + 1)
print(dp[n])

Solution (Python):
n = int(input())
amounts = [1, 6, 9, 36, 81, 216, 729, 1296, 6561, 7776, 46656, 59049]

INF = 10 ** 6
dp = [INF] * (n + 1)
dp[0] = 0
dp[1] = 1
for i in range(2, n + 1):
  for a in amounts:
    r = i - a
    if r >= 0:
      dp[i] = min(dp[i], dp[r] + 1)
print(dp[n])

Solution (Python):
a=int(input())
l=[i for i in range(a+1)]
i=1
while 6**i<=a:
    q=6**i
    for x in range(q,a+1):
        l[x]=min(l[x-q]+1,l[x])
    i+=1
i=1
while 9**i<=a:
    q=9**i
    for x in range(q,a+1):
        l[x]=min(l[x-q]+1,l[x])
    i+=1
print(l[a])

Solution (Python):
n = int(input())
c = [6**i for i in range(1,7)]
c.extend([9**i for i in range(1, 6)])
c = sorted(c)[::-1]
dp = [0]*1000000
for i in range(1,n+1):
    dp[i]=dp[i-1]+1
    for c_ in c:
        if i>=c_:
            dp[i]=min(dp[i],dp[i-c_]+1)
print(dp[n])

Solution (Python):
N = int(input())
inf = float("inf")
dp = [inf]*(100011)
def main():
    dp[0] = 0
    for i in range(1,100011):
        dp[i] = inf
        power_6 = 1
        power_9 = 1
        while power_6 <= i:
            dp[i] = min(dp[i],dp[i-power_6]+1)
            power_6 *= 6
        while power_9 <= i:
            dp[i] = min(dp[i],dp[i-power_9]+1)
            power_9 *= 9

if __name__ == "__main__":
    main()
    print(dp[N])

Solution (Python):
import sys
from itertools import count, takewhile

def dfs(n, d={}):
  if n < 6:
    return n
  if n in d:
    return d[n]

  max9 = max(takewhile(lambda x: x<=n, (9**i for i in count())))
  max6 = max(takewhile(lambda x: x<=n, (6**i for i in count())))
  d[n] = min(dfs(n-max9), dfs(n-max6)) + 1
  return d[n]


def main():
  input = sys.stdin.readline
  N = int(input())
  print(dfs(N))
  
if __name__ == '__main__':
  main()

Solution (Python):
import sys

def f(n):
  X6 = []
  X9 = []
  for i in range(0, 10):
    if n >= 6**i:
      X6.append(6**i)
    if n >= 9**i:
      X9.append(9**i)
  return max(X6), max(X9)


def main():
  input = sys.stdin.readline
  N = int(input())
  dp = [0 for _ in range(N+1)]
  for i in range(1, N+1):
    can = []
    max6, max9 = f(i)
    X = [1, max6, max9]
    for x in X:
      can.append(dp[i-x] + 1)
    dp[i] = min(can)
  print(dp[N])

if __name__ == '__main__':
  main()