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

Solution (Python):
def ds(a, b):
	return a if a<b else ds(a//b,b)+a%b
n = int(input())
print(min([ds(i,6)+ds(n-i,9) for i in range(n+1)]))

Solution (Python):
def ds(a, b):
	return a if a<b else ds(a//b,b)+a%b
ans = float('inf')
n = int(input())
for i in range(n+1):
	ans = min(ans,ds(i,6)+ds(n-i,9))
print(ans)

Solution (Python):
N = int(input())
res = 1e6

for i in range(0, N + 1):
    cc = 0
    t = i
    while t > 0:
        cc += t % 6
        t //= 6
    t = N - i
    while t > 0:
        cc += t % 9
        t //= 9
    if cc < res:
        res = cc

print(res)

Solution (Python):
dp_list = [0]

def dp(N, money_list):
    ans = 100000
    if N==0:
        return dp_list[0]
    else:
        for money in money_list:
            if N-money >= 0:
                ans = min(ans, dp_list[N-money]+1)
        dp_list.append(ans)
        
        return dp_list[N]
        
        
def main():
    money_list = [1]
    for i in range(1,7):
        money_list.append(6**i)
    for i in range(1,6):
        money_list.append(9**i)
    money_list.sort(reverse=True)
        
    N = int(input())
    
    for i in range(N+1):
        ans = dp(i, money_list)
        
    print(ans)
    
    
if __name__ == "__main__":
    main()

Solution (Python):
from itertools import count, takewhile

def calc(N, d={}):
    if N < 6:
        return N
    if N in d:
        return d[N]

    max9 = max(takewhile(lambda x: x<=N, (9**i for i in count())))
    max6 = max(takewhile(lambda x: x<=N, (6**i for i in count())))

    d[N] = min(calc(N-max9), calc(N-max6))+1
    
    return d[N]

print(calc(int(input())))

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

    def trans(x, y):
        r = ""
        k = ""
        while not(x==y==0):
            r += str(x%6)
            x = x//6
            k += str(y%9)
            y = y//9
        return r,k

    cost = N
    for i in range(N+1):
        roku, kyu = trans(i, N-i)
        cost_i = 0
        for j in range(len(roku)):
            cost_i += int(roku[j]) + int(kyu[j])
        cost = min(cost, cost_i)

    return cost

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

Solution (Python):

def div_by_N(inpt, N):
    if inpt < N:
        return inpt
    else:
        ans = 0
        while inpt>0:
            ans += inpt%N
            inpt = inpt // N
        return ans
        
def main():
    inpt = int(input())
    ans = 1000000
    for i in range(inpt+1):
        ans = min(ans, div_by_N(i,6)+div_by_N(inpt-i,9))
    print(ans)
    
    
if __name__ == "__main__":
    main()

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

Solution (Python):
num = int(input())
res = num
for i in range(num+1):
    cc = 0
    t = i
    while(t > 0):
        cc += t%6
        t //=6
    t = num-i
    while(t > 0):
        cc += t%9
        t //=9
    if res > cc:
        res = cc

print(res)

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

for i in range(N+1):
    count = 0
    t = i
    
    while (t>0):
        count += t%6
        t = int(t/6)
        
    t = N - i
        
    while (t>0):
        count += t%9
        t = int(t/9)
        
    if(result > count):
        result = count
           

print(result)

Solution (Python):
n=int(input())
s_6=[6**(6-i) for  i in range(6)] 
s_9=[9**(5-i) for  i in range(5)]
amari=[0,1,2,3,4,5,1,2,3,1,2,3,2,3]

best=float("inf")
for i in range(n+1):
    count_6=0
    n_6=i
    for j in range(len(s_6)):
        count_6+=n_6//s_6[j]
        n_6=n_6%s_6[j]

    n_9=n-i
    count_9=0
    for j in range(len(s_9)):
        count_9+=n_9//s_9[j]
        n_9=n_9%s_9[j]

    best=min(best, count_6+count_9+ amari[n_6+n_9])

print(best)

Solution (Python):


n=int(raw_input())
res=n
for i in xrange(n+1):
 s=0
 t=i
 while t>0:
  s+=t%6
  t/=6
 t=n-i
 while t>0:
  s+=t%9
  t/=9
 res=min(s,res)
print res

Solution (Python):
def g(n, a):
    for i in range(1, 100):
        if a**i > n:
            return a**(i-1)
    return -1

dp = {}
def solve(n):
    if n < 6:
        return n
    if not n in dp:
        a = g(n, 6)
        b = g(n, 9)
        dp[n] = min(solve(n-a)+1, solve(n-b)+1)
    return dp[n]





print solve(input())

Solution (Python):





N = int(input())

F = [1]
F += [pow(6,i) for i in range(1,7)]
F += [pow(9,i) for i in range(1,6)]

dp = [0]

for i in range(1,N+1):
    dp.append(dp[i-1]+1) 
    for f in F:
        if i-f>=0: 
            dp[i] = min(dp[i],dp[i-f]+1) 
            
print(dp[N])

Solution (Python):
N=int(input().strip())
pays=[]
p1=set([1,])
n=6
while n<=N:
    p1.add(n)
    n*=6
n=9
while n<=N:
    p1.add(n)
    n*=9
pays.append(p1)
p2=p1
i=1
while i<=N:
    if N in p2:
        break
    else:
        p3=set()
        i+=1
        for i1 in p2:
            for i2 in p1:
                if i1+i2 <=N:
                    p3.add(i1+i2)
        p2=p3
print(i)

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

ans=[1]
cnt=1
while 6**cnt<100000:
  ans.append(6**cnt)
  cnt+=1
cnt=1
while 9**cnt<100000:
  ans.append(9**cnt)
  cnt+=1

bfs=[10**10 for x in range(N+1)]
bfs[0]=0
for i in range(N+1):
  for j in range(len(ans)):
    if i+ans[j]<=N:
      bfs[i+ans[j]]=min(bfs[i+ans[j]],bfs[i]+1)

print(bfs[N])

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

def sol(n):
    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 res > cc:
            res = cc
    return res

print(sol(n))

Solution (Python):
N = int(input())
v = [9**5, 9**4, 9**3, 9**2, 9, 6**6, 6**5, 6**4, 6**3, 6**2, 6, 1]
dp = [0] + [float('inf')] * N
for i in range(N):
    for j in v:
        if i + j <= N:
            dp[i + j] = min(dp[i + j], dp[i] + 1)
print(dp[N])

Solution (Python):
import bisect
n=int(input())
six=[6**(i) for i in range(10)]
nine=[9**(i) for i in range(10)]
times=[0,1,2,3,4,5,1,2,3]
times.extend([0]*100000)
for i in range(6):
    times[i]=i

def solve(n):
    if n==0 or times[n]!=0:
        return times[n]
    six_ex=bisect.bisect_right(six,n)-1
    nine_ex=bisect.bisect_right(nine,n)-1
    six_n=1+solve(n-six[six_ex])
    nine_n=1+solve(n-nine[nine_ex])

    times[n]=min(six_n, nine_n)
    return times[n]

print(solve(n))

Solution (Python):
from itertools import count, takewhile
from functools import lru_cache
 
@lru_cache(maxsize=None)
def dfs(n):
  if n == 0: return 0
  
  max9 = max(takewhile(lambda x: x<=n, (9**i for i in count())))
  max6 = max(takewhile(lambda x: x<=n, (6**i for i in count())))
  return min(dfs(n-max9), dfs(n-max6))+1
 
print(dfs(int(input())))

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


X=[1]+[6**i for i in range(1,7)]+[9**i for i in range(1,6)]
X.sort()
X.reverse()

ANS=1000000



i=5



for i_0 in range(max(N//X[0]-i,0),N//X[0]+1):
    N_0=N-X[0]*i_0
    for i_1 in range(max(N_0//X[1]-i,0),N_0//X[1]+1):
        N_1=N_0-X[1]*i_1
        for i_2 in range(max(N_1//X[2]-i,0),N_1//X[2]+1):
            N_2=N_1-X[2]*i_2
            for i_3 in range(max(N_2//X[3]-i,0),N_2//X[3]+1):
                N_3=N_2-X[3]*i_3
                for i_4 in range(max(N_3//X[4]-i,0),N_3//X[4]+1):
                    N_4=N_3-X[4]*i_4
                    for i_5 in range(max(N_4//X[5]-i,0),N_4//X[5]+1):
                        N_5=N_4-X[5]*i_5
                        for i_6 in range(max(N_5//X[6]-i,0),N_5//X[6]+1):
                            N_6=N_5-X[6]*i_6
                            for i_7 in range(max(N_6//X[7]-i,0),N_6//X[7]+1):
                                N_7=N_6-X[7]*i_7
                                for i_8 in range(max(N_7//X[8]-i,0),N_7//X[8]+1):
                                    N_8=N_7-X[8]*i_8
                                    for i_9 in range(max(N_8//X[9]-i,0),N_8//X[9]+1):
                                        N_9=N_8-X[9]*i_9
                                        i_10=N_9//6
                                        N_10=N_9-X[10]*i_10
                                        if ANS>i_0+i_1+i_2+i_3+i_4+i_5+i_6+i_7+i_8+i_9+i_10+N_10:
                                            ANS=i_0+i_1+i_2+i_3+i_4+i_5+i_6+i_7+i_8+i_9+i_10+N_10


                                            




print(ANS)

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


X=[1]+[6**i for i in range(1,7)]+[9**i for i in range(1,6)]
X.sort()
X.reverse()

ANS=1000000



i=4



for i_0 in range(max(N//X[0]-i,0),N//X[0]+1):
    N_0=N-X[0]*i_0
    for i_1 in range(max(N_0//X[1]-i,0),N_0//X[1]+1):
        N_1=N_0-X[1]*i_1
        for i_2 in range(max(N_1//X[2]-i,0),N_1//X[2]+1):
            N_2=N_1-X[2]*i_2
            for i_3 in range(max(N_2//X[3]-i,0),N_2//X[3]+1):
                N_3=N_2-X[3]*i_3
                for i_4 in range(max(N_3//X[4]-i,0),N_3//X[4]+1):
                    N_4=N_3-X[4]*i_4
                    for i_5 in range(max(N_4//X[5]-i,0),N_4//X[5]+1):
                        N_5=N_4-X[5]*i_5
                        for i_6 in range(max(N_5//X[6]-i,0),N_5//X[6]+1):
                            N_6=N_5-X[6]*i_6
                            for i_7 in range(max(N_6//X[7]-i,0),N_6//X[7]+1):
                                N_7=N_6-X[7]*i_7
                                for i_8 in range(max(N_7//X[8]-i,0),N_7//X[8]+1):
                                    N_8=N_7-X[8]*i_8
                                    for i_9 in range(max(N_8//X[9]-i,0),N_8//X[9]+1):
                                        N_9=N_8-X[9]*i_9
                                        i_10=N_9//6
                                        N_10=N_9-X[10]*i_10
                                        if ANS>i_0+i_1+i_2+i_3+i_4+i_5+i_6+i_7+i_8+i_9+i_10+N_10:
                                            ANS=i_0+i_1+i_2+i_3+i_4+i_5+i_6+i_7+i_8+i_9+i_10+N_10


                                            




print(ANS)

Solution (Python):
from itertools import count, takewhile
from functools import lru_cache

@lru_cache(maxsize=None)
def dfs(n):
  if n < 6:
    return n
  max9 = max(takewhile(lambda x: x<=n, (9**i for i in count())))
  max6 = max(takewhile(lambda x: x<=n, (6**i for i in count())))
  return min(dfs(n-max9), dfs(n-max6))+1
 
print(dfs(int(input())))

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


X=[1]+[6**i for i in range(1,7)]+[9**i for i in range(1,6)]
X.sort()
X.reverse()


DP=[i for i in range(100001)]

def dpmin(i):
    Y=i
    for j in X:
      if i-j>=0:
        Y=min(Y,DP[i-j]+1)

    return Y

for i in range(100001):
    DP[i]=dpmin(i)

print(DP[N])

Solution (Python):
from itertools import count, takewhile
 
def dfs(n, d={}):
  if n < 6:
    return n
  if n in d:
    return d[n]
  max9 = max(takewhile(lambda x: x<=n, (9**i for i in count())))
  max6 = max(takewhile(lambda x: x<=n, (6**i for i in count())))
  d[n] = min(dfs(n-max9), dfs(n-max6))+1
  return d[n]
 
print(dfs(int(input())))

Solution (Python):
from itertools import takewhile, chain, count
 
n = int(input())
 
def powers(a, n):
   return takewhile(lambda x: x<=n, (a**i for i in count(1)))
 
draws = sorted(set(chain([1], powers(6, n), powers(9, n))))
d = {}
for draw, last_draw in zip(draws[1:], draws):
  d[draw, 0] = 0
  for i in range(1, n+1):
    d[draw, i] = min(d.get((draw, i-draw), n)+1, d.get((last_draw, i), i))
 
print(d.get((max(draws), n), n))

Solution (Python):
def s(n,p):
  while n>0:yield n%p;n//=p
c=lambda*a:sum(s(*a));n=int(input());print(min(c(i,6)+c(n-i,9)for i in range(n+1)))

Solution (Python):
def s(n,c):
  if n<6:return c+n
  a=b=1
  while a*6<=n:a*=6
  while b*9<=n:b*=9
  return min(s(n-a,c+1),s(n-b,c+1))
print(s(int(input()),0))

Solution (Python):
def s(n,c):
  if n<6:return c+n
  a=b=1
  while a*6<=n:a*=6
  while b*9<=n:b*=9
  return min(s(n-a,c+1),s(n-b,c+1))
print(s(int(input()),0))

Solution (Python):

def convert(num,radix):
    res = 0
    while num > 0:
        res += num % radix
        num //= radix
    return res


INF = (1 << 31)
N   = int(input())
ans = INF


for i in range(N + 1):
    dec6 = i
    dec9 = N - i
    ans  = min(ans , convert(dec6,6) + convert(dec9,9))


print(ans)

Solution (Python):
a = []
N = 100000
i = 6
a.append(1)
while i<=N:
    a.append(i)
    i*=6
i = 9
while i<=N:
    a.append(i)
    i*=9
a.sort()
n = len(a)
dp = [10*20]*100001

dp[0],dp[1]=0,1 

for mon in range(2,100001):
    for i in range(n):
        if a[i]>mon:
            break
        dp[mon] = min(dp[mon],dp[mon-a[i]]+1)
print(dp[int(input())])

Solution (Python):
N = int(input())
A=[]
A.append(1)
for i in range(1,7):
    A.append(6**i)
for i in range(1,6):
    A.append(9**i)
A.sort()
dp=[10*5+5]*(N+1)
dp[0]=0
for i in range(1,N+1):
    for s in range(len(A)):
        if i-A[s]>=0:
            dp[i]=min(dp[i-A[s]]+1,dp[i])
print(dp[N])

Solution (Python):
n_max = 100000

bs = [(6 ** i, 6) for i in range (1, 10)]
bs.extend([(9 ** i, 9) for i in range (1, 10)])
bs = list(sorted(filter(lambda x: x[0] <= n_max, bs)))
bms = []
s = 5
for b, i in bs:
    s += b * (i - 1)
    bms.append((b, i, s))





m = int(input())

stack = [(m, 0, len(bms) - 1)]

result = 10000
while stack:
    m, n, bms_i = stack.pop()
    b, i, s = bms[bms_i]
    

    if n > result:
        
        continue
    if m > s:
        continue
    if bms_i < 0:
        if m <= 6 and m + n < result:
            result = m + n
        
        continue

    for j in range(i):
        next_m = m - b * j
        if next_m >= 0 and n + j < result:
            stack.append((next_m, n + j, bms_i - 1))

print(result)

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

ans = 0
mod_base = [59049, 46656, 7776, 6561, 1296, 729, 216, 81, 36, 9, 6, 1]
mod_list = [59049, 46656, 7776, 6561, 1296, 729, 216, 81, 36, 9, 6, 1]
ans_list = [0 for _ in range(100000)]

for mod in mod_base:
	ans_list[mod - 1] = 1

for i in range(10000):
	if ans_list[n - 1] != 0:
		break
	new_mod_list = []
	for j in mod_list:
		for k in mod_base:
			if j + k <= 100000 and ans_list[j + k - 1] == 0:
				new_mod_list.append(j + k)
				ans_list[j + k - 1] = i + 2
	mod_list = sorted(new_mod_list, reverse=True)

print(ans_list[n - 1])

Solution (Python):






N = int(input())





list_9 = [9]
for i in range(4):
    list_9.append(list_9[i] * 9)
    
list_6 = [6]
for i in range(5):
    list_6.append(list_6[i] * 6)





amount_list = list_9 + list_6 + [1]
amount_list.sort(reverse=True)





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





for i in range(len(dp)):
    for amount in amount_list:
        if i >= amount:
            dp[i] = min(dp[i],dp[i-amount]+1)
print(dp[N])

Solution (Python):
n = int(input())
dp = [float('Inf')]*(n+1)
np = [9**i for i in range(1, 6)]
sp = [6**i for i in range(1, 7)]
dp[0] = 0
for i in range(1, len(dp)):
  
  for j in np:
    if j > i:
      break
    dp[i] = min(dp[i], dp[i-j]+1)
    
  for j in sp:
    if j > i:
      break
    dp[i] = min(dp[i], dp[i-j]+1)
  
  dp[i] = min(dp[i], dp[i-1]+1)

print(dp[-1])

Solution (Python):
def oper(n):
    res = 100001
    sn = [i for i in range(0, 100001)]
    for i in range(1, 7):
        for j in range(1, 100001):
            sn[j] = min(sn[j], j // (6 ** i) + sn[j % (6 ** i)])

    nn = [i for i in range(0, 100001)]
    for i in range(1, 6):
        for j in range(1, 100001):
            nn[j] = min(nn[j], j // (9 ** i) + nn[j % (9 ** i)])

    for i in range(n + 1):
        res = min(res, sn[i] + nn[n - i])

    return res


if __name__ == "__main__":
    n = input()
    print oper(n)

Solution (Python):
def it(n,p):
  while n > 0:
    yield n%p
    n //= p
cost = lambda *a: sum(it(*a))

n = int(input())
print(min(cost(x,6)+cost(n-x,9) for x in range(n+1)))

Solution (Python):
m = [1]
for i in range(1,7):
    if 6**i < 100000:
        m.append(6**i)
    if 9**i < 100000:
        m.append(9**i)
        
N = int(input())

dp = [10**9 for x in range(100001)]
dp[0] = 0
for v in range(1,100001):
    for i in range(len(m)):
        if v >= m[i] and dp[v - m[i]] != -1:
            dp[v] = min(dp[v],1 + dp[v-m[i]])

print(dp[N])

Solution (Python):
SixNum = [i for i in range(0,100001)]
for i in range(1,7):
        for j in range(1,100001):
                SixNum[j] = min(SixNum[j],j//(6**i) + SixNum[j%(6**i)])

NineNum = [i for i in range(0,100001)]
for i in range(1,6):
        for j in range(1,100001):
                NineNum[j] = min(NineNum[j],j//(9**i) + NineNum[j%(9**i)])

N = int(input())
ans = 100001
for i in range(0,N+1):
        ans = min(ans,SixNum[i]+NineNum[N-i])
print(ans)

Solution (Python):
N = int(input())
res = N;
for i in range(N + 1):
    cc = 0
    t = i
    while t:
        cc += t % 6; t //= 6
    t = N - i
    while t:
        cc += t % 9; t //= 9
    if res > cc:
        res = cc
print(res)

Solution (Python):
def c_strange_bank(N):
    
    money_withdraw = [1, 6, 9, 36, 81, 216,
                      729, 1296, 6561, 7776, 46656, 59049]
    
    dp = [float('inf') for _ in range(N + 1)]
    dp[0] = 0  
    for k in range(1, N + 1):
        for money in money_withdraw:
            if money > k:
                continue
            else:
                
                
                dp[k] = min(dp[k - money] + 1, dp[k])
    ans = dp[-1]
    return ans

N = int(input())
print(c_strange_bank(N))

Solution (Python):



def ret_ans(n):
    li = [1]
    li.extend([6 ** i for i in range(1, 15) if 6 ** i <= n])
    li.extend([9 ** i for i in range(1, 15) if 9 ** i <= n])
    li.sort(reverse=True)
    
    s = set([n])
    cnt = 1
    while True:
        ts = set(s)
        for e in li:
            for c in s:
                if c - e == 0:
                    return cnt
                if c - e > 0:
                    ts.add(c - e)
        s = ts
        cnt += 1
 

def solve():
    print(ret_ans(int(input())))

if __name__=="__main__":
    solve()

Solution (Python):



def ret_ans(n):
    li = [1]
    li.extend([6 ** i for i in range(0, 15) if 6 ** i <= n])
    li.extend([9 ** i for i in range(1, 15) if 9 ** i <= n])
    li.sort(reverse=True)
    
    s = set([n])
    cnt = 1
    while True:
        ts = set(s)
        for e in li:
            for c in s:
                if c - e == 0:
                    return cnt
                if c - e > 0:
                    ts.add(c - e)
        s = ts
        cnt += 1
 

def solve():
    print(ret_ans(int(input())))

if __name__=="__main__":
    solve()

Solution (Python):



def ret_ans(n):
    li = [1]
    li.extend([6 ** i for i in range(0, 15) if 6 ** i <= n])
    li.extend([9 ** i for i in range(1, 15) if 9 ** i <= n])
    li.sort(reverse=True)
    
    s = set([n])
    cnt = 1
    while True:
        ts = set(s)
        for e in li:
            for c in s:
                if c - e == 0:
                    return cnt
                if c - e > 0:
                    ts.add(c - e)
        s = ts
        cnt += 1
 

def solve():
    print(ret_ans(int(input())))

if __name__=="__main__":
    solve()

Solution (Python):
INF=9999999

n=int(input())
dp=[INF for i in range(n+1)]
dp[-1]=0
for i in range(n,0,-1):
    e6=1
    while 6**e6<=i:
        dp[i-6**e6]=min(dp[i]+1,dp[i-6**e6])
        e6+=1
    e9=1
    while 9**e9<=i:
        dp[i-9**e9]=min(dp[i]+1,dp[i-9**e9])
        e9+=1
ans=INF
for i in range(n):
    if dp[i]==0:
        continue
    ans=min(ans,i+dp[i])
if ans==INF:
    ans=n
print(ans)

Solution (Python):
n = int(input())
l = [0]

for i in range(1, n+1):
    a = 0
    b = 0
    while 6**(a+1) <= i: 
        a += 1
    while 9**(b+1) <= i:
        b += 1
    l += [min([l[i-6**p] for p in range(1, a+1)] + [l[i-9**q] for q in range(1, b+1)] + [l[i-1]]) + 1]

print(l[n])

Solution (Python):
N=int(input())
ans=N
def func1():
    global ans
    for i in range(N+1):
        cnt=0
        t=i
        while(t>0):
            cnt+=t%6
            t/=6
            t=int(t)
        t=N-i
        while(t>0):
            cnt+=t%9
            t/=9
            t=int(t)
        if(ans>cnt):
            ans=cnt
    return ans

func1()
print(ans)

Solution (Python):
a = int(input())
k = a
for i  in range(a+1):
  al = 0
  t = i
  while t > 0:
    al += t%6
    t //=6
  t = a - i
  while t > 0:
    al += t%9
    t //=9
  if al < k:
    k = al

print(k)

Solution (Python):
from sys import stdin

def Base_10_to_n(X, n):
    if (int(X/n)):
        return Base_10_to_n(int(X/n), n)+str(X%n)
    return str(X%n)

def sum_num(num):
    sum = 0
    for i in range(len(num)):
        sum += int(num[i])
    return sum

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

x = N

for i in range(N+1):
    cc = 0
    t = i
    while(t > 0):
        cc += t % 6
        t //= 6
    t = N - i
    while(t > 0):
        cc += t % 9
        t //= 9
    if x > cc:
        x = cc

print(x)

Solution (Python):
n = int(input())
v = []
i = 6
while i<=n:
    v.append(i)
    i *= 6
i=9
while i <= n:
    v.append(i)
    i *= 9
v.sort(reverse=True)
dic = dict()
def dp(i, N):
    if i == len(v):
        return N
    if (i, N) not in dic:
        dic[(i, N)] = min(dp(i, N-v[i])+1, dp(i+1, N)) if N-v[i] >= 0 else dp(i+1, N)
    return dic[(i, N)]
print(dp(0, n))

Solution (Python):


def main():
    n = int(input())
    li = dp(n)
    print(li[n])

def dp(n):
    inf=float('inf')
    dp = [inf for i in range(n+1)]
    dp[0] = 0
    money_list = get_money_list()
    for i in range(1, n + 1):
        for pay in money_list:
            if pay > i:
                continue
            else:
                dp[i] = min(dp[i - pay] + 1, dp[i])
    return dp

def create_list(n):
    i = 1
    money_list = []
    while i < 100000:
        money_list.append(i)
        i = i * n
    return money_list

def get_money_list():
    li = create_list(9)
    li.extend(create_list(6))
    li = list(set(li))
    li.sort(key=int, reverse=True)
    return li

if __name__ == '__main__':
    main()

Solution (Python):
import sys
six = [6,36,216,1296,7776,46656]
nine = [9,81,729,6561,59049]

def dfs(n):
    if n < 6:
        return n
    six_max, nine_max = (1, 1)

    for i in six:
        if n < i:
            break
        six_max = i
    
    for i in nine:
        if n < i:
            break
        nine_max = i
    
    ans = 123
    
    if nine_max != 1:
        ans = dfs(n - nine_max) + 1
    if six_max != 1:
        ans = min(ans, dfs(n - six_max) + 1)
    return ans

print(dfs(int(input())))

Solution (Python):
import math
from itertools import product

N = int(input())

values = sorted([9**i for i in range(1, math.ceil(math.log(100000, 9)))] +
                [6**i for i in range(math.ceil(math.log(100000, 6)))])
values = [x for x in values if x <= N]
dp = [N] * (N + 1)
dp[0] = 0
for i, v in product(range(1, N + 1), values):
    if i - v >= 0:
        dp[i] = min(dp[i - v] + 1, dp[i])
print(dp[N])

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


"""

n = 6
while True:
    num.append(n)
    n *= 6
    if n > 100000:
        break
n = 9
while True:
    num.append(n)
    n *= 9
    if n > 100000:
        break
num.sort()

ans = 0
print(num)


def DP(n , index):
    if index == 0:
        return  n
    elif n == 0:
        return 0
    min_ = 10000000
    if n < num[index]:
        
        return DP(n,index - 1)
    can = num[index]
    

    for i in range(n // can+1):
        min_ = min(min_ , DP(n - i * can,index - 1) + i)
 
    
     
    
    memo[n][index] = min_
    return min_
    
print(DP(N,11))
"""

def ninep(N):
    if N <9:
        return N
    ans = 0
    while N > 0:
        ans += N % 9
        N =N // 9
    return ans


def sixp(N):
    if N <6:
        return N
    ans = 0
    while N > 0:
        ans += N % 6
        N = N // 6
    return ans


ans = 1000000
for i in range(N+1):
    ans = min(ans,ninep(i) + sixp(N - i))


print(ans)

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

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

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

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

for i in range(2, N+1):
    for u in units:
        p = i-u
        if p >= 0:
            dp[i] = min(dp[p]+1, dp[i])

print(dp[N])

Solution (Python):
import math

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

for i in range(1,N+1):
	memo[i] = memo[i-1]+1
	j = 1
	while pow(6,j) <= i:  
		memo[i] = min(memo[i],memo[i-pow(6,j)]+1)
		j += 1
	j = 1
	while pow(9,j) <= i:
		memo[i] = min(memo[i],memo[i-pow(9,j)]+1)
		j += 1

print(memo[-1])

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

def calc(x, base):
    r = 0
    while x:
        x, m = divmod(x, base)
        r += m
    return r

result = min(calc(i, 6) + calc(N - i, 9) for i in range(N + 1))

print(result)

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

res = 100000

for i in range(N+1):
  cc = 0
  t = i
  while t>0:
    cc += t%6
    t = int(t/6)
  t = N-i
  while t>0:
    cc += t%9
    t = int(t/9)
  if res > cc:
    res = cc

print(res)

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

result = N
for i in range(0,N+1):
    count = 0
    tmp = i 
    while tmp > 0:
        count += tmp%6
        tmp //= 6
    tmp = N - i 
    while tmp > 0:
        count += tmp%9
        tmp //=9
    
    if result > count:
        result = count

print(result)

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

dp = [10 ** 5]*(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):

def getCnt(n, x):
    ret = 0
    while (n > 0):
        ret += n % x
        n //= x
    return ret

if __name__ == '__main__':
    n = int(input())
    ans = n
    for i in range(n + 1):
        cnt = 0
        cnt += getCnt(i, 6)
        cnt += getCnt(n - i, 9)
        ans = min(ans, cnt)
    print(ans)

Solution (Python):
import numpy as np

N = int(input())

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

    if res < ans:
        ans = res



print(ans)

Solution (Python):
N=int(raw_input())
M=[999999 for i in range(N+1)]
possible=sorted([1]+[6**i for i in range(1,100) if 6**i<=N]+[9**i for i in range(1,100) if 9**i<=N])
M[0]=0
for p in possible:
    M[p]=1

for m in range(N+1):
    tmp=999999
    for p in possible:
        if m-p>0:
            tmp=min(tmp, M[m-p]+1)

    M[m]=min(tmp,M[m])

print M[N]

Solution (Python):
n=int(input())
a=[]
for i in range(n+1):
  a.append(0)
for i in range(1,n+1):
  if i<=5:
    a[i]=i
  elif i<=8:
    a[i]=i-5
  else:
    j=1
    next1=0
    while 6**j<=i:
      next1=6**j
      j+=1
    k=1
    next2=0
    while 9**k<=i:
      next2=9**k
      k+=1
    if a[i-next1]<a[i-next2]:
      a[i]=a[i-next1]+1
    else:
      a[i]=a[i-next2]+1
print(a[n])

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

ans = N
for i in range(N+1):
    cc = 0
    num_6 = i
    num_9 = N - i
    while num_6 > 0:
        cc += (num_6 % 6)
        num_6 //= 6
    while num_9 > 0:
        cc += (num_9 % 9)
        num_9 //= 9
    if ans > cc:
        ans = cc

print(ans)

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

n_max=100000

a1=[1]

a9=[]
for i in range(1, n+1):
	j=9**i
	if j<=n:
		a9.append(j)
	else:
		break

a6=[]
for i in range(1, n+1):
	j=6**i
	if j<=n:
		a6.append(j)
	else:
		break




k1=a1+a6+a9
kn=list(k1)




ans=1

while (1==1):
	if n in kn: break
	kn=[i+j for i in kn for j in k1 if i+j<=n]
	kn=list(set(kn))
	ans+=1


print(ans)

exit(0)

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

ans = N

for A in range(N+1):
    counter = 0
    temp = A
    while temp > 0:
        q, r = divmod(temp, 6)
        counter += r
        temp = q

    temp = N - A
    while temp > 0:
        q, r = divmod(temp, 9)
        counter += r
        temp = q

    if ans > counter:
        ans = counter

print(ans)

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

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

Solution (Python):
n = int(input())
sixs = [6,36,216,1296,7776,46656]
nines = [9,81,729,6561,59049]
lis = [i for i in range(170000)]
for i in range(0,100001):
 for j in sixs:
  if lis[i+j] > lis[i]+1:
    lis[i+j] = lis[i] + 1
 for j in nines:
  if lis[i+j] > lis[i]+1:
    lis[i+j] = lis[i] + 1
print(lis[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 = int(t/6)
    t = n-i
    while(t>0):
        cc+=t%9
        t = int(t/9)
    if res > cc:
        res =cc
print(res)

Solution (Python):
import itertools
import math
import sys

MAX_N = 100000
MAX_LOG6 = int(math.log(MAX_N, 6))
MAX_LOG9 = int(math.log(MAX_N, 9))

def main(N):
    dp = [MAX_N] * (N + 1)
    for i in range(min(N + 1, 6)):
        dp[i] = i
    for i in range(N + 1):
        t = 1
        for j in range(1, MAX_LOG6 + 1):
            t *= 6
            if i - t < 0:
                break
            dp[i] = min(dp[i], dp[i - t] + 1)
        t = 1
        for j in range(1, MAX_LOG9 + 1):
            t *= 9
            if i - t < 0:
                break
            dp[i] = min(dp[i], dp[i - t] + 1)
    print(dp[N])

if __name__ == '__main__':
    N = int(sys.stdin.readline())
    main(N)