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):
def calc(n,num):
  ret=0
  while n>0:
    ret+=n%num
    n//=num
  return ret

N=int(input())
ans=N

for i in range(N+1):
  cnt=0
  cnt+=calc(i,6)
  cnt+=calc(N-i,9)
  ans=min(ans,cnt)
print(ans)

Solution (Python):

n = int(input())
ans = n

def calc(n, num):
    ret = 0
    while n > 0:
        ret += n % num
        n //= num
    return ret

for i in range(n + 1):
    cc = 0
    cc += calc(i, 6)
    cc += calc(n - i, 9)
    ans = min(ans, cc)

print(ans)

Solution (Python):
n = int(input())
min_count = n
for i in range(n+1):
    m = i
    result = 0
    while m > 0:
        result += m % 6
        m //= 6
    m = n-i
    while m > 0:
        result += m %9
        m //= 9
    min_count = min(result, min_count)
print(min_count)

Solution (Python):
import math
import collections
from operator import mul
from functools import reduce
import bisect



n=int(input())
a=[1]
s=6
while s<=n:
    a.append(s)
    s*=6
s=9
while s<=n:
    a.append(s)
    s*=9
a=sorted(list(set(a)))


dp=[10000000000000]*(n+1)
dp[0]=0

for i in range(n):
    for ai in a:
        if i+ai<=n:
            dp[i+ai]=min(dp[i+ai],dp[i]+1)
       
print(dp[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
    ans = min(ans,cc)
print(ans)

Solution (Python):


'''

import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
from itertools import permutations, combinations, product, accumulate, groupby
from bisect import bisect_left, bisect_right, insort_left, insort_right
from operator import itemgetter as ig

'''

'''
INF = float("INF")
mod = 10 ** 9 + 7
"""dd = [(-1, 0), (0, 1), (1, 0), (0, -1)];
ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)];
ddn9 = ddn + [(0, 0)]
for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""

def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]  
def ws(): return sys.stdin.readline().split()
def si(): return int(sys.stdin.readline())  
def ss(): return input()
def hi(n): return [si() for _ in range(n)]
def hs(n): return [ss() for _ in range(n)]  
def s_list(): return list(input())
def mi(n): return [wi() for _ in range(n)]  
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]
def num_grid(n): return [[int(i) for i in sys.stdin.readline().split()[0]] for _ in range(n)]  
def grid(n): return [s_list() for _ in range(n)]

'''
def main():
    N = int(input())
    dp = [99999999] * (N + 1)
    dp[0] = 0
    for i in range(1, N + 1):
        dp[i] = dp[i - 1] + 1
        k = 6
        while i - k >= 0:
            dp[i] = min(dp[i], dp[i - k] + 1)
            k *= 6
        k = 9
        while i - k >= 0:
            dp[i] = min(dp[i], dp[i - k] + 1)
            k *= 9

    print(dp[N])

if __name__ == '__main__':
    main()

Solution (Python):
import sys

import bisect






import itertools


import math



readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n = int(input())

    ones = [1]
    sixs = [6, 36, 216, 1296, 7776, 46656]
    nines = [9, 81, 729, 6561, 59049]
    withdraws = ones + sixs + nines

    money = {0}
    cnt = 0

    while True:
        cnt += 1
        next_money = set()
        for i in money:
            for j in withdraws:
                nxt = i + j
                if nxt <= n:
                    next_money.add(nxt)
        if n in next_money:
            print(cnt)
            sys.exit()
        else:
            money = next_money


if __name__ == '__main__':
    main()

Solution (Python):
from functools import lru_cache
import sys
sys.setrecursionlimit(10**6)
n=int(input())
@lru_cache(None)
def solve(n):
    
    if n==0:
        return 0
    if n==1:
        return 1
    ans=n
    cur=6
    while cur<=n:
        ans=min(ans,1+solve(n-cur))
        cur*=6
    cur=9
    while cur<=n:
        ans=min(ans,1+solve(n-cur))
        cur*=9
    return ans
print(solve(n))

Solution (Python):

import math

N = int(input()) 




single_withdraw_set = set()
single_withdraw_set.add(1)
single_withdraw_set |= {6**i for i in range(1,2 + int(math.log(N,6)))}
single_withdraw_set |= {9**i for i in range(1,2 + int(math.log(N,9)))}



withdraw_dict = {int(-i):10**9+7 for i in range(1,1 + max(single_withdraw_set)) }
withdraw_dict[0] = 0


for i in range(1,N+1):
    if i in single_withdraw_set:
        
        withdraw_dict[i] = 1
    else:
        
        withdraw_dict[i] = 1 + min([withdraw_dict[i-j] for j in single_withdraw_set])
    
    
    

print(withdraw_dict[N])

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

print(dp[N])

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

for i in range(1,N+1):
    s = 1
    while i-6**s >= 0:
        dp[i] = min(dp[i],dp[i-6**s] + 1)
        s += 1
    n = 1
    while i-9**n >= 0:
        dp[i] = min(dp[i],dp[i-9**n] + 1)
        n += 1

print(dp[N])

Solution (Python):
import sys
import heapq
from math import ceil, floor
from collections import deque, Counter, defaultdict
from fractions import gcd
input = lambda: sys.stdin.readline().rstrip()

def eprint(s):
    sys.stderr.write('DEBUG: {}'.format(s))
    return

def shortest_path(s, n, w, es):
    d = [float("inf")]*n
    d[s] = 0
    while True:
        update = False
        for p,q,r in es:
            if d[p] != float("inf") and d[q] > d[p] + r:
                d[q] = d[p] + r
                update = True
        if not update:
            break
    return d

def main():
    n = int(input())
    es = list()
    cnt = 0
    ps = [1, 6, 9, 36, 81, 216, 729, 1296, 6561, 7776, 46656, 59049]
    ps.sort()
    for i in range(n+1):
        for j in ps:
            if i + j <= n:
                es.append([i, i+j, 1])
                cnt += 1
            else:
                break

    reslut = shortest_path(0,n+1, cnt, es)
    print(reslut[n])
    return

if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
ary = [1]
x = 1
for i in range(6):
	x *= 6
	ary.append(x)
x = 1
for i in range(5):
	x *= 9
	ary.append(x)
ary.sort()

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

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

Solution (Python):
n = int(input())
ary = [1]
x = 1
for i in range(6):
	x *= 6
	ary.append(x)
x = 1
for i in range(5):
	x *= 9
	ary.append(x)
ary.sort()

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

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

Solution (Python):








import sys

sys.setrecursionlimit(10 ** 5 + 10)




def resolve():
    N = int(input())
    M = N//9  

    
    def nary_notation(x, n):
        bi = ''
        while x != 0:
            
            
            bi += str(x % abs(n))
            if n < 0:
                x = -(-x // n)
            else:
                x = x // n
        
        cnt = 0
        for j in bi:
            cnt += int(j)
        return cnt

    ans = 10 ** 9
    for i in range(M + 1):
        ans = min(nary_notation(9*i, 9) + nary_notation(N - (9 *i), 6), ans)
    print(ans)


resolve()

Solution (Python):
n=int(input())
A=[100]*(10**5+4)
A[0]=0
B=[1,6,6**2,6**3,6**4,6**5,6**6,9,9**2,9**3,9**4,9**5]
for i in range(1,n+2):
  A[i]=min(A[i-B[j]] for j in range(12))+1
print(A[n])

Solution (Python):
N = int(input())
dp = [i for i in range(100000+1)]
arr_6 = [6**i for i in range(11)]
arr_9 = [9**i for i in range(11)]
for index in range(100000+1):
  tmp = [v for v in arr_6 if index >= v]
  if len(tmp) != 0:
    tmp = tmp[-1]
    dp[index] = min(dp[index], dp[index - tmp] + 1)

  tmp = [v for v in arr_9 if index >= v]
  if len(tmp) != 0:
    tmp = tmp[-1]
    dp[index] = min(dp[index], dp[index - tmp] + 1)

print(dp[N])

Solution (Python):
dp=[100000 for i in range(100001)]
dp[0]=0
l=[1]
i=6
while i<=100000:
    l.append(i)
    i*=6
i=9
while i<=100000:
    l.append(i)
    i*=9
for i in range(1,100001):
    for j in l:
        if j<=i and dp[i-j]+1<dp[i]:
            dp[i]=dp[i-j]+1
print(dp[int(input())])

Solution (Python):
n = int(input())
base = []
i = 1
j = 1
i_6 = 6
i_9 = 9
dp = [float("inf")]*(n+1)
dp[0] = 0

base.append(1)

while i_6<=n:
  i_6 = 6**i
  base.append(i_6)
  i = i+1
  
while i_9<=n:
  i_9 = 9**j
  base.append(i_9)
  j = j+1
  
base.sort()
base_n = len(base)

for i  in range(1,n+1):
  for j in range(base_n):
    if 0 > i-base[j]:
      break
     
    temp = dp[i-base[j]]
    if temp < dp[i]:
      dp[i] = temp + 1
      
    
print(dp[n])

Solution (Python):
n = int(input())
base = []
i = 1
j = 1
i_6 = 6
i_9 = 9
dp = [float("inf")]*(n+1)
dp[0] = 0

base.append(1)

while i_6<=n:
  i_6 = 6**i
  base.append(i_6)
  i = i+1
  
while i_9<=n:
  i_9 = 9**j
  base.append(i_9)
  j = j+1
  
base.sort()
base_n = len(base)

for i  in range(1,n+1):
  for j in range(base_n):
    if 0 > i-base[j]:
      break
     
    temp = dp[i-base[j]]
    if temp < dp[i]:
      dp[i] = temp + 1
      
    
print(dp[n])

Solution (Python):
N=int(input())
DP=[0]*(N+1)
DP[1]=1
six=[]
nine=[]
numbersix=6
while numbersix<=N:
    six.append(numbersix)
    numbersix*=6
numbernine=9
while numbernine<=N:
    nine.append(numbernine)
    numbernine*=9
answers=six+nine

if N<=5:
    print(N)
elif N==6:
    print(1)
else:
    for a in range(2,N+1):
        kotae=[b for b in answers if b<=a]
        kouho=[DP[a-1]+1]
        for z in kotae:
            y=DP[a-z]+1
            kouho.append(y)
        DP[a]=min(kouho)
    print(DP[-1])

Solution (Python):


import itertools
from math import factorial
import sys
import heapq
from collections import Counter
from collections import deque
from fractions import gcd
from functools import reduce

sys.setrecursionlimit(4100000)
INF = 1 << 60
MOD = 10 ** 9 + 7


n = int(input())
dp = [INF] * (n + 1)
for i in range(n + 1):
    dp[i] = i
for i in range(n + 1):
    
    
    j = 1
    while i - pow(6, j) >= 0:
        dp[i] = min(dp[i], dp[i - pow(6, j)] + 1)
        j += 1
    k = 1
    while i - pow(9, k) >= 0:
        dp[i] = min(dp[i], dp[i - pow(9, k)] + 1)
        k += 1

print(dp[-1])

Solution (Python):
n = int(input())
res = n
for i in range(n+1):
    cnt = 0
    tmp = i
    while tmp > 0:
        t = 0
        while 6**t <= tmp:
            t += 1
        tmp -= 6**(t-1)
        cnt += 1
    tmp = n-i
    while tmp > 0:
        t = 0
        while 9**t <= tmp:
            t += 1
        tmp -= 9**(t-1)
        cnt += 1
    res = min(res, cnt)
print(res)

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

dp = [float("inf") for _ in range(100010)]
dp[0] = 0

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

Solution (Python):



N = int(input())


INF = 10**15
dp = [INF] * (N+1)


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

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

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

    
    if i>=1:
        dp[i] = min(dp[i], dp[i-1]+1)


print(dp[N])

Solution (Python):
N=int(input())
dp=[float("inf")]*(10**5+10)
dp[0]=0
for i in range(1,N+1):
	dp[i]=1+dp[i-1]
	X=6
	Y=9
	j=1
	k=1
	while(i>=X**j):
		dp[i]=min(dp[i],1+dp[i-X**j])
		j+=1
	while(i>=Y**k):
		dp[i]=min(dp[i],1+dp[i-Y**k])
		k+=1
print(dp[N])

Solution (Python):
def main():
    from functools import lru_cache
    from sys import setrecursionlimit
    setrecursionlimit(10**6)
    N = int(input())
    withdraws = []
    for i in range(N):
        if N < 9**i:
            break
        withdraws.append(9**i)
    for i in range(1, N):
        if N < 6**i:
            break
        withdraws.append(6**i)
    withdraws.sort(reverse=True)

    @lru_cache(maxsize=100000)
    def rec(cur):
        if cur == 0:
            return 0
        ret = cur
        for draw in withdraws:
            if cur < draw:
                continue
            ret = min(ret, rec(cur - draw) + 1)
        return ret

    print(rec(N))


if __name__ == '__main__':
    main()

Solution (Python):

n = int(input())

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

inf = pow(10, 10)
dp = [inf for _ in range(n + 1)]
dp[0] = 0
for i in range(1, n + 1):
    for j in range(len(coin)):
        if i - coin[j] >= 0:
            dp[i] = min(dp[i], dp[i - coin[j]] + 1)
print(dp[n])

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

    withdraws = []
    for i in range(N):
        if N < 9**i:
            break
        withdraws.append(9**i)
    for i in range(1, N):
        if N < 6**i:
            break
        withdraws.append(6**i)
    withdraws.sort(reverse=True)
    W = len(withdraws)

    dp = [[10**9 for i in range(N + 1)] for j in range(W + 1)]
    dp[0][0] = 0
    for i in range(1, W+1):
        for n in range(N + 1):
            if n - withdraws[i-1] >= 0:
                dp[i][n] = min(dp[i-1][n], dp[i][n - withdraws[i-1]] + 1)
            else:
                dp[i][n] = dp[i-1][n]
    print(dp[W][N])


if __name__ == '__main__':
    main()

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

    withdraws = []
    for i in range(N):
        if N < 9**i:
            break
        withdraws.append(9**i)
    for i in range(1, N):
        if N < 6**i:
            break
        withdraws.append(6**i)
    withdraws.sort(reverse=True)
    W = len(withdraws)

    dp = [[10**9 for i in range(N + 1)] for j in range(W + 1)]
    dp[0][0] = 0
    for i in range(1, W+1):
        for n in range(N + 1):
            if n - withdraws[i-1] >= 0:
                dp[i][n] = min(dp[i-1][n], dp[i][n],
                               dp[i][n - withdraws[i-1]] + 1)
            else:
                dp[i][n] = min(dp[i-1][n], dp[i][n])
    print(dp[W][N])


if __name__ == '__main__':
    main()

Solution (Python):
def rec(n, x):
        d, m = divmod(n, x)
        if d: return m + rec(d, x)
        else: return m

ans = n = int(input())
for i in range(n+1):
        ans = min(ans, rec(i, 6)+rec(n-i, 9))
print(ans)

Solution (Python):
import sys


def solve():
    input = sys.stdin.readline
    N = int(input())
    DP = [int(i) for i in range(N + 1)]
    ni = 9
    for i in range(N):
        if ni > N: break
        for j in range(N - ni + 1):
            DP[j + ni] = min(DP[j + ni], DP[j] + 1)
        ni *= 9
    six = 6
    for i in range(N):
        if six > N: break
        for j in range(N - six + 1):
            DP[j + six] = min(DP[j + six], DP[j] + 1)
        six *= 6
    print(DP[N])
    
    return 0

if __name__ == "__main__":
    solve()

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

a = [1]
n6 = 6
while n6 <= 100000:
    a.append(n6)
    n6 *= 6
n9 = 9
while n9 <= 100000:
    a.append(n9)
    n9 *= 9


dp = [10**9] * (N+100010)
dp[0] = 0

for i in range(N):
    for n in a:
        dp[i+n] = min(dp[i+n], dp[i]+1)
print(dp[N])

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

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()
dp = [0]*(n+1)

for i in range(1,n+1):
    c = dp[i-1]
    for j in range(6):
        a = i-9**j if i-9**j >= 0 else i-1
        c = min(c, dp[a])
    for j in range(7):
        a = i-6**j if i-6**j >= 0 else i-1
        c = min(c, dp[a])
    dp[i] = c+1

print(dp[n])

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

l=[1]
l_9=[pow(9,i) for i in range(1,7)]
l_6=[pow(6,i) for i in range(1,8)]
l+=l_9
l+=l_6
l.sort(reverse=True)
dp=[10**9 for i in range(n+1)]

dp[0]=0

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

Solution (Python):



def sixnine(m):
    ret=[]
    for n in [6,9]:
        tmp=1
        while True:
            tmp*=n
            if tmp<=m:
                ret.append(tmp)
            else:
                break
    ret.sort()
    return ret


N=int(input())
dp=[0 for i in range(N+1)]
for i in range(1,N+1):
    if i<=5:
        dp[i]=i
        continue
    sn=sixnine(i)
    if i in sn:
        dp[i]=1
        continue
    ans=10**19
    for k in sn:
        ans=min(ans,dp[k]+dp[i-k])
    dp[i]=ans

print(dp[-1])

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
N = int(input())
bl = [False]*(N+1)
memo = [N]*(N+1)

def f(n):
    if bl[n]:
        return memo[n]
  
    m = N

    i = 0
    while n >= 6**i:
        if n == 6**i:
            bl[n] = True
            memo[n] = 1
            return 1
        m = min(m, f(n-6**i)+1)
        i += 1

    i = 1
    while n >= 9**i:
        if n == 9**i:
            bl[n] = True
            memo[n] = 1
            return 1
        m = min(m, f(n-9**i)+1)
        i += 1
    
    bl[n] = True
    memo[n] = m
    return m

print(f(N))

Solution (Python):
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

n = INT()
arr = [1]
arr.extend([pow(9, i) for i in range(1, 7)])
arr.extend([pow(6, i) for i in range(1, 8)])
arr.sort(reverse=True)
dp = [inf for _ in range(n + 1)]
dp[0] = 0
for i in range(1, n + 1):
    for j in arr:
        if i - j >= 0:
            dp[i] = min(dp[i], dp[i - j] + 1)
print(dp[n])

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

dp = [10**18] * (N + 1)
dp[0] = 0

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

ans = 10**18
for i, c in enumerate(dp):
    ans = min(ans, N - i + c)
print(ans)

Solution (Python):
n = int(input())
dp = [10 ** 18] * (n + 1)
dp[0] = 0

info = [[1, 1]]
for i in range(1, 10):
    info.append([6**i, 1])
for i in range(1, 10):
    info.append([9**i, 1])
    
for i in range(n):
    for w, v in info:
        if i + w >= n + 1:
            continue
        dp[i + w] = min(dp[i] + 1, dp[i + w])
print(dp[-1])

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

for n in range(N+1):
  i = 0
  while n >= 6**i:
    if n == 6**i:
      dp[n] = 1
    else:
      dp[n] = min(dp[n], dp[n-6**i]+1)
    i += 1
                
  i = 1
  while n >= 9**i:
    if n == 9**i:
      dp[n] = 1
    else:
      dp[n] = min(dp[n], dp[n-9**i]+1)
    i += 1

print(dp[N])

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

Solution (Python):




def div(n, t):
    if n < t:
        return n
    else:
        return div(n // t, t) + n % t


def main():
    N = int(input())
    print(min(div(i, 6) + div(N - i, 9) for i in range(N + 1)))


if __name__ == "__main__":
    main()

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

DP = [100010]*(N+1)
DP[0] = 0

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

print(DP[-1])

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

six = []
s = 6
while s <= n:
    six.append(s)
    s *= 6
s = 9
while s <= n:
    six.append(s)
    s *= 9
six.sort()
dp = [i for i in range(n+13)]
for s in six:
    for i in range(n-s+1):
        if dp[i] + 1 < dp[i+s]:
            dp[i+s] = dp[i] + 1

print(dp[n])

Solution (Python):
n = int(input())
dp = [0 for x in range(n+1)]
key = 1
while key <= n:
  key *= 6
while key > 1:
  for j in range(n+1):
    if j == 0 or dp[j]:
      if j+key <= n:
        if dp[j+key]:
          dp[j+key] = min([dp[j]+1, dp[j+key]])
        else:
          dp[j+key] = dp[j]+1
  key //= 6

key = 1
while key <= n:
  key *= 9
while key > 1:
  for j in range(n+1):
    if j == 0 or dp[j]:
      if j+key <= n:
        if dp[j+key]:
          dp[j+key] = min([dp[j]+1, dp[j+key]])
        else:
          dp[j+key] = dp[j]+1
  key //= 9

for i in range(1, n+1):
  if dp[i]:
    dp[i] = min([dp[i-1]+1, dp[i]])
  else:
    dp[i] = dp[i-1]+1

print(dp[n])

Solution (Python):
import sys


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())
a = [1]
b = 6
while True:
    a.append(b)
    b *= 6
    if b > 10 ** 5:
        break
b = 9
while True:
    a.append(b)
    b *= 9
    if b > 10 ** 5:
        break
a.sort()
a = [0] + a
dp = [[0 for _ in range(n + 1)] for _ in range(len(a))]
for i in range(n + 1):
    dp[0][i] = 10 ** 5
for i in range(1, len(a)):
    for j in range(1, n + 1):
        if a[i] > j:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = min(dp[i - 1][j], dp[i][j - a[i]] + 1)
print(dp[len(a) - 1][n])

Solution (Python):
n=int(input())
c=[1]
i=1
while (6**i)<=100000:
    c.append(6**i)
    i+=1
i=1
while (9**i)<=100000:
    c.append(9**i)
    i+=1
c.sort(reverse=True)
dp=[[0]*(n+1) for _ in range(len(c)+1)]
dp[0]=[i for i in range(n+1)]

for i in range(len(c)):
    for j in range(n+1):
        if 0<=j-c[i]<=n:
            dp[i+1][j]=min(dp[i][j], dp[i+1][j-c[i]]+1)
        else:
            dp[i+1][j]=dp[i][j]

print(dp[-1][-1])

Solution (Python):
n=int(input())
c=[1]
i=1
while (6**i)<=100000:
    c.append(6**i)
    i+=1
i=1
while (9**i)<=100000:
    c.append(9**i)
    i+=1
c.sort(reverse=True)
dp=[[0]*(n+1) for _ in range(len(c)+1)]
dp[0]=[i for i in range(n+1)]

for i in range(len(c)):
    for j in range(n+1):
        if 0<=j-c[i]<=n:
            dp[i+1][j]=min(dp[i][j], dp[i+1][j-c[i]]+1)
        else:
            dp[i+1][j]=dp[i][j]

print(dp[-1][-1])

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

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

print(ans)

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

ans = N
for v9 in range(N + 1):
    cnt = 0
    t = v9
    w = 9 ** 5
    while t >= 9:
        if t >= w:
            cnt9, t = divmod(t, w)
            cnt += cnt9
        w //= 9
    t = N - (v9 - t)
    w = 6 ** 7
    while t >= 6:
        if t >= w:
            cnt6, t = divmod(t, w)
            cnt += cnt6
        w //= 6
    ans = min(ans, cnt + t)

print(ans)

Solution (Python):
n=int(input())
s=set()
s.add(1)
a=6
while a<=n:
  s.add(a)
  a*=6
b=9
while b<=n:
  s.add(b)
  b*=9
dp=[10**9]*(n+1)
dp[0]=0
dp[1]=1
for i in range(n+1):
  for t in s:
    if i+t<=n:
      dp[i+t]=min(dp[i+t],dp[i]+1)
print(dp[n])

Solution (Python):
def solve():
    N = int(input())
    res = N
    for i in range(N + 1):
        cnt = 0
        t = i
        while t > 0:
            cnt += t % 6
            t //= 6
        t = N - i
        while t > 0:
            cnt += t % 9
            t //= 9
        res = min(res, cnt)
    return res

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

Solution (Python):
cand = [1]
MAX = 10**5 +1
for c in (6,9):
  coin = 1
  while 1:
    coin *= c
    if coin <= MAX:
      cand.append(coin)
    else:
      break
cand.sort()

dp = [float('inf') for i in range(MAX)]
dp[0] = 0
n = int(input())
for i in range(n):
  for c in cand:
    if i+c < MAX:
      dp[i+c] = min(dp[i+c], dp[i]+1)
print(dp[n])

Solution (Python):
inf=float("inf")
n=int(input())
DP=[inf]*(n+1)
DP[0]=0

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

print(DP[n])

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

res = n
for i in range(0, n+1):
    cnt = 0
    val = i
    while val > 0:
        cnt += val % 6
        val //= 6
    val = n - i
    while val > 0:
        cnt += val % 9
        val //= 9
    if res > cnt:
        res = cnt

print(res)

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

Solution (Python):
n=int(input())
dp=[i for i in range(n+1)]
for i in range(n):
    for j in range(7):
        if i+6**j>n:
            continue
        dp[i+6**j]=min(dp[i+6**j],dp[i]+1)
        if i+9**j<=n:
            dp[i+9**j]=min(dp[i+9**j],dp[i]+1)
print(dp[n])

Solution (Python):
from collections import deque


max_n = 110000
dp = [-1] * max_n  
dp[0] = 0  
n = int(input())
que = deque([])
que.append(dp[0])
while que:
    v = que.popleft()
    pow = 1
    while v + pow <= n:
        if dp[v + pow] == -1:
            dp[v + pow] = dp[v] + 1
            que.append(v + pow)
        pow *= 6
    pow = 1
    while v + pow <= n:
        if dp[v + pow] == -1:
            dp[v + pow] = dp[v] + 1
            que.append(v + pow)
        pow *= 9

print(dp[n])

Solution (Python):
n = int(input())
dp = [i for i in range(n + 2)]
for i in range(n + 1):
    pow = 6
    while i + pow <= n + 1:
        dp[i + pow] = min(dp[i + pow], dp[i] + 1)
        pow *= 6
    pow = 9
    while i + pow <= n + 1:
        dp[i + pow] = min(dp[i + pow], dp[i] + 1)
        pow *= 9

print(dp[n])

Solution (Python):
n = int(input())
a = [1]
q = [10000000000000 for _ in range(n+1)]
q[0] = 0

for i in range(6):
    a.append(6**(i+1))
for i in range(5):
    a.append(9**(i+1))
    
a.sort()

for i in range(1,n+1):
    for j in range(12):
        x = a[j]
        if i-x >= 0:
            q[i] = min(q[i] , q[i-x] + 1)
            
print(q[n])

Solution (Python):
n = int(input())
dp = [i for i in range(n + 1)]
for i in range(1, n+1):
    pow = 6
    while i - pow > -1:
        dp[i] = min(dp[i], dp[i - pow] + 1)
        pow *= 6
    pow = 9
    while i - pow > -1:
        dp[i] = min(dp[i], dp[i - pow] + 1)
        pow *= 9

print(dp[n])

Solution (Python):
n=int(input())
inf=float("inf")
DP=[inf]*(n+1)
DP[0]=0

for i in range(1,n+1):
    DP[i]=DP[i-1]+1
    for P in (6,9):
        cnt=1
        while P**cnt<=i:
            DP[i]=min(DP[i-1]+1,DP[i-P**cnt]+1,DP[i])
            cnt +=1
            
print(DP[n])

Solution (Python):
n=int(input())
inf=float("inf")
DP=[inf]*(n+1)
DP[0]=0

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

print(DP[n])

Solution (Python):
n=int(input())
inf=float("inf")
DP=[inf]*(n+1)
DP[0]=0

for i in range(1,n+1):
    DP[i]=DP[i-1]+1
    for point in (6,9):
        cnt=1
        while point**cnt<=i:
            DP[i]=min(DP[i-1]+1,DP[i-point**cnt]+1,DP[i])
            cnt +=1
            
print(DP[n])

Solution (Python):

import numpy as np

inf=10**7
n=int(input())
coin=[6**x for x in range(10)]
coin+=[9**x for x in range(1,10)]

dp=[0]*(n+1)
for (i,x) in enumerate(dp):
    dp[i]+=inf
dp[0]=0


for i in range(n+1):
    for x in coin:
        if(i+x<=n):
            dp[i+x]=min(dp[i+x],dp[i]+1)
print(dp[-1])

Solution (Python):

inf=10**7
n=int(input())

ad=[6**x for x in range(10)]
ad2=[9**x for x in range(1,10)]
ad.extend(ad2)

a=[inf]*(n+1)
a[0]=0
for i in range(n+1):
    for x in ad:
        if(x+i<=n):a[x+i]=min(a[x+i],a[i]+1)



print(a[n])

Solution (Python):
import sys
import os


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = int(sys.stdin.readline().rstrip())

    ret = N
    for n in range(N+1):
        cnt = 0
        i = n

        while (i > 0):
            cnt += i % 6
            i //= 6

        j = N - n
        while (j > 0):
            cnt += j % 9
            j //= 9

        ret = min(cnt, ret)

    print(ret)


if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
ans = [0]

for i in range(1, N+1):
    dp = []
    k = 1
    while i >= k:
        dp.append(ans[i-k]+1)
        k *= 6
    k = 1
    while i >= k:
        dp.append(ans[i-k]+1)
        k *= 9
    ans.append(min(dp))
print(ans[-1])

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

Solution (Python):
n=int(input())
nl=[9**i for i in range(1,6)][::-1]
sl=[6**i for i in range(1,7)][::-1]
a=n
for i in range(n+1):
    totals=0
    ps=i
    for j in sl:
        if ps >= j:
            totals+=ps//j
            ps= ps-ps//j*j
    totaln=0
    pn=n-i
    for k in nl:
        if pn >=k:
            totaln+= pn //k
            pn=pn-pn//k*k
    a=min(a,totals+totaln+ps+pn)
print(a)

Solution (Python):
n=int(input())
nl=[9**i for i in range(1,6)][::-1]
sl=[6**i for i in range(1,7)][::-1]
tl=[]
for i in range(n+1):
    totals=0
    ps=i
    for j in sl:
        if ps >= j:
            totals+=ps//j
            ps= ps-ps//j*j
    totaln=0
    pn=n-i
    for k in nl:
        if pn >=k:
            totaln+= pn //k
            pn=pn-pn//k*k
    tl.append(totals+totaln+ps+pn)
print(min(tl))