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

import sys
input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7



N = int(input())

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




for i in range(1, N+1):
    pow6 = 6
    while pow6 <= N:
        if i >= pow6:
            dp[i] = min(dp[i], dp[i-pow6]+1)

        pow6 *= 6

    pow9 = 9
    while pow9 <= N:
        if i >= pow9:
            dp[i] = min(dp[i], dp[i-pow9]+1)

        pow9 *= 9

print(dp[N])

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

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

counter_min = n

for i in range(n+1):
  counter = 0
  n_six = i
  n_nine = n-i

  
  j = 1
  while True:
    if  n_six >= 6**j:
      j += 1
    else:
      div_n = 6**(j-1)
      break
  
  while n_six > 0:
    counter += n_six // div_n
    n_six %= div_n
    div_n //= 6 
    
  
  j = 1
  while True:
    if  n_nine >= 9**j:
      j += 1
    else:
      div_n = 9**(j-1)
      break
        
  while n_nine > 0:
    counter += n_nine // div_n
    n_nine %= div_n
    div_n //= 9
  
  counter_min = min(counter, counter_min)

print(counter_min)

Solution (Python):
N = int(input())
yen6, yen9 = [1], [1]
[x for x in yen6 if yen6[-1] <= N and (yen6.append(yen6[-1]*6) or True)]
[x for x in yen9 if yen9[-1] <= N and (yen9.append(yen9[-1]*9) or True)]

yen = sorted(yen6[1:-1] + yen9[1:-1])
dp = [0]
for i in range(1, N+1):
    temp = 1 + dp[i-1]
    for y in yen:
        if i < y:
            break
        if temp > 1 + dp[i-y]:
            temp = 1 + dp[i-y]
    dp.append(temp)

print(dp[-1])

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


tup=((1,6,9,6**2,9**2,6**3,9**3,6**4,9**4,6**5,6**6,9**5))

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

INF = float('inf')

N = int(input())

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

dp = [0] * (N + 1)
for i in range(1, N + 1):
    t = INF
    for j in c:
        if i - j >= 0 and t > dp[i - j] + 1:
            t = dp[i - j] + 1
    dp[i] = t
print(dp[N])

Solution (Python):

INF = float('inf')

N = int(input())

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

dp = [INF] * (N + 1)
dp[0] = 0
for i in range(N):
    for j in c:
        if i + j <= N and dp[i + j] > dp[i] + 1:
            dp[i + j] = dp[i] + 1
print(dp[N])

Solution (Python):

INF = float('inf')

N = int(input())

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

dp = [INF] * (N + 1)
dp[0] = 0
for i in range(N):
    t0 = dp[i] + 1
    for j in c:
        t1 = i + j
        if t1 <= N and dp[t1] > t0:
            dp[t1] = t0
print(dp[N])

Solution (Python):

INF = float('inf')

N = int(input())

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

dp = [INF] * (N + 1)
dp[0] = 0
for i in range(N):
    t0 = dp[i] + 1
    for j in c:
        t1 = i + j
        if t1 <= N and dp[t1] > t0:
            dp[t1] = t0
        if t1 == N:
            break
print(dp[N])

Solution (Python):

INF = float('inf')

N = int(input())

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

dp = [INF] * (N + 1)
dp[0] = 0
for i in range(N):
    t0 = dp[i]
    for j in c:
        t1 = i + j
        if t1 <= N and dp[t1] > t0 + 1:
            dp[t1] = t0 + 1
        if t1 == N:
            break
print(dp[N])

Solution (Python):

INF = float('inf')

N = int(input())

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

dp = [INF] * (N + 1)
dp[0] = 0
for i in range(N):
    for j in c:
        t = i + j
        if t <= N and dp[t] > dp[i] + 1:
            dp[t] = dp[i] + 1
        if t == N:
            break
print(dp[N])

Solution (Python):

INF = float('inf')

N = int(input())

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

dp = [INF] * (N + 1)
dp[0] = 0
for i in range(N):
    for j in c:
        if i + j <= N:
            dp[i + j] = min(dp[i + j], dp[i] + 1)
        if i + j == N:
            break
print(dp[N])

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

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

print(dp[n])

Solution (Python):
pow_6 = [6**i for i in range(11)]
pow_9 = [9**i for i in range(11)]
N = int(input())
log = [0]*N
def ans(n):
  if n in pow_6 or n in pow_9:
    return 1
  else:
    num6 = 0
    while pow_6[num6]<n:
      num6 += 1
    num6 -= 1
    num9 = 0
    while pow_9[num9]<n:
      num9 += 1
    num9 -= 1
    if log[n-pow_6[num6]]!=0:
      x = log[n-pow_6[num6]]
    else:
      x = ans(n-pow_6[num6])
      log[n-pow_6[num6]] = x
    if log[n-pow_9[num9]]!=0:
      y = log[n-pow_9[num9]]
    else:
      y = ans(n-pow_9[num9])
      log[n-pow_9[num9]] = y
    return min(x+1,y+1)
print(ans(N))

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

def main():
    N = int(input())
    ind = [1]
    tmp = 6
    while tmp <= N:
        ind.append(tmp)
        tmp *= 6
    tmp = 9
    while tmp <= N:
        ind.append(tmp)
        tmp *= 9
    ind = sorted(ind)
    INF = int(1e9)
    dp = [INF] * (N+1)
    dp[0] = 0
    for i in range(1, N+1):
        for t in ind:
            if i - t >= 0:
                dp[i] = min(dp[i], dp[i-t]+1)
            else:
                break
    
    print(dp[N])
    


if __name__ == "__main__":
    main()

Solution (Python):

import math
import itertools

N = int(input().split()[0])


i = 0
p_6_list = []
while 6 ** i <= N:
    p_6_list.append(6 ** i)
    i += 1

p_9_list = []
i = 0
while 9 ** i <= N:
    p_9_list.append(9 ** i)
    i += 1

p_6_gen = list(itertools.product(range(0, 6), repeat=len(p_6_list)))
min_count = float("inf")

for p_6 in p_6_gen:
    x = sum([x * i for x, i in zip(p_6_list, list(p_6))])
    c = sum(list(p_6))

    if c >= min_count:
        
        
        continue

    balance = N - x
    if balance < 0:
        continue

    for y in reversed(p_9_list):
        
        y_count = balance // y
        balance -= y * y_count
        c += y_count
        if balance == 0:
            break

    min_count = min(min_count, c)

ans = min_count
print(ans)

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

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

print(ans)

Solution (Python):
ref = [6, 36, 216, 1296, 7776, 46656, 9, 81, 729, 6561, 59049]
N = int(input())
dp = list(range(N+1))
for x in ref:
	for i in range(x, N+1):
		y = dp[i-x] + 1
		if y < dp[i]:
			dp[i] = y
print(dp[N])

Solution (Python):
import sys
from collections import defaultdict, deque

input = sys.stdin.readline

def chmin(a, b):
    if a > b:
        return b
    else:
        return a

def main():
    N = int(input())
    f_inf = float('inf')
    
    MAX_N = 110000
    dp = [f_inf] * MAX_N
    dp[0] = 0
    for i in range(1, N+1):
        for j in range(N):
            pow6 = 6 ** j
            if pow6 > N:
                break
            dp[i] = min(dp[i], dp[i-pow6] + 1)
        for j in range(N):
            pow9 = 9 ** j
            if pow9 > N:
                break
            dp[i] = min(dp[i], dp[i-pow9] + 1)
    print(dp[N])


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import defaultdict, deque

input = sys.stdin.readline

def chmin(a, b):
    if a > b:
        return b
    else:
        return a

def main():
    N = int(input())
    f_inf = float('inf')
    
    MAX_N = 110000
    dp = [f_inf] * MAX_N
    dp[0] = 0
    for i in range(1, N+1):
        for j in range(N):
            pow6 = 6 ** j
            if pow6 > N:
                break
            dp[i] = chmin(dp[i], dp[i-pow6] + 1)
        for j in range(N):
            pow9 = 9 ** j
            if pow9 > N:
                break
            dp[i] = chmin(dp[i], dp[i-pow9] + 1)
    print(dp[N])


if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
dp = [-1 for i in range(n+1)]
c = [1]
for i in [6,9]:
    c += [i**j for j in range(1,10) if i**j <=10**5]

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

Solution (Python):
lists=[]
emptylists=[]
numbers=int(input())

for nums in range(numbers+3):
    
    if nums<6:
        lists.append(int(nums))
         
    elif nums==6 or nums==36 or nums==216 or nums==1296 or nums==7776 or nums==46656:
        lists.append(1)
        
    elif nums==9 or nums==81 or nums==729 or nums==6561 or nums==59049:
        lists.append(1)
        
    else:
        power6=0
        power9=0
        for k in range(7):
            if 6**(k)< nums <6**(k+1):
                power6=k
                break   
                
        for j in range(6):
            if 9**(j) <nums< 9**(j+1):
                power9=j
                break
        add=min(min(lists[nums-6**(k)]+1 for k in range(0,power6+1)),min(lists[nums-9**(j)]+1 for j in range(0,power9+1)))
        lists.append(add)
print(lists[numbers])

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

M=[0]*(N+1)
M[1]=1

for i in range(2,N+1):
  L=[M[i-1]+1]
  j=0
  while i-6**j>=0:
    L.append(M[i-6**j]+1)
    j+=1
  j=0
  while i-9**j>=0:
    L.append(M[i-9**j]+1)
    j+=1
  M[i]=min(L)


print(M[N])

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


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

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

if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
dp = [0] * (10 ** 5 + 10)
dp[0] = 0
for i in range(1, (10 ** 5) + 10):
    dp[i] = 10 ** 5 + 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())
INF = 10 ** 9
dp = [0] + [INF for _ in range(N)]
for i in range(1,N+1):
  dp[i] = dp[i-1]+1
  for j in [6,9]:
    k = j
    while (k <= i):
      dp[i] = min(dp[i],dp[i-k]+1)
      k *= j
print(dp[N])

Solution (Python):
import itertools
N = int(input())
result = 10**18
for six in itertools.product(range(6), repeat=6):
    ans = 0
    SUM = 0
    for i in range(1, 7):
        SUM += (6**i) * six[i-1]
    if SUM <= N:
        ans += sum(six)
        rem = N-SUM
        for j in range(1, 6):
            if rem >= 9**(6-j):
                ans += rem // (9**(6-j))
                rem -= (rem // (9**(6-j))) * (9**(6-j))
        ans += rem
        result = min(ans, result)
print(result)

Solution (Python):
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)

print(res)

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

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

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

print(dp[n])

Solution (Python):
from bisect import bisect_right

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


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

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

    """
    i円分を6**xxx で、　残りを９**yyyと１*zzzで構成する。これらを全通り試す
    """

    ans = N
    for i in range(N+1):
        cnt = 0
        sum_six = i
        sum_nine = N-i
        while sum_six > 0:
            idx = bisect_right(sixs, sum_six) - 1
            tmp = sum_six // sixs[idx]
            cnt += tmp
            sum_six -= tmp * sixs[idx]

        while sum_nine > 0:
            idx = bisect_right(nines, sum_nine) - 1
            tmp = sum_nine // nines[idx]
            cnt += tmp
            sum_nine -= tmp * nines[idx]

        ans = min(ans, cnt)
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
import bisect as bi

def ref(n):
  if n < 6:
    return n
  else:
    s6 = l6[bi.bisect(l6, n)-1]
    s9 = l9[bi.bisect(l9, n)-1]
    return min(n//s6 + ref(n%s6), 1+ref(n-s9))

l6 = [6**i for i in range(7)]
l9 = [9**i for i in range(6)]
print (ref(int(input())))

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


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

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



def func(n,a):
    x = 0
    while n > 0:
        x += n%a
        n //= a
    return x

def main():
    N = int(input())
    mi = N
    for i in range(N+1):
        mi = min(mi, func(i,6) + func(N-i,9))
    print(mi)
    
if __name__ == '__main__':
    main()

Solution (Python):
n=int(input())
cnt = float('inf')
for i in range(0,n+1):
  j=n-i
  temp=0
  while i:
    temp+=i%9
    i//=9
  while j:
    temp+=j%6
    j//=6
  cnt=min(temp,cnt)
    
print(cnt)

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

ls = []
k = 1
while True:
    k *= 6
    if k > n:
        break
    ls.append([k, 6])

k = 1
while True:
    k *= 9
    if k > n:
        break
    ls.append([k, 9])
ls.append([1, 1])
ls.sort(key=lambda x: x[0], reverse=True)

res = float('inf')


def dfs(x, count, index):
    global res
    if count > res:
        return
    if index == len(ls):
        if x == 0:
            res = min(res, count)
        return
    k, base = ls[index]
    m = min(x // k, max(base - 1, 5))
    if (m + 1) * k < x:
        return
    for i in range(m, -1, -1):
        dfs(x - i * k, count + i, index + 1)


dfs(n, 0, 0)
print(res)

Solution (Python):
def base(x,p):
    if int(x/p) >= 1:
        return base(int(x/p),p)+str(x%p)
    return str(x%p)
n = int(input())
c = 10**9
for i in range(n+1):
  c = min(c,sum(list(map(int,(base(i,6)+base(n-i,9))))))
print(c)

Solution (Python):
import sys

if sys.platform =='ios':
    sys.stdin=open('input_file.txt')
   
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())

xs_0 = [1]
i = 1
while True:
    if 6 ** i > n:
        break
    xs_0.append(6 ** i)
    i += 1
i = 1
while True:
    if 9 ** i > n:
        break
    xs_0.append(9 ** i)
    i += 1

xs = sorted(xs_0)

counts = [0]
for i in range(1, n+1):
    opts = [_ for _ in xs if _ <= i]
    tmps = []
    for opt in opts:
        tmp = counts[i-opt] + 1
        tmps.append(tmp)
    counts.append(min(tmps))

print(counts[-1])

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

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

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

    power_6 = 6
    while i >= power_6:
        dp[i] = min(dp[i], dp[i-power_6] + 1)
        power_6 *= 6

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

ans = dp[N]
print(ans)

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

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

Solution (Python):
N = int(input())
dp = [999999] * (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])

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

Solution (Python):
import sys
import numpy as np


N = int(input())

dp = [float('inf')]*(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):
n = int(input())
dp = [i for i in range(n+1)]
for i in range(n+1):
    power = 1
    while 6**power <= i:
        dp[i] = min(1+dp[i-6**power],dp[i])
        power += 1
    power = 1
    while 9**power <= i:
        dp[i] = min(1+dp[i-9**power],dp[i])
        power += 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())
s = [6**i for i in range(7)]
q = [9**j for j in range(6)]
m = {}

def b(n):
  if n < 6:
    return n
  elif n in m:
    return m[n]
  else:
    m_s = max(i for i in s if i<=n)
    m_q = max(j for j in q if j<=n)
    ms = n - m_s
    mq = n - m_q
    m[n] = min(b(ms)+1, b(mq)+1)
    return m[n]

print(b(n))

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

for i in range(N + 1):
    count = 0
    n_f = N - i
    n_s = i
    while n_f != 0:
        count += n_f % 6
        n_f //= 6
    while n_s != 0:
        count += n_s % 9
        n_s //= 9
    ans.append(count)

print(min(ans))

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

A = [1]
tmp = 6
while tmp < 10**5:
    A.append(tmp)
    tmp *= 6
tmp = 9
while tmp < 10**5:
    A.append(tmp)
    tmp *= 9

Ans = [float("inf")] * (10**5+1)
Ans[0] = 0

for i in range(1,10**5+1):
    tmp = float("inf")
    for j in A:
        if i-j >= 0:
            if tmp > Ans[i-j] + 1:
                tmp = Ans[i-j] + 1
    Ans[i] = tmp
print(Ans[N])

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

res = float('inf')
for i in range(0, 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)
print(res)

Solution (Python):
N = int(input())
li=[6,9,36,81,216,729,1296,6561,7776,46656,59049]
dp = [i for i in range(100010)]
for a in li:
    for x in range(a,N+1):
        dp[x] = min(dp[x],dp[x-a]+1)
print(dp[N])

Solution (Python):
from collections import Counter,defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

n = inp()
dp = [mod for i in range(2*n)]
dp[0] = 0
p_6 = []
p_9 = []
tmp = 1
while tmp <= n:
    p_6.append(tmp)
    tmp *= 6
tmp = 1
while tmp <= n:
    p_9.append(tmp)
    tmp *= 9


for i in range(n):
    for j in p_6:
        if i+j <= n:
            dp[i+j] = min(dp[i+j],dp[i]+1)
    for k in p_9:
        if i+k <= n:
            dp[i+k] = min(dp[i+k],dp[i]+1)

print(dp[n])

Solution (Python):

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

Solution (Python):
N=int(input())
ls=[i for i in range(N+1)]
cand=[1]
x=6
while (x<=N):
  cand.append(x)
  x*=6
x=9
while (x<=N):
  cand.append(x)
  x*=9
cand.sort()
for i in range(1,N+1):
  y=N
  for e in cand:
    if e>i: break
    if ls[i-e]<y:y=ls[i-e]
  ls[i]=y+1
print(ls[N])

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate
import sys



def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LIM(): return list(map(lambda x:int(x) - 1, sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def LIRM(n): return [LIM() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 1000000007

n = I()




def recur(c, i):
    if c < i:
        return c
    ret = 1
    while ret * i <= c:
        ret *= i
    else:
        return min((recur(c - ret, 6) + 1), (recur(c - ret, 9) + 1))



print(min(recur(n, 6), recur(n, 9)))

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

answer = N
for i in range(N+1):
    count = 0
    t = i
    
    while t:
        count += t%6
        t //= 6
    t = N-i
    while t:
        count += t%9
        t //= 9
    answer = min(answer, count)
print(answer)

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

list_6_9 = [1]

tmp = 6
while tmp < 100000:
  list_6_9.append(tmp)
  tmp *= 6

tmp = 9
while tmp < 100000:
  list_6_9.append(tmp)
  tmp *= 9


cnt_draw_list = [100000] * (N+1)
cnt_draw_list[0] = 0



for n in range(1,N+1):
  for draw_cash in list_6_9:
    tmp = n - draw_cash
    if tmp >= 0:
      cnt_draw_list[n] = min(cnt_draw_list[n],cnt_draw_list[tmp] + 1)


print(cnt_draw_list[N])

Solution (Python):
import sys
from collections import deque
from functools import reduce
import copy
import math


sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def solve(inputs):
    n = int(inputs[0])
    LIMIT = 100000
    sixs = [6]
    nines = [9]
    while sixs[-1] <= LIMIT:
        sixs.append(6 * sixs[-1])
    sixs.pop()
    while nines[-1] <= LIMIT:
        nines.append(9 * nines[-1])
    nines.pop()

    choises = [1]
    choises.extend(sixs)
    choises.extend(nines)

    
    dp = [0]

    for i in range(1, n+1):
        candidates = []
        for c in choises:
            if i - c >= 0:
                candidates.append(dp[i-c] + 1)
        dp.append(min(candidates))

    return dp[-1]


def string_to_int(string):
    return list(map(int, string.split()))


if __name__ == "__main__":
    ret = solve(inputs(1))
    print(ret)

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

dp = [0]*(N+10)

for n in range(1, N+1):
  dp[n] = 100000
  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):

INF = float('inf')
n = int(input())
a = [1]
i = 6
while i <= n:
  a.append(i)
  i *= 6
i = 9
while i <= n:
  a.append(i)
  i *= 9
t = [0] * (n + 1)
for i in range(1, n + 1):
  k = INF
  for j in a:
    if i - j >= 0 and k > t[i - j] + 1:
      k = t[i - j] + 1
  t[i] = k
print(t[n])

Solution (Python):
import queue
N = int(input())
M = [-1]*(N+1)
M[0] = 0
q = queue.Queue()
q.put(0)
while not(q.empty()):
  c = q.get()
  i = M[c]
  for n in range(1, 20):
    s = c+6**n
    if s <= N and (M[s] < 0 or i+1 < M[s]):
      M[s] = i+1
      q.put(s)
  for n in range(1, 20):
    s = c+9**n
    if s <= N and (M[s] < 0 or i+1 < M[s]):
      M[s] = i+1
      q.put(s)

for i in reversed(range(0, N+1)):
  if not(M[i] < 0):
    r = M[i]+(N-i)
    break
print(r)

Solution (Python):
n = int(input())
dp = [float('inf')]*(n+1)
dp[0] = 0
for i in range(n+1):
    power = 1
    
    while power <= i:
        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())
ans=N
for i in range(N+1):
    element_cnt=0
    t=i
    '''Nを6の累乗で処理する部分(i)と9の累乗で処理する部分(j)に分ける
    ある数(i)を6で割った余りは6のゼロ乗の要素がいくつ含まれるかを示す
    ある数の6の商をさらに6で割った余りは、ある数に6の1乗がいくつ含まれるかを示す
    ある数の6の商の6の商をさらに6で割った余りは、ある数に6の2乗がいくつ含まれるかを示す
    したがって、ある数を6で割って余りと商を順に処理すれば6の累乗の要素がどれだけあるかがわかる。
    最終的に商がゼロになるまで繰り返す
    '''
    while t>0:
        element_cnt+=t%6
        t//=6
    j=N-i
    while j>0:
        element_cnt+=j%9
        j//=9
    ans = min(ans,element_cnt)
print(ans)

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


Withdr = [1] + [6**i for i in range(1, 7)] + [9**i for i in range(1,6)]
INF = 100010
dp = [INF]*159050
dp[0] = 0


for j in range(n + 1):
    
    for WithdrOrder in Withdr:
        
        dp[j + WithdrOrder] = min(dp[j + WithdrOrder], dp[j] + 1)
print(dp[n])

Solution (Python):
import sys
from collections import deque
from collections import  Counter
import statistics
import math

stdin = sys.stdin

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

n = ni()

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

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

INF = 1000000

N = int(input())
m = [INF] * 100001
m[0] = 0
m[1] = 1

def f(N):
    if m[N] != INF:
        return m[N]

    tmp = INF

    tmp = min(f(N - 1) + 1, tmp)

    a = 6
    while a <= N:
        tmp = min(f(N - a) + 1, tmp)
        a *= 6

    a = 9
    while a <= N:
        tmp = min(f(N - a) + 1, tmp)
        a *= 9

    m[N] = tmp
    return tmp

print(f(N))

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

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

print(score)

Solution (Python):
def nsin(X,n):
    if(int(X/n)):
        return nsin(int(X/n),n)+str(X%n)
    return str(X)

N = int(input())
score = N
for i in range(N+1):
    score = min(score,sum(map(int,nsin(i,6)+nsin(N-i,9))))
print(score)

Solution (Python):





N = int(input())

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

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

print(dp[N])


"""

N = int(input())

money = [1]
for i in range(1, 100):
    if 6**i <= N:
        money.append(6**i)
    if 9**i <= N:
        money.append(9**i)
    if 6**i > N and 9**i > N:
        break
money.sort()
money.reverse()

zannkinn = N
ans = 0
for i in range(len(money)):
    ans += zannkinn//money[i]
    zannkinn = zannkinn % money[i]
    if zannkinn == 0:
        break

print(ans)
"""

Solution (Python):
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
from itertools import permutations,groupby
import sys
import bisect
import string
alp=string.ascii_lowercase
sys.setrecursionlimit(10**6)
def SI():
    return input().split()
def MI():
    return map(int,input().split())
def I():
    return int(input())
def LI():
    return [int(i) for i in input().split()]
YN=['Yes','No']
mo=10**9+7



n=I()
p6=[6**i for i in range(0,7)][::-1]
p9=[9**i for i in range(0,7)][::-1]
ans=n

for i in range(n+1):
    m=0
    n6=i
    n9=n-i
    for j in p6:
        m+=n6//j
        n6%=j
    for j in p9:
        m+=n9//j
        n9%=j
    ans=min(ans,m)
print(ans)

Solution (Python):
n = int(input())
a = [1] + [6 ** i for i in range(1, 7)] + [9 ** i for i in range(1, 6)]

INF = 10 ** 5
dp = [INF] * 200000
dp[0] = 0

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

print(dp[n])

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

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

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

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

print(dp[N])

Solution (Python):
N = int(input())
dp = [float("inf") for i in range(N+100)]
dp[0] = 0 
for i in range(1,N+50):
    r = 1 
    dp[i] = min(dp[i],dp[i-r]+1)
    p = 6 
    while (i>=p) :
        dp[i] = min(dp[i],dp[i-p]+1)
        p *= 6
    q = 9 
    while (i>=q) :
        dp[i] = min(dp[i],dp[i-q]+1)
        q *= 9
print(dp[N])

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

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

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

Solution (Python):

N = int(input())

INF = 10 ** 5 + 1

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

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

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

print(dp[N])

Solution (Python):

N = int(input())

INF = 10 ** 5 + 1

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

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

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

print(dp[N])