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())
ans=10**10
dp=[0]*100001
for i in range(1,n+1):
  tmp=[dp[i-1]+1]
  if i>=6**1:
    tmp.append(dp[i-6**1]+1)
  if i>=9**1:
    tmp.append(dp[i-9**1]+1)
  if i>=6**2:
    tmp.append(dp[i-6**2]+1)
  if i>=9**2:
    tmp.append(dp[i-9**2]+1)
  if i>=6**3:
    tmp.append(dp[i-6**3]+1)
  if i>=9**3:
    tmp.append(dp[i-9**3]+1)
  if i>=6**4:
    tmp.append(dp[i-6**4]+1)
  if i>=9**4:
    tmp.append(dp[i-9**4]+1)
  if i>=6**5:
    tmp.append(dp[i-6**5]+1)
  if i>=9**5:
    tmp.append(dp[i-9**5]+1)
  if i>=6**6:
    tmp.append(dp[i-6**6]+1)
  if i>=9**6:
    tmp.append(dp[i-9**6]+1)
  dp[i]=min(tmp)
print(dp[n])

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

INF = 105 * 10 ** 7
dp = [INF] * 100010
dp[0] = 0

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

print(dp[N])

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

ans = N
for i in range(N + 1):

    temp_ans = 0
    first = i
    second = N - i

    while first != 0:
        temp_ans += first % 6
        first = first // 6
    while second != 0:
        temp_ans += second % 9
        second = second // 9

    ans = min(ans, temp_ans)

print(ans)

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

Solution (Python):


def read_input():
    n = int(input())
    return n


def count_coin(x, op, min_op):
    if x == 0:
        return 0

    if x in min_op.keys():
        return min_op[x]

    min_count = 10000000
    for o in op:
        if x >= o:
            count = 1 + count_coin(x - o, op, min_op)
            if count < min_count:
                min_count = count

    min_op[x] = min_count
    return min_count


def submit():
    n = read_input()

    ops = [1, 6, 9]

    for op in ops[1:]:
        i = 1
        t = op ** i
        while t <= n:
            ops.append(t)
            t *= op

    ops = list(set(ops))
    ops.sort(reverse=True)
    print(count_coin(n, ops, {}))

if __name__ == '__main__':
    submit()

Solution (Python):
n = int(input())
six = []
for i in range(20):
    six.append(6 ** i)
nine = []
for i in range(20):
    nine.append(9 ** i)

res = 10 ** 10
for i in range(n + 1):
    j = n - i
    k = i
    
    cnt = 0

    
    piv = 19
    while k > 0 and piv >= 0:
        cnt += k // six[piv]
        k %= six[piv]
        piv -= 1

    
    piv = 19
    while j > 0 and piv >= 0:
        cnt += j // nine[piv]
        j %= nine[piv]
        piv -= 1

    res = min(res,cnt)
print(res)

Solution (Python):
n = int(input())
six = []
for i in range(20):
    six.append(6 ** i)
nine = []
for i in range(20):
    nine.append(9 ** i)

res = 10 ** 10
for i in range(n + 1):
    j = n - i
    k = i
    
    cnt = 0

    
    piv = 19
    while k > 0 and piv >= 0:
        cnt += k // six[piv]
        k %= six[piv]
        piv -= 1

    
    piv = 19
    while j > 0 and piv >= 0:
        cnt += j // nine[piv]
        j %= nine[piv]
        piv -= 1

    res = min(res,cnt)
print(res)

Solution (Python):
l=[1,6,9,36,81,216,729,1296,6561,7776,46656,59049]
l2=[0]*100001

N=int(input())

for i in range(1,N+1):
  mn=100000000000000000
  for x in l:
    if i-x>=0 and l2[i-x]<mn:
      mn=l2[i-x]+1
  l2[i]=mn

print(l2[N])

Solution (Python):
N=int(input())
l=[1,6,9,36,81,216,729,1296,6561,7776,46656,59049]
l2=[0]*100001

for i in range(1,100001):
  mn=100000000000000000
  for x in l:
    if i-x>=0 and l2[i-x]<mn:
      mn=l2[i-x]+1
  l2[i]=mn
print(l2[N])

Solution (Python):
N=int(input())
l=[1,6,9,36,81,216,729,1296,6561,7776,46656,59049]
l2=[0]*100010
for i in range(1,100010):
  mn=100000000000000000
  for x in l:
    if i-x>=0 and l2[i-x]<mn:
      mn=l2[i-x]+1
  l2[i]=mn
print(l2[N])

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

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

dp = [0] * (N + 1)

for i in range(1, N + 1):
    dp[i] = float('inf')
    p = 1
    while i - p >= 0:
        dp[i] = min(dp[i], dp[i - p] + 1)
        p *= 6
    q = 9
    while i - q >= 0:
        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(1, N+1):
    n = 1
    while n <= i:
        dp[i] = min(dp[i], dp[i-n]+1)
        n*=6
    n = 1
    while n <= i:
        dp[i] = min(dp[i], dp[i-n]+1)
        n*=9

print(dp[N])

Solution (Python):
N=int(input())
list=[1]
i=1
while(6**i<=N):
    list.append(6**i)
    i+=1
i=1
while(9**i<=N):
    list.append(9**i)
    i+=1
list.sort(reverse=True)
n=len(list)
INF=10**19
dp=[INF]*(N+1)
dp[0]=0
for i in range(N):
    for j in list:
        if i+1-j>=0:
            dp[i+1]=min(dp[i+1],dp[i+1-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):
N = int(input())



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

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 = t // 6
  t = N - i
  while t>0:
    cc += t % 9
    t = t // 9
  if cc < res:
    res = cc
print(res)

Solution (Python):
import sys
import numpy as np

readInt = lambda: int(sys.stdin.readline())
readIntN = lambda: [int(v) for v in sys.stdin.readline().split(' ')]

n = readInt()
ret = n
for s in range(n+1):
    c = 0
    v = s
    while 0 < v:
        c += v % 6
        v //= 6
    v = n - s
    while 0 < v:
        c += v % 9
        v //= 9
    ret = min(ret, c)
print(ret)

Solution (Python):
N = int(input())
a = [1, 6, 6**2, 6**3, 6**4, 6**5, 6**6, 9, 9**2, 9**3, 9**4, 9**5]
a.sort()
dp = [10**6]*160000
for i in a:
    dp[i] = 1
for i in range(1, N+1):
    for j in a:
        dp[i+j] = min(dp[i]+1, dp[i+j])
print(dp[N])

Solution (Python):
N = int(input())
a = [1, 6, 6**2, 6**3, 6**4, 6**5, 6**6, 9, 9**2, 9**3, 9**4, 9**5]
a.sort()
dp = [10**6]*160000
for i in a:
    dp[i] = 1
for i in range(1, N+1):
    for j in a:
        dp[i+j] = min(dp[i]+1, dp[i+j])
print(dp[N])

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

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

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

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

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

def compress(n, k, depth=1):
    d, m = divmod(n, k)
    if d == 0:
        return n * depth
    return compress(d, k) + m * depth

minv = float("inf")
for n9 in range(n // 9 + 1):
    m = (n - n9 * 9)
    n6, n1 = divmod(m, 6)
    result = n1 + compress(n6, 6) + compress(n9, 9)
    minv = min(minv, result)
print(min(minv, n))

Solution (Python):
N = int(input())
DP = [0]+[10**7]*(N)
li = [1] + [6**i for i in range(1,7)] + [9**i for i in range(1,6)]
for i in range(N+1):
    if(i in li):
        DP[i]=1
    else:
        for j in li:
            if(i-j>=0):
                DP[i]=min(DP[i],DP[i-j]+1)
print(DP[N])

Solution (Python):
N = int(input())
INF = float('inf')
dp = [INF] * 100010
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 = 1
    while i - k >= 0:
        dp[i] = min(dp[i], dp[i-k] + 1)
        k *= 9
print(dp[N])

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

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

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

		dp[i] = ans

	print(dp[N])

if __name__ == '__main__':
    main()

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

res = 10**10

for i in range(N+1):
  count = 0
  six = i
  while six>0:
    count += six%6
    six = six//6
  nine = N-i
  while nine>0:
    count += nine%9
    nine = nine//9
  res = min(res,count)

print(res)

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

count = 1
use_money = [1]
x = 1
while 6**x<=N:
  use_money.append(6**x)
  x+=1
x = 1
while 9**x<=N:
  use_money.append(9**x)
  x+=1
use_money.sort(reverse=True)
money = copy.copy(use_money)

while not(N in money):
  B = []
  for x in money:
    for y in use_money:
      if x+y<=N and not(x+y in B):
        B.append(x+y)
  B.sort(reverse=True)
  money = B[:min(5,len(B))]
  count+=1
print(count)

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

l1 = 2 ** 30
p6 = [1] * 7
p9 = [1] * 6
for i in range(1,7):
    p6[i] = p6[i-1] * 6
    if i < 6 : p9[i] = p9[i-1] * 9

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

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

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

Solution (Python):

import sys
INF = float("inf")


def solve(N: int):
    cand = [1]
    a = 6
    while a < 10**5:
        cand.append(a)
        a *= 6
    a = 9
    while a < 10**5:
        cand.append(a)
        a *= 9
    cand.sort()
    M = len(cand)

    dp = [0]*(N+1)
    for i in range(1, N+1):
        dp[i] = min([dp[i-cand[j]]+1 for j in range(M) if i-cand[j] >= 0])
    print(dp[N])
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    solve(N)


if __name__ == '__main__':
    main()

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

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

Solution (Python):
z=set([1])
for i in range(100):
	if 6**i <= 100000:
		z.add(6**i)
	if 9**i <= 100000:
		z.add(9**i)

N=int(input())
A=[0]*(N+1)

for n in range(1, N+1):
	ans = []
	for m in z:
		if n-m >= 0:
			ans.append(1 + A[n-m])
	A[n] = min(ans)

print(A[N])

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

for n in range(1, N+1):
    dp.append(dp[n-1]+1)
    exp = 6
    while exp <= n:
        dp[n] = min(dp[n], dp[n-exp] + 1)
        exp *= 6
    exp = 9
    while exp <= n:
        dp[n] = min(dp[n], dp[n-exp] + 1)
        exp *= 9

print(dp[-1])

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()

dp = [INF]*(100001)
dp[0] = 0
dp[1] = 1
dp[6] = 1
dp[6**2] = 1
dp[6**3] = 1
dp[6**4] = 1
dp[6**5] = 1
dp[6**6] = 1
dp[9] = 1
dp[9**2] = 1
dp[9**3] = 1
dp[9**4] = 1
dp[9**5] = 1

for i in range(N):
	dp[i+1] = min(dp[i+1], dp[i]+1)
	if i+6 > N:
		continue
	dp[i+6] = min(dp[i+6], dp[i]+1)
	if i+9 > N:
		continue
	dp[i+9] = min(dp[i+9], dp[i]+1)
	if i+6**2 > N:
		continue
	dp[i+6**2] = min(dp[i+6**2], dp[i]+1)
	if i+9**2 > N:
		continue
	dp[i+9**2] = min(dp[i+9**2], dp[i]+1)
	if i+6**3 > N:
		continue
	dp[i+6**3] = min(dp[i+6**3], dp[i]+1)
	if i+9**3 > N:
		continue
	dp[i+9**3] = min(dp[i+9**3], dp[i]+1)
	if i+6**4 > N:
		continue
	dp[i+6**4] = min(dp[i+6**4], dp[i]+1)
	if i+9**4 > N:
		continue
	dp[i+9**4] = min(dp[i+9**4], dp[i]+1)
	if i+6**5 > N:
		continue
	dp[i+6**5] = min(dp[i+6**5], dp[i]+1)
	if i+6**6 > N:
		continue
	dp[i+6**6] = min(dp[i+6**6], dp[i]+1)
	if i+9**5 > N:
		continue
	dp[i+9**5] = min(dp[i+9**5], dp[i]+1)



print(dp[N])

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

dp = [0] * (N+1)

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

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



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

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

a=[0]*(N+1)
for i in range(1,N+1):
    k=[a[i-1]]
    for j in range(1,10):
        x=i-6**j
        if x<0: break
        k.append(a[x])
        
    for j in range(1,10):
        x=i-9**j
        if x<0: break
        k.append(a[x])
    
    a[i]=min(k)+1


print(int(a[N]))

Solution (Python):
N = int(input())
dp = [0 for i in range(N+1)]
dp[1] = 1
kazu = [1]
i = 6
while i <= N:
    kazu.append(i)
    i*=6
i = 9
while i <= N:
    kazu.append(i)
    i*=9
kazu.sort()
kazulazor = len(kazu)
temp = [1]
lentemp = 1
index = 1
for i in range(2, N+1):
    kouho = []
    if index < kazulazor and i == kazu[index]:
        temp.append(i)
        index += 1
        lentemp += 1
    for j in range(lentemp):
        kouho.append(dp[i-temp[j]]+1)
    dp[i] = min(kouho)
print(str(dp[N]))

Solution (Python):
if __name__ == '__main__':
    target = int(input())
    withdraw_counts = [0] * (target + 1)

    for i in range(target + 1):
        if i < 6:
            withdraw_counts[i] = i
        elif i < 9:
            withdraw_counts[i] = i - 5
        else:
            needed_withdraw_counts = [withdraw_counts[i-1]]
            exp_n = 1
            while 6 ** exp_n <= i:
                needed_withdraw_counts.append(withdraw_counts[i - 6 ** exp_n])
                exp_n += 1
            exp_n = 1
            while 9 ** exp_n <= i:
                needed_withdraw_counts.append(withdraw_counts[i - 9 ** exp_n])
                exp_n += 1
            withdraw_counts[i] = min(needed_withdraw_counts) + 1
    print(withdraw_counts[target])

Solution (Python):

N = int(input())

def get_nums(wa,ar):
    ar = sorted(ar,reverse=True)
    tmp = 0
    for a in ar:
        tmp += wa // a
        wa %= a
    return tmp + wa


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

sixes = []
tmp = 6
while tmp <= N:
    sixes.append(tmp)
    tmp *= 6



res = N
for t in range(0,N + 1):
    hoge = get_nums(t,sixes) + get_nums(N - t,nines)
    res = min(res,hoge)

print(res)

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

memo = {i:i for i in range(6)}
def f(n):
    tmp = memo.get(n,None)
    if tmp != None:
        return tmp
    i,j = 0,0
    a,b = n,n
    while a >= 6:
        i += 1
        a //= 6
    while b >= 9:
        j += 1
        b //= 9
    ret = min(1+f(n-6**i),1+f(n-9**j))
    memo[n] = ret
    return ret

print(f(N))

Solution (Python):
N = int(input())
a = [1]
t = 6
while t <= N:
    a.append(t)
    t *= 6
t = 9
while t <= N:
    a.append(t)
    t *= 9
INF = 10 ** 9
dp = [0] + [INF for _ in range(N)]
for i in range(1, N + 1):
    for x in a:
        if x <= i and dp[i - x] + 1 < dp[i]:
            dp[i] = dp[i - x] + 1
print(dp[N])

Solution (Python):
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())

N = int(stdin.readline())
large = float('inf')
memo = {}
def cal_count(total):
    global memo
    if total in memo: return memo[total]
    if total < 0: return large
    if total == 0: return 0
    cans = []
    for i in range(1, 8):
        if 6 ** i > total: break
        cans.append(cal_count(total - 9 ** i))
        cans.append(cal_count(total - 6 ** i))
    cans.append(cal_count(total - 1))
    res = min(cans) + 1
    memo[total] = res
    return res
cnt = cal_count(N)
print(cnt)

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())
dp = [N]*(N+1)
dp[0] = 0

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

print(dp[-1])

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

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

print(dp[-1])

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

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

def fun(n):
  if n == 0:
    return 0
  elif dp[n] != 0:
    return dp[n]
  
  ans = N
  for i in [6**k for k in range(7)]:
    if i <= n:
      ans = min(ans, fun(n-i) + 1)
  for j in [9**l for l in range(6)]:
    if j <= n:
      ans = min(ans, fun(n-j) + 1)
  
  dp[n] = ans
  return dp[n]

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

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

def fun(n,x):
  i = 0
  while(n > 0):
    i += n % x
    n //= x
  return i

ans = N

for j in range(N+1):
  ans = min(ans,fun(j,6)+fun(N-j,9))
print(ans)

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] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007


def A():
    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
        if m < ans:
            ans = m
    print(ans)
    return


def B():
    return


def C():
    return


def D():
    return


def E():
    return


def F():
    return


def G():
    return


def H():
    return


def I_():
    return


def J():
    return


if __name__ == "__main__":
    A()

Solution (Python):
import bisect

six_list = [6 ** i for i in range(7)]
nine_list = [9 ** i for i in range(6)]

from functools import lru_cache


@lru_cache(maxsize=1000)
def six_nine(n):
    if n < 6:
        return n
    else:
        six = six_list[bisect.bisect_right(six_list, n) - 1]
        nine = nine_list[bisect.bisect_right(nine_list, n) - 1]
        return min(n // six + six_nine(n % six), 1 + six_nine(n - nine))


if __name__ == '__main__':
    x = int(input())
    print(six_nine(x))

Solution (Python):
import bisect
from functools import lru_cache

six_list = [6 ** i for i in range(7)]
nine_list = [9 ** i for i in range(6)]


@lru_cache(maxsize=1000)
def six_nine(n):
    if n < 6:
        return n
    else:
        six = six_list[bisect.bisect_right(six_list, n) - 1]
        nine = nine_list[bisect.bisect_right(nine_list, n) - 1]
        return min(n // six + six_nine(n % six), 1 + six_nine(n - nine))


if __name__ == '__main__':
    x = int(input())
    print(six_nine(x))

Solution (Python):
import bisect

six_list = [6 ** i for i in range(7)]
nine_list = [9 ** i for i in range(6)]


def six_nine(n):
    if n < 6:
        return n
    else:
        six = six_list[bisect.bisect_right(six_list, n) - 1]
        nine = nine_list[bisect.bisect_right(nine_list, n) - 1]
        return min(n // six + six_nine(n % six), 1 + six_nine(n - nine))


if __name__ == '__main__':
    x = int(input())
    print(six_nine(x))

Solution (Python):
import bisect


def six_nine(n):
    if n < 6:
        return n
    else:
        six = six_list[bisect.bisect_right(six_list, n) - 1]
        nine = nine_list[bisect.bisect_right(nine_list, n) - 1]
        return min(n // six + six_nine(n % six), 1 + six_nine(n - nine))


if __name__ == '__main__':
    x = int(input())
    six_list = [6 ** i for i in range(7)]
    nine_list = [9 ** i for i in range(6)]
    print(six_nine(x))

Solution (Python):
import bisect

x = int(input())
six_list = [6 ** i for i in range(7)]
nine_list = [9 ** i for i in range(6)]


def six_nine(n):
    if n < 6:
        return n
    else:
        six = six_list[bisect.bisect_right(six_list, n) - 1]
        nine = nine_list[bisect.bisect_right(nine_list, n) - 1]
        return min(n // six + six_nine(n % six), 1 + six_nine(n - nine))


print(six_nine(x))

Solution (Python):
import bisect

x = int(input())
six_list = [6 ** i for i in range(7)]
nine_list = [9 ** i for i in range(6)]


def six_nine(n):
    if n == 0:
        return 0
    else:
        six = six_list[bisect.bisect_right(six_list, n) - 1]
        nine = nine_list[bisect.bisect_right(nine_list, n) - 1]
        return min(n // six + six_nine(n % six), 1 + six_nine(n - nine))


print(six_nine(x))

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

six_list = [6 ** i for i in range(7)]
nine_list = [9 ** i for i in range(6)]

import bisect

def six_nine(n):
  if n == 0:
    return 0
  else:
    six = six_list[bisect.bisect_right(six_list, n) - 1]
    nine = nine_list[bisect.bisect_right(nine_list, n) - 1]
    return min(n // six + six_nine(n % six), 1 + six_nine(n - nine))


print(six_nine(n))

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

N = int(input())

dp = [float("inf") for i in range(200000)]
dp[0] = 0
for i in range(N + 1):
	for j in L:
		if dp[i] + 1 <= dp[i + j]:
			dp[i + j] = dp[i] + 1
print(dp[N])

Solution (Python):


















import math
import copy
from collections import defaultdict, Counter

from itertools import product

from itertools import permutations

from itertools import combinations
from bisect import bisect_left, bisect_right


def i_inpl(): return int(input())
def s_inpl(): return map(int,input().split())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")

N = i_inpl()
dp = [INF for _ in range(N+1)]

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):


















import math
import copy
from collections import defaultdict, Counter

from itertools import product

from itertools import permutations

from itertools import combinations
from bisect import bisect_left, bisect_right


def i_inpl(): return int(input())
def s_inpl(): return map(int,input().split())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")

N = i_inpl()
dp = [INF for _ in range(N+1)]

dp[0] = 0

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

print(dp[N])

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

for i in range(1,N+1):
    for p in range(N+1):
        p = 6**p
        if p > N:
            break
        dp[i] = min(dp[i],dp[i-p]+1)
    for p in range(N+1):
        p = 9**p
        if p > N:
            break
        dp[i] = min(dp[i],dp[i-p]+1)

print(dp[N])

Solution (Python):
from collections import defaultdict
from string import ascii_uppercase
import sys, bisect
stdin = sys.stdin
read_int = lambda : list(map(int,stdin.readline().split()))
read_str = lambda : stdin.readline().rstrip()

N = read_int()[0]

items = [1]
Nd6 = 0
while True:
    if N // (6**(Nd6 + 1)) > 0:
        Nd6 += 1
        items.append(6 ** Nd6)
    else: break

Nd9 = 0
while True:
    if N // (9 ** (Nd9 + 1)) > 0:
        Nd9 += 1
        items.append(9 ** Nd9)
    else: break

items.sort()

dp = [0 for _ in range(N + 1)]
def solve():
    for i in range(N):
        for itm in items:
            if i + itm < N + 1:
                if dp[i + itm] == 0:
                    dp[i + itm] =dp[i] + 1
                else:
                    dp[i + itm] = min(dp[i + itm], dp[i] + 1)

    return dp[N]
  

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

Solution (Python):
from collections import Counter
from functools import reduce
import fractions
import math
import statistics
import sys
import time
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) 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 MI(): return map(int, sys.stdin.readline().split())  
def II(): return int(sys.stdin.readline())  
def IS(): return input()  
def P(x): return print(x)
def C(x): return Counter(x)
def GCD_LIST(numbers):  
    return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers):  
    return reduce(LCM, numbers)
def LCM(m, n):
    return (m * n // fractions.gcd(m, n))









N = int(input())
dp = [INF] * 100001
dp[0], dp[1] = 0, 1
L = [1, 6, 36, 216, 1296, 7776, 46656, 9, 81, 729, 6561, 59049]

for i in range(2, 100001):
    for j in range(len(L)):
        if i-L[j] >= 0:
            dp[i] = min(dp[i-L[j]]+1, dp[i])





print(dp[N])

Solution (Python):
def sum_base10to(n, b):
    if n // b:
        return sum_base10to(n // b, b) + n % b
    return n % b


n = int(input())
i = 0
res = n
for i in range(n + 1):
    cc = sum_base10to(i, 6) + sum_base10to(n - i, 9)
    if cc < res:
        res = cc
print(res)

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

Solution (Python):
N = int(input())
l = [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 l:
        if i-j >= 0:
            dp[i] = min(dp[i],dp[i-j]+1)
print(dp[N])

Solution (Python):


import math
from collections import defaultdict
 
N = int(input())
 
memo = defaultdict(lambda: -1)
memo[0] = 0
def recursive(n):
    if memo[n] != -1:
        return memo[n]
    
    min_num_operation = n
    
    index = 0
    temp_n = n
    while temp_n > 0:
        if temp_n % 9 == 0:
            index += 1
            temp_n //= 9
        else:
            index += int(math.log(temp_n, 9))
            break
    if index > 0:
        min_num_operation = min(min_num_operation, 1 + recursive(int(n - math.pow(9, index))))
        
    index = 0
    temp_n = n
    while temp_n > 0:
        if temp_n % 6 == 0:
            index += 1
            temp_n //= 6
        else:
            index += int(math.log(temp_n, 6))
            break
    if index > 0:
        min_num_operation = min(min_num_operation, 1 + recursive(int(n - math.pow(6, index))))
        
    memo[n] = min_num_operation
    
    return min_num_operation
 
print(recursive(N))

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

ms = set([1])
i = 1
while True:
    m = 6**i
    if m > N:
        break
    ms.add(m)
    i += 1
i = 1
while True:
    m = 9**i
    if m > N:
        break
    ms.add(m)
    i += 1

dp = [0] * (N+1)
dp[0] = 0
for i in range(1, N+1):
    dp[i] = min(dp[i-m] for m in ms if i-m >= 0) + 1
print(dp[-1])

Solution (Python):
N = int(input())
INF = 10**9
dp = [INF]*(N+1)
dp[0] = 0
num6 = [6**i for i in range(1, 10)]
num9 = [9**i for i in range(1, 7)]
S = sorted([1] + num6 + num9)

for i in range(1, N+1):
    for j in S:
        if j > i:
            break
        else:
            dp[i] = min(dp[i], dp[i-j]+1)

print(dp[N])

Solution (Python):
N = int(input())
INF = 10**9
dp = [INF]*(N+1)
dp[0] = 0
num6 = [6**i for i in range(1, 10)]
num9 = [9**i for i in range(1, 7)]
S = sorted([1] + num6 + num9)

for i in range(1, N+1):
    tmp = INF
    for j in S:
        if j > i:
            break
        else:
            dp[i] = min(tmp, dp[i-j]+1)
            tmp = dp[i]

print(dp[N])