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):
N = int(input())

def calculate(n):

    indexes = [0]
    for i in range(n):
        indexes.append(0)


    for index in range(1,n+1):
        pow6 = 6
        pow9 = 9
        pows = []
        if index == 6:
            indexes[index] = 1
            continue
        elif index == 9:
            indexes[index] = 1
            continue
        elif index < 9:
            indexes[index] = index
            continue
        else:
            while pow6 <= index:
                pows.append(indexes[index - pow6] + 1)
                pow6 = pow6 * 6
            while pow9 <= index:
                pows.append(indexes[index - pow9] + 1)
                pow9 = pow9 * 9

            pows.append(indexes[index - 1] + 1)

            indexes[index] = min(pows)



    print(indexes[n])
calculate(N)

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

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


for i in range(n+1):
    
    
    cnt, p6, p9 = 0, i, n-i
    while p6 > 0:
        cnt += p6 % 6
        p6 //= 6
    while p9 >0:
        cnt += p9 %9
        p9 //= 9
    if cnt < ans:
        ans = cnt
print(ans)

Solution (Python):
pow9 = [1, 9, 81, 729, 6561, 59049]
pow6 = [1, 6, 36, 216, 1296, 7776, 46656]
memo={1:1}
def cand(n):
    if memo.get(n):
        return memo[n]
    else:
        for c in pow6[::-1]:
            if c == n:
                memo[n] = 1
                return 1
            elif c < n:
                a = 1 + cand(n - c)
                break
        for c in pow9[::-1]:
            if c == n:
                return 1
            elif c < n:
                b = 1 + cand(n - c)
                break
        memo[n] = min(a,b)
        return memo[n]
n = int(input())
print(cand(n))

Solution (Python):
n = int(input())
inf = 10**9
dp = [inf for i in range(n+1)]
dp[0] = 0
for i in range(n):
    if dp[i] != inf:
        
        dp[i+1] = min(dp[i] + 1, dp[i+1])
        num = 6
        while i + num <= n:
            dp[i + num] = min(dp[i] + 1, dp[i+num])
            num *= 6
        num = 9
        while i + num <= n:
            dp[i + num] = min(dp[i] + 1, dp[i+num])
            num *= 9

print(dp[n])

Solution (Python):


def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    
    from itertools import combinations, permutations, accumulate
    
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    

    inf = 10**17
    

    N = int(input())
    dp = [inf]*(N+1)
    dp[0] = 0
    money = [1, 6, 9, 36, 81, 216, 729, 6**4, 6561, 6**5, 6**6, 59049]
    while dp[N]==inf:
        for i in range(N, 0, -1):
            for j in money:
                if i<j:
                    continue
                dp[i] = min(dp[i-j]+1, dp[i])
    print(dp[N])

if __name__ == '__main__':
    main()

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

dp = [i for i in range(101010)]





t = 7
while True:
    for i in range(101010):
        if 6**t+(i+1) < 101010:
            dp[6**t+(i)] = min(dp[6**t+(i)], dp[i] + 1) 
    t -= 1
    if t == 0:
        break


t = 7
while True:
    for i in range(101010):
        if 9**t+(i+1) < 101010:
            dp[9**t+(i)] = min(dp[9**t+(i)], dp[i] + 1)
    t -= 1
    if t == 0:
        break

i = 0
while i+1 < 101010:
    dp[i+1] = min(dp[i+1],dp[i]+1)
    i += 1


print(dp[n])

Solution (Python):
N=int(input())
l=[i for i in range(100010)]
p=[6**i for i in range(1,7)]+[9**j for j in range(1,6)]
p.sort()

for c in p:
  if c>N:break
  for i in range(c, N+1):
    l[i] = min(l[i],l[i-c]+1)
print(l[N])

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

dp = [i for i in range(101010)]





t = 10
while True:
    for i in range(101010):
        if 6**t+(i+1) < 101010:
            dp[6**t+(i)] = min(dp[6**t+(i)], dp[i] + 1) 
    t -= 1
    if t == 0:
        break


t = 10
while True:
    for i in range(101010):
        if 9**t+(i+1) < 101010:
            dp[9**t+(i)] = min(dp[9**t+(i)], dp[i] + 1)
    t -= 1
    if t == 0:
        break

i = 0
while i+1 < 101010:
    dp[i+1] = min(dp[i+1],dp[i]+1)
    i += 1


print(dp[n])

Solution (Python):
def dfs(cc,t):
    global ans
    if t >= ans:
        return -1
    if t < ans:
        for i in range(6, 0, -1):
            if cc >= 9**i and t + cc//(9**i) < ans: 
                dfs(cc - 9**i, t + 1)
            if cc >= 6**i and t + cc//(6**i) < ans:
                dfs(cc - 6**i, t + 1)
    if ans > t + cc:
        ans = t + cc
        
N = int(input())
ans = N
dfs(N, 0)
print(ans)

Solution (Python):
N = int(input()) 
DP = [10000000]*(2*N+1)
DP[0] = 0
for i in range(0, N+1):
  DP[i+1] = min(DP[i+1],DP[i]+1)
  s = 6
  while s <= N:
    DP[i + s] = min(DP[i + s],DP[i]+1) 
    s = s*6
  n = 9
  while n <= N:
    DP[i + n] = min(DP[i + n],DP[i]+1)  
    n = n*9
print(DP[N])

Solution (Python):



from math import log, floor

def main():
  n = int(input())
  min = 10**10
  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 min > cc:
      min = cc
  print(min)

if __name__=='__main__':
  main()

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

def six_p(n) :
    temp = 0
    for i in reversed(range(7)) :
        temp += n//(6**i)
        n = n%(6**i)
    return temp

def nin_p(n) :
    temp = 0
    for i in reversed(range(6)) :
        temp += n//(9**i)
        n = n%(9**i)
    return temp

ans = 10**6
for i in range(N+1):
    ans = min(ans, six_p(i)+nin_p(N-i))

print(ans)

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

dp = [0] * (n + 1)
for i in range(n):
     if i in range(5):
          dp[i+1] = i + 1
     else:
          j = 1
          k = 1
          a = [100001]
          b = [100001]
          while i + 1 - 6**j >= 0:
              a += [dp[i + 1 - 6**j]]
              j += 1
          while i + 1 - 9**k >= 0:
              b += [dp[i + 1 - 9**k]]
              k += 1
          dp[i + 1] = min(dp[i],min(a),min(b)) + 1
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
    t=n-i
    while t>0:
        cnt+=t%9
        t//=9
    ans=min(ans,cnt)
print(ans)

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 = n + 100
dp = [inf] * (n+1)
dp[0] = 0
for i in range(n):
    if i <= n-1:
        dp[i+1] = min(dp[i+1], dp[i] + 1)

    cnt6 = 6
    while True:
        if i + cnt6 <= n:
            dp[i + cnt6] = min(dp[i + cnt6], dp[i] + 1)
            cnt6 *= 6
        else:
            break

    cnt9 = 9
    while True:
        if i + cnt9 <= n:
            dp[i + cnt9] = min(dp[i + cnt9], dp[i] + 1)
            cnt9 *= 9
        else:
            break

print(dp[n])

Solution (Python):
n = int(input())
INF = 10**5
answer = INF
for i in range(n+1):
    money = i
    cnt = 0
    while money > 0:
        cnt += money % 6
        money //= 6

    money = n-i
    while money > 0:
        cnt += money % 9
        money //= 9
    if answer > cnt:
        answer = cnt
print(answer)

Solution (Python):
n = int(input())
INF = 10**5
answer = INF

for i in range(n+1):
    cost = i
    ans = 0
    for p in range(8):
        ans += (cost // 6**p) % 6

    cost = n-i
    for q in range(7):
        ans += (cost // 9**q) % 9
    if answer > ans:
        answer = ans
print(answer)

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

def calculate(n):

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

    for index in range(1,n+1):
        pow6 = 6
        pow9 = 9
        if index < 6:
            memo[index] = index
        elif index == 6:
            memo[index] = 1
        elif index == 9:
            memo[index] = 1
        else:
            values = []

            while pow6 <= index:
                values.append(1 + memo[index - pow6])
                pow6 = pow6 * 6

            while pow9 <= index:
                values.append(1 + memo[index - pow9])
                pow9 = pow9 * 9

            values.append(1+memo[index-1])
            minValue = min(values)

            memo[index] = minValue

    return memo

result = calculate(N)
print(result[N])

Solution (Python):
import math,sys
sys.setrecursionlimit(20000000)
N = int(input())
memo = [-1 for i in range(110000)]
def calculate(n):

    if n == 0:
        memo[n] = 0
        return 0

    if memo[n] != -1:
        return memo[n]

    res = n

    pow6Num = 1
    while pow6Num*6 <= n:
        pow6Num = pow6Num * 6
        res = min(res, calculate(n - pow6Num) + 1)


    pow9Num = 1
    while pow9Num*9 <= n:
        pow9Num = pow9Num * 9
        res = min(res, calculate(n - pow9Num) + 1)

    memo[n] = int(res)
    return int(res)



result = calculate(N)
print(memo[N])

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

dp=[0]*(n+1)

for i in range(n+1):
    cnt=0
    j=i
    for exp6 in range(6,0,-1):
        curcnt=j//(6**exp6)
        j-=curcnt*(6**exp6)
        cnt+=curcnt
    dp[i]=j+cnt

for i in range(9**6):
    j=i
    paynine=0
    cnt=0
    exp9=1
    while j>0:
        bit=j%9
        j//=9
        cnt+=bit
        paynine+=bit*(9**exp9)
        exp9+=1
    
    if paynine>n:
        break

    dp[n]=min(dp[n],dp[n-paynine]+cnt)

print(dp[n])

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

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

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

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

print(dp[-1])

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):
def cash(a,N):
    ans = 0
    for i in reversed(range(len(a))):
        num = N//a[i]
        N -= a[i]*num
        ans += num
    return ans


N = int(input())

cash6 = []
cash9 = []
for i in range(1000):
    tmp = 6**i
    if tmp>N:
        break
    cash6.append(tmp)
for j in range(1000):
    tmp = 9**j
    if tmp>N:
        break
    cash9.append(tmp)

ans = 1e9
for i in range(N+1):
    ans = min(ans,cash(cash6,i)+cash(cash9,N-i))
print(ans)

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

LIMIT = 100000

unit = [1]
for a in [6, 9]:
    b = a
    while b <= LIMIT:
        unit.append(b)
        b *= a
unit.sort(reverse=True)


unit_num = len(unit)
unit = [0] + unit

dp = [[float('inf')]*(n+1) for _ in range(unit_num+1)]
dp[0][0] = 0

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

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

LIMIT = 100000

unit = [1]
for a in [6, 9]:
    b = a
    while b <= LIMIT:
        unit.append(b)
        b *= a
unit.sort()


unit_num = len(unit)
unit = [0] + unit

dp = [[float('inf')]*(n+1) for _ in range(unit_num+1)]
dp[0][0] = 0

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

Solution (Python):

from collections import deque

N=int(input())

dp = [-1] * 200005;
q = deque()

g = [1]
a = 6
while a <= 100000:
  g.append(a)
  a *= 6
a = 9
while a <= 100000:
  g.append(a)
  a *= 9
g.sort(reverse=True)

dp[0] = 0
q.append(0)

while len(q) > 0:
  v = q.popleft()
  if v == N: break
  for j in g:
    if dp[v+j] != -1: continue
    if v+j > N: continue
    dp[v+j] = dp[v] + 1
    q.append(v+j)

print(dp[N])

Solution (Python):


N=int(input())

dp = [100000] * 200005;

g = [1]
a = 6
while a <= 100000:
  g.append(a)
  a *= 6
a = 9
while a <= 100000:
  g.append(a)
  a *= 9
g.sort(reverse=True)

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

print(dp[N])

Solution (Python):
import math

dp = [float('inf') for _ in range(200000)]
withdraw = []

N = int(input())


withdraw.append(1)

for i in range(20):
    if 100000 >= 6**i:
        withdraw.append(6**i)
    if 100000 >= 9**i:
        withdraw.append(9**i)

withdraw = sorted(list(set(withdraw)))

dp[0] = 0

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

Solution (Python):


import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni = lambda: int(ns())
nin = lambda y: [ni() for _ in range(y)]
na = lambda: list(map(int, stdin.readline().split()))
nan = lambda y: [na() for _ in range(y)]
ns = lambda: stdin.readline().rstrip()
nsn = lambda y: [ns() for _ in range(y)]
ncl = lambda y: [list(ns()) for _ in range(y)]
nas = lambda: stdin.readline().split()

N = ni()
dp = [inf for _ in range(N + 1)]
dp[0] = 0

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

print(dp[N])

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

k9=5
k6=6
n9=9**k9
smin=n
for i9 in range(n9):
    ii9=i9
    s=0
    m=0
    astr=""
    for ii in range(1,k9+2):
        r9=ii9%9
        ii9=(ii9-r9)//9    
        s=s*9+r9
        m=m+r9
        astr=astr+str(r9)

    
    nr=n-s
    nr1=nr

    
    if nr==0:
        snra=m

    elif nr>0:
        snra=m
        for jj in range(k6,-1,-1):
            nra=nr1//(6**jj)
            nr1=nr1%(6**jj)
            snra=snra+nra

    if smin>snra:
        smin=snra
print(smin)

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

def f(n, c):
    res = 0
    while n > 0:
        res += n%c
        n //= c
    return res

l = []
for i in range(n+1):
    l.append(f(i,9)+f(n-i,6))
print(min(l))

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

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

print(dp[N])

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

def solve(num, c):
    Result = 0
    while num > 0:
        Result += num%c
        num //= c
    return Result

result = []
for i in range(n+1):
    result.append(solve(i, 9)+ solve(n-i, 6))
print(min(result))

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

Solution (Python):
n = int(input())
dp = [0 for _ in range(n+1)]
for i in range(1, n+1):  
    dp[i] = i  
    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())
def Count(x,p):
    res=0
    while x:
        res+=x%p
        x=x//p
    return res

ans=10**6+1
for i in range(0,n+1):
    ans=min(ans,Count(i,6)+Count(n-i,9))
    
print(ans)

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

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    n = int(input())
    money = sorted([6 ** i for i in range(7)] + [9 ** i for i in range(1, 6)], reverse=True)
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        dp[i] = min(dp[i - j] + 1 for j in money if i - j >= 0)
    print(dp[n])

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    n = int(input())
    money = sorted([6 ** i for i in range(7)] + [9 ** i for i in range(1, 6)], reverse=True)
    dp = [0] + [1000000] * n
    for i in range(1, n + 1):
        dp[i] = min(dp[i], *[dp[i - j] + 1 for j in money if i - j >= 0])
    print(dp[n])

if __name__ == '__main__':
    main()

Solution (Python):

n=int(input())
dp=[10**10 for i in range(200000)]
dp[0]=0
for i in range(1,100001):
    for j in range(9):
        num=3**j
        if i>=6**j and dp[i-6**j]+1<dp[i]:
            dp[i]=dp[i-6**j]+1
        if i>=9**j and dp[i-9**j]+1<dp[i]:
            dp[i]=dp[i-9**j]+1
print(dp[n])

Solution (Python):


def get_pow(target: int, base: int):
    ans = 0
    current = base
    for i in range(1, target + 1):
        if current > target:
            break
        ans = i
        current *= base
    return ans


dic = {}


def get_ans(remain: int):
    if remain in dic:
        return dic[remain]
    if remain < 6:
        return max(0, remain)
    ans = remain

    pos9 = get_pow(remain, 9)
    for i in reversed(range(1, pos9 + 1)):
        ret = get_ans(remain - pow(9, i)) + 1
        ans = min(ans, ret)

    pow6 = get_pow(remain, 6)
    for i in reversed(range(1, pow6 + 1)):
        ret = get_ans(remain - pow(6, i)) + 1
        ans = min(ans, ret)

    dic[remain] = ans
    return ans


n = int(input().rstrip())
print(get_ans(n))

Solution (Python):
n = int(input())
INF = 10 ** 8
dp = [INF] * 100010
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

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

print(dp[n])

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

Solution (Python):

L = [59049,46656,7776,6561,1296,729,216,81,36,9,6]
maxi = 100000
N = int(input())
memo = [0,1,2,3,4,5] + [-1 for _ in range(maxi)]
def f(n):
    if memo[n]!=-1:
        return memo[n]
    res = N
    for l in L:
        if n>=l:
            res = min(res,f(n-l)+1)
    memo[n] = res
    return res
print(f(N))

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

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

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

unit = []
for i in range(1, 2**32):
    if 6 ** i > N:
        break
    unit.append(6 ** i)
for i in range(1, 2**32):
    if 9 ** i > N:
        break
    unit.append(9 ** i)

for v in unit:
    dp[v] = 1

for i in range(2, N+1):
    num = dp[i]
    for v in unit:
        num = min(num, dp[v] + dp[i - v])
    dp[i] = num

print(dp[N])

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

roku = kyu = 1
h_list = [1]

while(roku<N):
    roku *= 6
    h_list.append(roku)

while(kyu<N):
    kyu *= 9
    h_list.append(kyu)



FIN = 10**7
dp = [FIN]*(N+1)
dp[0] = 0
for i in range(1, N+1):
    for j in range(len(h_list)):
        if h_list[j] <= i:
            dp[i] = min(dp[i], dp[i-h_list[j]]+1)
            

print(dp[N])

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

lst = []
cnt = 1
while True:
    lst.append(6**cnt)
    if N < lst[-1]:
        lst.pop()
        break
    else:
        cnt += 1
cnt = 1
while True:
    lst.append(9**cnt)
    if N < lst[-1]:
        lst.pop()
        break
    else:
        cnt += 1
lst.append(1)
lst.sort()
i = 0
DP = [100000]*100001
DP[0] = 0
for i in range(100001):
    for add in lst:
        if i+add <= N:
            DP[i+add] = min(DP[i+add],DP[i]+1)
print(DP[N])

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

dp = [10**6]*(n+1)
dp[0] = 0

l = [1, 6, 36, 216, 1296, 7776, 46656, 9, 81, 729, 6561, 59049]


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

print(dp[-1])

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

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

Solution (Python):
def main():
    n=int(input())
    mon6=[6]
    mon9=[1]
    for i in range(5):
        mon6.append(6*mon6[i])
        mon9.append(9*mon9[i])
    mon=mon6+mon9
    mon.sort()
    
    
    inf=10**9
    dp=[[inf]*(n+1) for i in range(13)]
    
    for i in range(13):
      dp[i][0]=0
    for i in range(12):
        for j in range(1,n+1):
            if j-mon[i]>=0:
                dp[i+1][j]=min(dp[i+1][j-mon[i]]+1,dp[i][j])
            else:
                dp[i+1][j]=dp[i][j]
    print(dp[-1][-1]) 
if __name__=='__main__':
    main()

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

dp = [100000] * (10**6)
dp[0] = 0

for n in range(N):
  count = 1
  while(True):
    if count > N:
      break

    dp[n+count] = min(dp[n+count], dp[n]+1)
    count *= 6

  count = 1
  while(True):
    if count > N:
      break

    dp[n+count] = min(dp[n+count], dp[n]+1)
    count *= 9

print(dp[N])

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

dp = [10000] * (N+1)

dp[0] = 0

for n in range(N+1):
  count = 1
  while(True):
    if count > N:
      break

    if n - count < 0:
      break

    dp[n] = min(dp[n], dp[n-count]+1)
    count *= 6

  count = 1
  while(True):
    if count > N:
      break

    if n - count < 0:
      break

    dp[n] = min(dp[n], dp[n-count]+1)
    count *= 9

print(dp[N])

Solution (Python):
from math import log
N = int(input())
dp = [0] * (10**5+1)
dpl = set()
a = 1
b = 1
while True:
    if a > 10**5:
        break
    a *= 6
    dpl.add(a)
while True:
    if b > 10**5:
        break
    b *= 9
    dpl.add(b)

for i in range(1, 10**5+1):
    if i < 6:
        dp[i] = i
        continue
    log6 = log(i, 6)
    log9 = log(i, 9)
    l = set(map(float, range(1, 20)))
    
    if log6 in l:
        dp[i] = 1
    elif log9 in l:
        dp[i] = 1
    
    else:
        minl = [dp[i-d]+1 for d in dpl if i-d >= 0]
        if minl:
            dp[i] = min(minl)

print(dp[N])

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

Solution (Python):
n=int(input())
def f(k,m):
  c=0
  while k: c+=k%m; k//=m
  return c
a=n
for i in range(n+1):
  a=min(a,f(i,6)+f(n-i,9))
print(a)

Solution (Python):
s={int(input())}
def f(k,m):
  p=1;
  while p*m<=k: p*=m
  return p
a=0
while all(s):
  s={i-f(i,6) for i in s}|{i-f(i,9) for i in s}
  a+=1
print(a)

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

dp=[float('inf')]*(n+1)
dp[0]=0
moneys=[6,9]
for money in range(n+1):
    if dp[money]!=float('inf'):

        for i in moneys:
            cnt=0
            while money+i**cnt<=n:
                dp[money+i**cnt]=min(dp[money]+1,dp[money+i**cnt])
                cnt+=1
print(dp[-1])

Solution (Python):
import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nan = lambda x: [na() for _ in range(x)]
ns = lambda: stdin.readline().rstrip()
nsn = lambda x: [ns() for _ in range(x)]
nas = lambda: stdin.readline().split()

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

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

print(dp[n])

Solution (Python):
N = int(input())
n6 = 1
n9 = 1
li = []
while 9**n9 <= N:
    li.append(9**n9)
    n9 += 1
while 6**n6 <= N:
    li.append(6**n6)
    n6 += 1

li.sort()
INF = 10**10

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


for i,l in enumerate(li):
    for j in range(N+1):
        if j+l > N : continue
        dp[j+l] = min(dp[j+l], dp[j]+1)
print(dp[N])

Solution (Python):
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from functools import *
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def Golf():
    *a,=map(int,open(0))
def S_():
    return input()
def IS():
    return input().split()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'

    mp=[1]*(w+2)
    found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['YES','NO']

mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()

input=lambda: sys.stdin.readline().rstrip()
 
def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

ans=0

n=I()
N=10**5+1
dp=[inf]*(N)
dp[0]=0
six=[6**i for i in range(1,7)]
nine=[9**i for i in range(6)]
a=six+nine
for i in range(n):
    for j in a:
        if i+j<N:
            dp[i+j]=min(dp[i+j],dp[i]+1)

print(dp[n])

Solution (Python):
N = int(input())
dp = [0] * (N+1)
import math
import heapq
if N != 59049:
    for i in range(1,N+1):
        A = []
        heapq.heapify(A)
        k = dp[i-1] +1
        heapq.heappush(A,k)
        s6 = int(math.log(i,6))
        s9 = int(math.log(i,9))
        for j in range(1,s6+1):
            d = i - 6**j
            l = dp[d] + 1
            heapq.heappush(A,l)
        for j in range(1,s9+1):
            dl = i - 9**j
            lu = dp[dl] + 1
            heapq.heappush(A,lu)
        dp[i] = heapq.heappop(A)
    print(dp[N])
else:
    print(1)

Solution (Python):
N = int(input())
dp = [0] * (N+1)
import math
import heapq
if N != 59049:
    for i in range(1,N+1):
        A = []
        heapq.heapify(A)
        k = dp[i-1] +1
        heapq.heappush(A,k)
        s6 = int(math.log(i,6))
        s9 = int(math.log(i,9))
        for j in range(1,s6+1):
            d = i - 6**j
            l = dp[d] + 1
            heapq.heappush(A,l)
        for j in range(1,s9+1):
            dl = i - 9**j
            lu = dp[dl] + 1
            heapq.heappush(A,lu)
        dp[i] = heapq.heappop(A)
    print(dp[N])
else:
    print(1)

Solution (Python):
N = int(input())
inf = float('inf')
dp = [inf] * 100001
dp[0] = 0
for n in range(1, 100001):
    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):
n=int(input())
ans=n
for i in range(n+1):
    buf=0
    j=n-i
    while i>0:
        i0=i%6
        i=(i-i0)//6
        buf+=i0
    while j>0:
        j0=j%9
        j=(j-j0)//9
        buf+=j0
    if buf<ans:
        ans=buf
print(ans)

Solution (Python):
list1=[6**i for i in range(1,7)]
list2=[9**i for i in range(1,6)]
data=[1]
data+=list1+list2
data.sort()
N=int(input())
count=0
dp=[10**7 for i in range(0,N+1)]
dp[0]=0
dp[1]=1
for i in range(2,N+1):
    max=0
    start=0
    end=11
    while end-start>1:
        test=(start+end)//2
        if N>=data[test]:
            start=test
        else:
            end=test
    if N>=data[end]:
        max=end
    else:
        max=start
    dp[i]=1+min(dp[i-data[j]] for j in range(0,max+1))
print(dp[N])

Solution (Python):
N = int(input())
DP = [100000000] * (N+1)
DP[0] = 0
for i in range (N):
    DP[i + 1] = DP[i] + 1
    for j in range (8):
        if 6**j <= i + 1:
            DP[i + 1] = min(DP[i + 1],DP[i + 1 - 6**j] + 1)
    for j in range (8):
        if 9**j <= i + 1:
            DP[i + 1] = min(DP[i + 1],DP[i + 1 - 9**j] + 1)
print(DP[N])

Solution (Python):
N = int(input())
r = 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
  r=min(r,c)
  
print(r)

Solution (Python):
INF = 10 ** 20
 
N = int(input())
coin_list = [1] + [6**i for i in range(1, 7)] + [9**i for i in range(1, 6)]
dp = [INF]*(N+1)
dp[0] = 0
 
for amount in range(1,N+1):
	for coin in coin_list:
	    if amount-coin >= 0: dp[amount] = min(dp[amount], dp[amount-coin]+1)
 
print(dp[N])

Solution (Python):
INF = 10 ** 20
 
N = int(input())
coin_list = [1] + [6**i for i in range(1, 7)] + [9**i for i in range(1, 6)]
dp = [INF]*(N+1)
dp[0] = 0
 
for i in range(1,N+1):
	for coin in coin_list:
	    if i-coin >= 0: dp[i] = min(dp[i], dp[i-coin]+1)
 
print(dp[N])

Solution (Python):
INF = 10 ** 20
 
N = int(input())
coin_list = [1] + [6**i for i in range(1, 7)] + [9**i for i in range(1, 6)]
dp = [INF]*(N+1)
dp[0] = 0
 
for coin in coin_list:
    for i in range(coin,N+1):
        dp[i] = min(dp[i], dp[i-coin]+1)
 
print(dp[N])