Problem:
 Score : 300 points    Problem Statement To make it difficult to withdraw money, a certain bank allows its customers to withdraw only one of the following amounts in one operation:    1 yen (the currency of Japan)    6 yen, 6^2(=36) yen, 6^3(=216) yen, ...    9 yen, 9^2(=81) yen, 9^3(=729) yen, ...    At least how many operations are required to withdraw exactly N yen in total?  It is not allowed to re-deposit the money you withdrew.      Constraints  1 \leq N \leq 100000  N is an integer.         Input Input is given from Standard Input in the following format:  N       Output If at least x operations are required to withdraw exactly N yen in total, print x .        Sample Input 1 127      Sample Output 1 4  By withdrawing 1 yen, 9 yen, 36(=6^2) yen and 81(=9^2) yen, we can withdraw 127 yen in four operations.       Sample Input 2 3      Sample Output 2 3  By withdrawing 1 yen three times, we can withdraw 3 yen in three operations.       Sample Input 3 44852      Sample Output 3 16

Solution (Python):
from math import log
n = int(input())










nums = [1]
i = 1
num = 1
while num <= n:
    num = 6 ** i
    nums.append(num)
    i += 1
i = 1
num = 1
while num <= n:
    num = 9 ** i
    nums.append(num)
    i += 1


dp = [float('inf')] * (n+1)
for num in nums:
    for i in range(1, n+1):
        if i == num:
            dp[i] = 1
        elif i >= num:
            dp[i] = min(dp[i], dp[i-num]+1)
print(dp[n])

Solution (Python):
from math import log
n = int(input())










nums = [1]
i = 1
num = 1
while num <= n:
    num = 6 ** i
    nums.append(num)
    i += 1
i = 1
num = 1
while num <= n:
    num = 9 ** i
    nums.append(num)
    i += 1


dp = [float('inf')] * (n+1)
dp[0] = 0
for num in nums:
    for i in range(1, n+1):
        if i >= num:
            dp[i] = min(dp[i], dp[i-num]+1)
print(dp[n])

Solution (Python):
bank = [1]
N = int(input())
for i in range(20):
    if 100000 >= 6**i:
        bank.append(6**i)
    if 100000 >= 9**i:
        bank.append(9**i)

dp = [[10**10]*(N+1) for _ in range(len(bank)+1)]

dp[0][0] = 0

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

Solution (Python):
wt = int(input())
w = [1]
for i in range(7):
    w.append(6 ** (i + 1))
for i in range(5):
    w.append(9 ** (i + 1))
n = len(w)
dp = [[float("inf") for i in range(wt + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(n):
    for j in range(wt + 1):
        if j >= w[i]:
            dp[i + 1][j] = min(dp[i + 1][j - w[i]] + 1, dp[i][j])
        else:
            dp[i + 1][j] = dp[i][j]
print(dp[n][wt])

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

l9 = [9**(i+1) for i in range(6)]
l6 = [6**(i+1) for i in range(6)]
l9.sort(reverse=True)
l6.sort(reverse=True)
ans = n
for i in range(n):
    n9 = i+1
    n6 = n-n9
    tmp = 0

    while (n9 >= 9):
        for t in l9:
            if t <= n9:
                n9 -= t
                tmp += 1
                break
    n6 += n9
    while (n6 >= 6):
        for t in l6:
            if t <= n6:
                n6 -= t
                tmp += 1
                break
    ans = min(ans, tmp+n6)
print(ans)

Solution (Python):
import os
import sys

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

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7




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

s = {0}
ans = 0
while True:
    ns = set()
    for n in s:
        d = 0
        while n + 6 ** d <= N:
            ns.add(n + 6 ** d)
            d += 1
        d = 0
        while n + 9 ** d <= N:
            ns.add(n + 9 ** d)
            d += 1
    ans += 1
    if N in ns:
        break
    s = ns
print(ans)

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

ans = 10**5
for a in range(0, N+1):
	cnt = 0
	t = 1
	for i in range(7):
		cnt += (a//t)%6
		t *= 6
	t = 1
	for i in range(6):
		cnt += ((N-a)//t)%9
		t *= 9
	ans = min(ans, cnt)
print(ans)

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

can.add(1)
i=1
ans=0
while True:
  ans=6**i
  if ans<=100000:
    can.add(ans)
    i+=1
  else:
    break
    
j=1
ans=0
while True:
  ans=9**j
  if ans<=100000:
    can.add(ans)
    j+=1
  else:
    break

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

for k in range(2,N+1):
  mini=10000000
  for item in can:
    if k-item>=0:
      mini=min(mini, dp[k-item]+1)
  dp[k]=mini

print(dp[-1])

Solution (Python):

import sys
import math
import os
import itertools

class cin():
    def int():
        return int(sys.stdin.readline().rstrip())
    def string():
        return sys.stdin.readline().rstrip()
    def mapInt():
        return [int(x) for x in cin.string().split()]
    def stringList(n):
        return [input() for i in range(n)]

class Util():
    def round_up(a,b):
        return -(-a // b)
    def toUpperMultiple(a,x):
        return Util.round_up(a,x) * x
    def toLowerMultiple(a,x):
        return (a // x) * x

N = cin.int()
dp = [0] * (N + 1)
dp[0] = 0
for i in range(1,N + 1):
    dp[i] = i
    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):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()
  
  l=[1]
  for i in range(1,20):
    a=6**i
    if a<=n:
      l.append(a)
    b=9**i
    if b<=n:
      l.append(b)

  l.sort()

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

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

  return dp[n]


print(main())

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

prices = [1]
idx = 1
while 6 ** idx <= N:
    prices.append(6 ** idx)
    idx += 1
idx = 1
while 9 ** idx <= N:
    prices.append(9 ** idx)
    idx += 1

prices.sort()

dp = [float('inf') for _ in range(N + 1)]
dp[0] = 0
for n in range(N + 1):
    for price in prices:
        dp[n] = min(dp[n], dp[n - price] + 1)

print(dp[-1])

Solution (Python):
N = int(input())
dp = [float('inf') for i in range(N+1)]
dp[0] = 0
if N >= 6:
    dp[6] = 1
def below_power(n,a):
    "n以下になるa**xのxの最大値を求める"
    x = 0
    while n >= a**x:
        x += 1
    return x-1
nine = below_power(N,9)
six = below_power(N,6)
for i in range(six,0,-1):
    for j in range(N+1):
        if j - 6**i >= 0:
            dp[j] = min(dp[j],dp[j-6**i]+1)
        if j - 9**i >= 0:
            dp[j] = min(dp[j],dp[j-9**i]+1)       
ans = dp[N]
for i in range(1,min(N+1,6)):
    ans = min(ans,dp[N-i]+i)
print(ans)

Solution (Python):
N = int(input())
dp = [float('inf') for i in range(N+1)]
dp[0] = 0
if N >= 6:
    dp[6] = 1
def below_power(n,a):
    "n以下になるa**xのxの最大値を求める"
    x = 0
    while n >= a**x:
        x += 1
    return x-1
nine = below_power(N,9)
six = below_power(N,6)
for i in range(six,0,-1):
    for j in range(N+1):
        if j - 6**i >= 0:
            dp[j] = min(dp[j],dp[j-6**i]+1)
for i in range(nine,0,-1):
    for j in range(N+1):
        if j - 9**i >= 0:
            dp[j] = min(dp[j],dp[j-9**i]+1)       
ans = dp[N]
for i in range(1,min(N+1,6)):
    ans = min(ans,dp[N-i]+i)
print(ans)

Solution (Python):
N=int(input())
import itertools
A=list(itertools.product([0,1,2,3,4,5],repeat=6))
ans=10**6
cnt=0
for i in A:
  a=6*i[0]+36*i[1]+216*i[2]+1296*i[3]+7776*i[4]+46656*i[5]
  if a<=N:
    b=N-a
    cnt=sum(i)
    for j in range(6,0,-1):
      d=b//(9**j)
      b-=(9**j)*d
      cnt+=d
    cnt+=b
    ans=min(cnt,ans)
print(ans)

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

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

n = int(input())

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

p = int(math.log(n, 6))
q = int(math.log(n, 9))

for i in range(1, n + 1):
    dp[i] = chmin(dp[i], dp[i - 1] + 1)
    for j in range(1, p + 2):
        if i - 6 ** j >= 0:
            dp[i] = chmin(dp[i], dp[i - 6 ** j] + 1)
        else:
            break
    for k in range(1, q + 2):
        if i - 9 ** k >= 0:
            dp[i] = chmin(dp[i], dp[i - 9 ** k] + 1)
        else:
            break

print(dp[n])

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
N = int(input())
memo = [-1]*(N+1)
def rec(n):
    if n == 0:
        return 0
    if memo[n] != -1:
        return memo[n]
    res = n
    m = 1
    while m <= n:
        res = min(res,rec(n-m)+1)
        m *= 6
    m = 1
    while m <= n:
        res = min(res,rec(n-m)+1)
        m *= 9
    memo[n] = res
    return memo[n]

print(rec(N))

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

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

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

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

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

    print(dp[N])


main()

Solution (Python):
import sys

input = sys.stdin.readline


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

    dp = [0] * (10 ** 5 + 1)
    dp[1] = 1

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


    for i in range(2, 10 ** 5 + 1):
        tmp = []
        for v in x:
            if i >= v:
                tmp.append(dp[i - v] + 1)

        dp[i] = min(tmp)

    print(dp[N])


if __name__ == '__main__':
    main()

Solution (Python):
import itertools

N = int(input())

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

ans = float("inf")
for combi in itertools.product([i for i in range(6)], repeat=6):
    
    count = sum(combi)
    six_sum = sum([a*b for a, b in zip(six_list, combi)])
    if N < six_sum:
        continue
    rest = N - six_sum
    for nine in reversed(nine_list):
        if nine > rest:
            continue
        count += rest // nine
        rest = rest % nine
    ans = min(ans, count)

print(ans)

Solution (Python):
from math import log

def n_number(num:int , n:int)->list:
    
    ans = []
    while num > 0:
        ans.append(num%n)
        num = num // n
    return ans[::-1]


def main():
    N = int(input())
    ans = N
    for six in range(N + 1):
        ans = min(ans,sum(n_number(six,6)) + sum(n_number(N - six,9)))
    print(ans)
    return
        
if __name__ == "__main__":
    main()

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)
    six = 6
    while i + six <= n:
        dp[i + six] = min(dp[i+six], dp[i] + 1)
        six *= 6
    nine = 9
    while i + nine <= n:
        dp[i + nine] = min(dp[i+nine], dp[i] + 1)
        nine *= 9
print(dp[-1])

Solution (Python):
def f(num, base):
    
    ret = 1
    while ret <= num:
        ret *= base
    return ret // base


def main():
    N = {int(input())}
    ans = 0
    while (all(N)):
        N = {x - f(x, 6) for x in N} | {x - f(x, 9) for x in N}
        ans += 1
    print(ans)
    return


main()

Solution (Python):
def f(num, base):
    
    ret = 1
    while ret <= num:
        ret *= base
    return ret // base


def main():
    N = int(input())
    st = {N}
    ans = 0
    while (all(st)):
        st = {x - f(x, 6) for x in st} | {x - f(x, 9) for x in st}
        ans += 1
    print(ans)
    return


main()

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

for i in range(1, 7):
    a.append(pow(6, i))

for i in range(1, 6):
    a.append(pow(9, i))

dp = [0] * 100001
for i in range(1, n+1):
    m = dp[i-1] + 1
    for v in a:
        if i - v < 0:
            continue
        if m > dp[i-v] + 1:
            m = dp[i-v] + 1
    dp[i] = m

print(dp[n])

Solution (Python):

from itertools import product, permutations, combinations
N=int(input())
dp = [N for i 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):
N=int(input())
def money(n):
    dp=[n]*(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
    return dp[n]
print(money(N))

Solution (Python):
N = int(input())
memo = [-1]*(N+1)
import sys
sys.setrecursionlimit(10**8)
def rec(n):
    if n == 0:return 0
    if memo[n] != -1:return memo[n]

    res = float('inf')

    pow6 = 1
    while pow6 <= n:
        res = min(res,rec(n-pow6)+1)
        pow6 *= 6

    pow9 = 1
    while pow9 <= n:
        res = min(res,rec(n-pow9)+1)
        pow9 *= 9

    memo[n] = res
    return memo[n]

print(rec(N))

Solution (Python):
"""
import bisect
N = int(input())
ans = 0
hikidashi_list = [1, 6, 9]
tmp_6 = 6
tmp_9 = 9
while tmp_6 < N:
    tmp_6 *= 6
    hikidashi_list.append(tmp_6)

while tmp_9 < N:
    tmp_9 *= 9
    hikidashi_list.append(tmp_9)

hikidashi_list.sort()
while N > 0:
    now = bisect.bisect_left(hikidashi_list, N)
    if now == 0:
        N -= 1
    else:
        N -= hikidashi_list[now-1]
    ans += 1
print(ans)



"""


N = int(input())
dp = [100000000] * (N+1)
dp[0] = 0
dp[1] = 1
ans = 0
hikidashi_list = [1, 6, 9]
tmp_6 = 6
tmp_9 = 9
while tmp_6 < N:
    tmp_6 *= 6
    hikidashi_list.append(tmp_6)

while tmp_9 < N:
    tmp_9 *= 9
    hikidashi_list.append(tmp_9)
hikidashi_list.sort()
for i in range(N+1):
    for k in hikidashi_list:
        if i + k > N :
            break
        dp[i+k] = min(dp[i] + 1, dp[i+k])

print(dp[N])

Solution (Python):
"""
import bisect
N = int(input())
ans = 0
hikidashi_list = [1, 6, 9]
tmp_6 = 6
tmp_9 = 9
while tmp_6 < N:
    tmp_6 *= 6
    hikidashi_list.append(tmp_6)

while tmp_9 < N:
    tmp_9 *= 9
    hikidashi_list.append(tmp_9)

hikidashi_list.sort()
while N > 0:
    now = bisect.bisect_left(hikidashi_list, N)
    if now == 0:
        N -= 1
    else:
        N -= hikidashi_list[now-1]
    ans += 1
print(ans)



"""


N = int(input())
dp = [100000000] * (N+1)
dp[0] = 0
dp[1] = 1
ans = 0
hikidashi_list = [1, 6, 9]
tmp_6 = 6
tmp_9 = 9
while tmp_6 < N:
    tmp_6 *= 6
    hikidashi_list.append(tmp_6)

while tmp_9 < N:
    tmp_9 *= 9
    hikidashi_list.append(tmp_9)
hikidashi_list.sort()
for i in range(N+1):
    for k in hikidashi_list:
        if i + k > N :
            break
        dp[i+k] = min(dp[i] + 1, dp[i+k])

print(dp[N])

Solution (Python):

N = int(input())

INF = 1<<60
dp = [INF]*(N+1)
dp[0] = 0


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

print(dp[N])

Solution (Python):

N = int(input())

INF = 1<<60
dp = [INF]*(N+1)
dp[0] = 0


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

print(dp[N])

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

dp = [float('INF')] * (n+1)
dp[0] = 0

pow6 = []
i = 1
while 6**i <= 10**5:
    pow6.append(6**i)
    i += 1
pow9 = []
i = 1
while 9**i <= 10**5:
    pow9.append(9**i)
    i += 1
money = [1] + pow6 + pow9

for i in range(n):
    for k in money:
        if n >= i+k >= 0:
            dp[i+k] = min(dp[i+k], dp[i] + 1)

print(dp[-1])

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

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

Solution (Python):
N = int(input())
lis = []
six = 6
nine = 9
while six<=100000:
    lis.append(six)
    six *= 6
while nine<=100000:
    lis.append(nine)
    nine *= 9
lis.sort()
dp = [0]
for i in range(1,N+1):
    tmp = dp[i-1]+1
    for l in lis:
        if i-l<0:
            break
        tmp = min(tmp,dp[i-l]+1)
    dp.append(tmp)
print(dp[N])

Solution (Python):
N = int(input())
lis = []
six = 6
nine = 9
while six<=100000:
    lis.append(six)
    six *= 6
while nine<=100000:
    lis.append(nine)
    nine *= 9
lis.sort()
dp = [0]
for i in range(1,N+1):
    tmp = dp[i-1]+1
    for l in lis:
        if i-l<0:
            break
        tmp = min(tmp,dp[i-l]+1)
    dp.append(tmp)
print(dp[N])

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

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

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

for i in range(N+1):
  for p in pattern:
    if i + p <= N:
      dp[i+p] = min(dp[i+p], dp[i]+1)

print(dp[N])

Solution (Python):

n = int(input())
dp = [10**9]*(n+1)
L = [6**i for i in range(1,7)]
L += [9**i for i in range(1,6)]

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):
from _collections import deque
from _ast import Num


def parser():
    while 1:
        data = list(input().split(' '))
        for number in data:
            if len(number) > 0:
                yield (number)


input_parser = parser()


def gw():
    global input_parser
    return next(input_parser)


def gi():
    data = gw()
    return int(data)


MOD = int(1e9 + 7)

import numpy
from collections import deque
from math import sqrt
from math import floor


"""
need to consider the case that ticket is not enough to lower everything
"""
N = gi()
cs = []
cs.append(1)
b6 = 6
while (b6 <= 1e5):
    cs.append(b6)
    b6 *= 6
b9 = 9
while (b9 <= 1e5):
    cs.append(b9)
    b9 *= 9
ans = [N] * (N + 1)
ans[0] = 0

for i in range(1, N + 1):
    for v in cs:
        if i >= v:
            ans[i] = min(ans[i], ans[i - v] + 1)

print(ans[N])

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

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

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

f_inf = float('inf')
dp = [f_inf] * (MAXN+n)

dp[0] = 0

for i in range(1, n+2):
    for j in range(7):
        dp[i] = min(dp[i], dp[i-pow(6, j)]+1)
    for k in range(6):
        dp[i] = min(dp[i], dp[i-pow(9, k)]+1)

print(dp[n])

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

f_inf = float('inf')
dp = [f_inf] * (MAXN+n)

dp[0] = 0

for i in range(1, n+2):
    for j in range(7):
        dp[i] = min(dp[i], dp[i-pow(6, j)]+1)
    for k in range(6):
        dp[i] = min(dp[i], dp[i-pow(9, k)]+1)

print(dp[n])

Solution (Python):










def full(shape, full_value):
    if isinstance(shape, tuple):
        sha = shape[::-1]
        ret = [full_value] * sha[0]
        for s in sha[1:]:
            ret = [ret.copy() for i in range(s)]
        return ret

        if len(shape) == 2:
            return [[full_value] * shape[1] for _ in range(shape[0])]
    else:
        return [full_value] * shape


INF = 10**9

N = int(input())
candi = [1]
i = 1
while 6 ** i <= N:
    candi.append(6**i)
    i += 1

i = 1
while 9 ** i <= N:
    candi.append(9**i)
    i += 1

candi.sort()

dp = full(N + 1, INF)
dp[0] = 0  

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

print(dp[-1])

Solution (Python):










def full(shape, full_value):
    if isinstance(shape, tuple):
        sha = shape[::-1]
        ret = [full_value] * sha[0]
        for s in sha[1:]:
            ret = [ret.copy() for i in range(s)]
        return ret

        if len(shape) == 2:
            return [[full_value] * shape[1] for _ in range(shape[0])]
    else:
        return [full_value] * shape


INF = 10**9

N = int(input())
candi = [1]
i = 1
while 6 ** i <= N:
    candi.append(6**i)
    i += 1

i = 1
while 9 ** i <= N:
    candi.append(9**i)
    i += 1

candi.sort()

dp = full(N + 1, INF)
dp[0] = 0  

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

print(dp[-1])

Solution (Python):
n = int(input())
dp = [[False for _ in range(n + 5)] for __ in range(100)]
dp[0][0] = True

for i in range(100):
    for m in range(n):
        if dp[i][m] == True:
            for j in range(10):
                if m + 6 ** j > n: break
                dp[i + 1][m + 6 ** j] = True
            for j in range(10):
                if m + 9 ** j > n: break
                dp[i + 1][m + 9 ** j] = True
    if dp[i + 1][n]:
        print(i + 1)
        break

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

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

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

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

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

Solution (Python):
import sys
from collections import defaultdict, deque
import bisect
from heapq import *
from math import factorial
sys.setrecursionlimit(200000)
input = sys.stdin.readline

N, = map(int, input().split())







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

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

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

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

print(dp[len(m)][N])

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


def fn(n, a):
    res = 0
    while n > 0:
        res += n % a
        n = n // a
    return res


ans = 1 << 60
for i in range(0, N+1):
    tmp = fn(i, 6) + fn(N - i, 9)
    ans = min(ans, tmp)

print(ans)

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

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

    dp = [float('inf')] * (N+1)
    dp[0] = 0

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

        k = 0
        while 9 ** k + i <= N:
            dp[9 ** k + i] = min(dp[9**k+i], dp[i] + 1)
            k += 1
        
        dp[i+1] = min(dp[i+1], dp[i] + 1)

    print(dp[-1])
if __name__ == '__main__':
    solve()

Solution (Python):
def chmin(a, b):
    if a < b:
        return (a)
    else:
        return (b)

ans = [100000000] * 100001
can = [1,6,9,36,81,216,729,1296,6561,7776, 46656, 59049]
ans[1] = 1
ans[6] = 1
ans[36] = 1
ans[216] = 1
ans[1296] = 1
ans[7776] = 1
ans[46656] = 1
ans[9] = 1
ans[81] = 1
ans[729] = 1
ans[6561] = 1
ans[59049] = 1

for i in range(2,100001):
    for j in can:
        if i > j:
            ans[i] = chmin(ans[i], ans[i-j]+1)

N = int(input())
print(ans[N])

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

max6 = n//6

ans = 10**9

def count_func(m,k): 
    if m<k:
        return m
    for i in range(1,8):
        if m<k**i:
            return count_func(m-k**(i-1),k)+1

    

for i in range(max6+1):
    ct6 = count_func(i,6)
    ct9 = count_func((n-6*i)//9,9)
    am = n-(i*6+((n-6*i)//9)*9)
    ans = min(ans,ct6+ct9+am)
    
print(ans)

Solution (Python):
import sys

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

def main():
    bit6 = [0] * 8
    bit9 = [0] * 7
    b = n
    for i in range(5, -1, -1):
        q, r = divmod(b, 9 ** i)
        bit9[i] = q
        b = r

    res = sum(bit6) + sum(bit9)

    for _ in range(n):
        i = 0
        while True:
            bit6[i] += 1
            if bit6[i] == 6:
                bit6[i] = 0
                i += 1
            else:
                break

        i = 0
        while True:
            bit9[i] -= 1
            if bit9[i] == -1:
                bit9[i] = 8
                i += 1
            else:
                break        

        res = min(res, sum(bit6) + sum(bit9))

    return res

if __name__ == '__main__':
    ans = main()
    print(ans)

Solution (Python):
import sys
from math import log, floor

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

def main():
    cand = set()
    for i in range(floor(log(n, 6)) + 1):
        if 6 ** i <= n:
            cand.add(6 ** i)
        if 9 ** i <= n:
            cand.add(9 ** i)
    cand = sorted(cand)

    res = set([0])
    cnt = 0
    while True:
        nex = set()
        for val in res:
            for c in cand:
                if val + c <= n:
                    nex.add(val + c)
                else:
                    break
        cnt += 1
        if n in nex:
            return cnt
        res = nex
    
if __name__ == '__main__':
    ans = main()
    print(ans)

Solution (Python):

import sys
from itertools import product

def solve(N: int):
    nine = [9**i for i in range(5,0,-1)]
    six = [6**i for i in range(6,0,-1,)]
    answer = 10**6

    for six_bit in product([0,1,2,3,4,5],repeat = 6):
        tmp = 0
        for i in range(6):
            tmp += six[i]*six_bit[i]

        if tmp > N:
            continue
        
        count = sum(six_bit)
        cur = N-tmp
        for i in range(5):
            syou = cur//nine[i]
            cur%=nine[i]
            count += syou
        else:
            answer = min(answer,count+cur)
    print(answer)
    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())

ans = 100000

def sum_digits(n,m):
    r = 0
    while n:
        r, n = r + n % m, n // m
    return r
 
for i in range(N+1):
    ans = min(ans, sum_digits(i,6)+sum_digits(N-i,9))
 
print(ans)

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

ans = 100000

def sum_digits(n,m):
    r = 0
    while n:
        r, n = r + n % m, n // m
    return r
 
for i in range(N+1):
    ans = min(ans, sum_digits(i,6)+sum_digits(N-i,9))
 
print(ans)

Solution (Python):
N=int(input())
def func(n,a):
    cnt=0
    while n!=0:
        r=n%a
        n=(n-r)//a
        cnt+=r
    return cnt

ans=N
for i in range(N+1):
    tmp=func(i,6)+func(N-i,9)
    ans=min(ans,tmp)
print(ans)

Solution (Python):
import heapq
N=int(input())
N_max=100000

d=set()
n=1
while n<=N_max:
    d.add(n)
    n*=6
n=1
while n<=N_max:
    d.add(n)
    n*=9

dp=[N_max+1 for _ in range(N_max+1)]
dp[0]=0
for i in range(1,N_max+1):
    for n in d:
        if i>=n:
            dp[i]=min(dp[i],dp[i-n]+1)

print(dp[N])

Solution (Python):
N = int(input())
List9 = [9 ** i for i in range(1,7) if 9 ** i <= N]
List6 = [6 ** i for i in range(1,7) if 6 ** i <= N]

def recur(n,con):
  if n == 0:
    return con

  elif n < 6:
    return con + n
    
  elif n < 9:
    return con + (n - 5)

  else:
    max9 = [i for i in List9 if i <= n][-1]
    max6 = [i for i in List6 if i <= n][-1]
    
    return min(recur(n - max9,con + 1),recur(n - max6,con + 1))
    
print(recur(N,0))

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

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

print(ans)

Solution (Python):
def main():
    n = int(input())
    dp = [n] * 200000
    dp[0] = 0
    
    for i in range(n):
        p6 = 1
        while True:
            if i + p6 > n:
                break
            dp[i + p6] = min(dp[i + p6], dp[i] + 1)
            p6 *= 6
        p9 = 1
        while True:
            if i + p9 > n:
                break
            dp[i + p9] = min(dp[i + p9], dp[i] + 1)
            p9 *= 9
    print(dp[n])


if __name__ == "__main__":
    main()

Solution (Python):
n = int(input())
a = [i for i in range(n+1)]

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

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

print(a[n])

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

memo = [-1] * 110000


def withdrawals(n):
    if n == 0:  
        return 0
    if memo[n] != -1:  
        return memo[n]
    res = n  
    pow6 = 1
    while pow6 <= n:
        res = min(res, withdrawals(n - pow6) + 1)
        pow6 *= 6

    pow9 = 1
    while pow9 <= n:
        res = min(res, withdrawals(n - pow9) + 1)
        pow9 *= 9

    memo[n] = res
    return res


N = int(input())
withdrawals(N)
print(memo[N])

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

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