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):
INF = 10 ** 20
 
N = int(input())
coin_list = [1] + [6**i for i in range(1, 7)] + [9**i for i in range(1, 6)]
dp = [INF]*(N+1)
dp[0] = 0
 
for coin in coin_list:
    for i in range(coin,N+1):
        dp[i] = min(dp[i], dp[i-coin]+1)
 
print(dp[N])

Solution (Python):
INF = 10 ** 20

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

Solution (Python):
'''
DPで解く
操作を以下2パターンとして考える
 6 ** 0(= 1), 6 ** 1, 6 ** 2...
 9 ** 0(= 1), 9 ** 1, 9 ** 2...
'''

N = int(input())


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


six = []
c = 0
while True:
    w = 6 ** c
    if w > N:
        break
    six.append(w)
    c += 1
nine = []
c = 0
while True:
    w = 9 ** c
    if w > N:
        break
    nine.append(w)
    c += 1


dp[0] = 0


for i in range(N + 1):
    
    for s in six:
        if i + s > N:
            break
        dp[i + s] = min(dp[i + s], dp[i] + 1)
    
    for n in nine:
        if i + n > N:
            break
        dp[i + n] = min(dp[i + n], dp[i] + 1)


print(dp[N])

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

import sys
sys.setrecursionlimit(999999999)
from functools import lru_cache
@lru_cache(maxsize=32)
def solve(cnt,nokori):
    if nokori<6:
        return cnt+nokori

    for six in range(10,-1,-1):
        if 6**six <= nokori:
            break
    for nine in range(10,-1,-1):
        if 9**nine <= nokori:
            break

    res1 = solve(cnt+1,nokori-6**six)
    if nine != 0:
        res2 = solve(cnt+1,nokori-9**nine)
    else:
        res2=10**9

    return min([res1,res2])

print(solve(0,n))

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

def digit(n,m):
    a=n
    _list = []
    while True:
        _list.append(a%m)
        a=a//m
        if a==0:
            break
    return sum(_list)

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

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

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

n=int(input())
maxn=110000
memo=[-1 for i in range(maxn)]
def rec(n):
    if n==0:
        return 0
    if memo[n]!=-1:
        return memo[n]
    res=n
    i=1
    while i<=n:
        res=min(res,rec(n-i)+1)
        i*=6
    j=1
    while j<=n:
        res=min(res,rec(n-j)+1)
        j*=9
    memo[n]=res
    return memo[n]
print(rec(n))

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

table = [0] * (N + 1)
s = {6 ** i for i in range(7) if 6 ** i <= N} | {9 ** i for i in range(6) if 9 ** i <= N}
for i in range(1, N + 1):
    table[i] = min(table[i - j] for j in s if i - j >= 0) + 1
print(table[N])

Solution (Python):
C=[]
for i in range(1,100):
    if 6**i<=10**5:
        C.append(6**i)
for i in range(1,100):
    if 9**i<=10**5:
        C.append(9**i)
        
N=int(input())
dp=[i for i in range(N+1)]
for c in C:
    for i in range(N+1):
        if i-c>=0:
            dp[i]=min(dp[i],dp[i-c]+1)
print(dp[N])

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

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

for i in range(1,n+1):
    if i >= 1:
        dp[i] = min(dp[i],dp[i-1]+1)
    if i >= 6:
        dp[i] = min(dp[i],dp[i-6]+1)
    if i >= 9:
        dp[i] = min(dp[i],dp[i-9]+1)
    if i >= 36:
        dp[i] = min(dp[i],dp[i-36]+1)
    if i >= 81:
        dp[i] = min(dp[i],dp[i-81]+1)
    if i >= 216:
        dp[i] = min(dp[i],dp[i-216]+1)
    if i >= 729:
        dp[i] = min(dp[i],dp[i-729]+1)
    if i >= 1296:
        dp[i] = min(dp[i],dp[i-1296]+1)
    if i >= 6561:
        dp[i] = min(dp[i],dp[i-6561]+1)
    if i >= 7776:
        dp[i] = min(dp[i],dp[i-7776]+1)
    if i >= 46656:
        dp[i] = min(dp[i],dp[i-46656]+1)
    if i >= 59049:
        dp[i] = min(dp[i],dp[i-59049]+1)
print(dp[-1])

Solution (Python):
import bisect
from collections import defaultdict
dd = defaultdict(int)

N=int(input())

a1=[1]
p=1
for i in range(100):
    p*=6
    if p>N:
        break
    a1.append(p)
    
p=1
a2=[1]
for i in range(100):
    p*=9
    if p>N:
        break
    a2.append(p)
    

def rep(NN):
    if dd[NN]!=0:
        return dd[NN]
    if NN==0:
        return 0
    x1=bisect.bisect_right(a1,NN)
    x2=bisect.bisect_right(a2,NN)
    dd[NN]=min(rep(NN-a1[x1-1]), rep(NN-a2[x2-1]))+1
    return dd[NN]
    
rep(N)
print(dd[N])

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

max_n = 110000
dp = [n] * max_n
dp[0] = 0

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

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

print(dp[n])

Solution (Python):

import sys 
input = sys.stdin.readline


def main():
    N = int(input())
    INF = float("inf")
    
    dp = [INF]*(N+1)
    dp[0] = 0

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

    print(dp[N])
    

if __name__ == '__main__':
    main()

Solution (Python):
import math
N = int(input())
dp=[100000]*(100000+1)
dp[0]=0
dp[1:5]=range(1,6)
k9=0
k6=0
for n in range(6,N+1):
  while n//(9**k9)>=9:
    k9+=1
  while n//(6**k6)>=6:
    k6+=1
  dp[n]=min(dp[n],dp[n-6**k6]+1,dp[n-9**k9]+1,dp[n-1]+1)
print(dp[N])

Solution (Python):
import math
N = int(input())
dp=[100000]*(100000+1)
dp[0]=0
dp[1:5]=range(1,6)
dp[6:9]=range(1,4)
k9=0
k6=0
for n in range(9,N+1):
  while n//(9**k9)>=9:
    k9+=1
  while n//(6**k6)>=6:
    k6+=1
  dp[n]=min(dp[n],dp[n-6**k6]+1,dp[n-9**k9]+1,dp[n-1]+1)
print(dp[N])

Solution (Python):
import math
N = int(input())
dp=[100000]*(100000+1)
dp[0]=0
dp[1:5]=range(1,6)
dp[6:9]=range(1,4)
for n in range(9,N+1):
  k9=0
  k6=0
  while n//(9**k9)>=9:
    k9+=1
  while n//(6**k6)>=6:
    k6+=1
  dp[n]=min(dp[n],dp[n-6**k6]+1,dp[n-9**k9]+1,dp[n-1]+1)
print(dp[N])

Solution (Python):
N=int(input())
l=[1,6,9,36,81,216,729,1296,6561,7776,46656,59049]
h=[None]*100001
h[0]=0
k=[0]
c=1
while None in h:
    t=[]
    for i in k:
        for j in l:
            if i+j>100000:
                break
            if h[i+j]==None:
                h[i+j]=c
                t.append(i+j)
    k=t
    c+=1
print(h[N])

Solution (Python):

dp = [float('INF')] * (100000*2)
dp[0] = 0

N = int(input())


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


print(dp[N])

Solution (Python):



def how_many_times_withdraw(withdraw, base, limit):
    result = 0
    while withdraw >= base:
        result += withdraw // (base ** limit)
        withdraw = withdraw % (base ** limit)
        limit -= 1
    return result + withdraw


def main():
    N = int(input())
    limit = []
    answer = float("inf")
    for yen in [6, 9]:
        i = 1
        while yen ** i <= N:
            i += 1
        limit.append(i - 1)
    for i in range(N + 1):
        answer = min(answer, how_many_times_withdraw(i, 6, limit[0]) + how_many_times_withdraw(N - i, 9, limit[1]))
    print(answer)


if __name__ == '__main__':
    main()

Solution (Python):

import math
import heapq
import bisect
import numpy as np
from collections import Counter


N = int(input())

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

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

print(ans[N])

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


class memoRec():
    def __init__(self, n):
        self.max_n = 110000
        self.memo = [n] * self.max_n
        self.memo[0] = 0
        self.n = n

    def power6(self, s, i):
        self.memo[i] = min(self.memo[i], self.memo[i - s] + 1)
        if i - s * 6 < 0:
            return
        return self.power6(s * 6, i)

    def power9(self, s, i):
        self.memo[i] = min(self.memo[i], self.memo[i - s] + 1)
        if i - s * 9 < 0:
            return
        return self.power9(s * 9, i)

    def search(self, s):
        memo = self.power6(1, s)
        memo = self.power9(1, s)
        if s + 1 == self.n + 1:
            return
        return self.search(s + 1)


n = int(input())
mr = memoRec(n)
mr.search(1)
print(mr.memo[n])

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


def power6(n, memo, s):
    memo[n] = min(memo[n], memo[n - s] + 1)
    if n - s * 6 < 0:
        return memo
    return power6(n, memo, s * 6)


def power9(n, memo, s):
    memo[n] = min(memo[n], memo[n - s] + 1)
    if n - s * 9 < 0:
        return memo
    return power9(n, memo, s * 9)


def search(n, memo, s):
    memo = power6(s, memo, 1)
    memo = power9(s, memo, 1)
    if s + 1 == n + 1:
        return memo
    return search(n, memo, s + 1)


n = int(input())
max_n = 110000
dp = [n] * max_n


dp[0] = 0
memo = search(n, dp, 0)
print(memo[n])

Solution (Python):


n = int(input())


max_n = 110000
dp = [n] * max_n


dp[0] = 0

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

print(dp[n])

Solution (Python):


n = int(input())


max_n = 110000
dp = [n] * max_n


dp[0] = 0

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

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

inf = float('inf')

dp = [inf]*(n+100000)
dp[0]=0



def motome(target):
    tmp = []
    for i in range(10):
        if 9**i <= n:
            tmp.append(9**i)
        if 6**i <= n:
            tmp.append(6**i)
    
    
    
    for k in range(target+1):
        for t in sorted(list(set(tmp))):
            if k-t>=0:
                dp[k] = min(dp[k],1 + dp[k-t])
                
                '''
                try:
                    dp[k] = min(dp[k],1 + min([dp[k-t] for t in tmp]))
                except:
                    print(len(dp),dp[k-t],dp[k])
                    pass
                '''
        
        
        

motome(n)

print(dp[n])

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

Solution (Python):
def solve(n):
    cands = [6 ** i for i in range(1, 7)] + [9 ** i for i in range(1, 6)]
    m = len(cands)
    dp = [(0, 0)] * (n + 1)
    for i in range(6, n + 1):
        dp[i] = max(
            ((dp[i - cand][0] + cand, dp[i - cand][1] + 1) for cand in cands if i >= cand),
            key=lambda x: (x[0], -x[1])
        )
    return n - dp[n][0] + dp[n][1]

_n = int(input())
print(solve(_n))

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

credit.sort()

dp=[[float("inf") for _ in range(n+1)] for _ in range(len(credit))]
for i in range(n+1):
    dp[0][i]=i
for i in range(len(credit)):
    dp[i][0]=0
for c_i in range(1,len(credit)):
    for m_i in range(1,n+1):
        if credit[c_i]>m_i:
            dp[c_i][m_i]=dp[c_i-1][m_i]
            continue
        tmp=dp[c_i][m_i-credit[c_i]]+1
        dp[c_i][m_i]=min(tmp,dp[c_i-1][m_i])



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

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

def num_withdraw_ll(N):
    dp = [N] * (N + 1)
    dp[0] = 0
    for n in range(0, N):
        dp[n + 1] = min(dp[n + 1], dp[n] + 1)
        coin = 6
        while n + coin <= N:
            dp[n + coin] = min(dp[n + coin], dp[n] + 1)
            coin *= 6
        coin = 9
        while n + coin <= N:
            dp[n + coin] = min(dp[n + coin], dp[n] + 1)
            coin *= 9
    return dp[N]

print(num_withdraw_ll(N))

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

def num_withdraw_l(N):
    dp = [N] * (N + 1)
    dp[0] = 0
    for n in range(1, N+1):
        dp[n] = min(dp[n], dp[n - 1] + 1)
        coin = 6
        while coin <= N:
            dp[n] = min(dp[n], dp[n - coin] + 1)
            coin *= 6
        coin = 9
        while coin <= N:
            dp[n] = min(dp[n], dp[n - coin] + 1)
            coin *= 9
    return dp[N]

print(num_withdraw_l(N))

Solution (Python):
n = int(input())
ans = float('INF')
hand = []
tmp = 1
while tmp * 6 <= n:
    tmp *= 6
    hand.append(tmp)
tmp = 1
while tmp * 9 <= n:
    tmp *= 9
    hand.append(tmp)
 
hand.sort()
hand = hand[::-1]
dp = [i for i in range(n+1)]
for v in hand:
    for i in range(n+1-v):
        if dp[i] + 1 < dp[i+v]:
            dp[i+v] = dp[i] + 1
print(dp[n])

Solution (Python):
N = int(input())
dp = [0]*(N+1)
money = [1]
p = 1
while p <= N:
    p = p*6
    money.append(p)
p = 1
while p <= N:
    p = p*9
    money.append(p)
lenM = len(money)

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

print(dp[N])

Solution (Python):
a = int(input())
l = [6**i for i in range(10) if 6**i < 10**5]
l += [9**i for i in range(10) if 9**i < 10**5]
l = sorted(list(set(l)))

ans = [10 ** 9 for i in range(a+1)]
ans[0] = 0

for i in range(a):
  for j in l:

    if i + j <= a:
      ans[i+j] = min(ans[i] + 1, ans[i+j])

print(ans[a])

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

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

dp[0] = 0

for i in range(n+1):
    for j in range(n):
        if i + 6 ** j > n:
            break
        dp[i + 6 ** j] = min(dp[i + 6 ** j], dp[i] + 1)
        if not i + 9 ** j > n:
            dp[i + 9 ** j] = min(dp[i + 9 ** j], dp[i] + 1)

print(dp[n])

Solution (Python):
d = tuple([1] + [6**i for i in range(1, 7)] + [9**i for i in range(1, 6)])
M = 10**5+1
B = [float("inf")]*M
B[0] = 0
for i in range(M):
  for j in d:
    if i+j < M:
      B[i+j] = min(B[i+j], B[i]+1)
n = int(input())
print(B[n])

Solution (Python):
l = [1, 6, 9, 36, 81, 216, 729, 1296, 6561, 7776,46656, 59049]
n = int(input())
ans = [10**9 for _ in range(n+1)]
ans[0] = 0

for i in range(n):
    for j in l:
        if i + j <= n:
            ans[i+j] = min(ans[i] + 1,ans[i+j])
        
print(ans[n])

Solution (Python):
n = int(input())
MAX_N = 10**6
dp = [MAX_N] * MAX_N
dp[0] = 0

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

Solution (Python):

N=input()
dp=[ float("inf") for _ in range(N+1) ]
dp[0]=0


for k in range(1,10**5):
    yen=6**k
    for i in range(N+1):
        if i+yen<=N:
            dp[i+yen]=min(dp[i+yen],dp[i]+1)
    if N<=yen:break


for k in range(1,10**5):
    yen=9**k
    for i in range(N+1):
        if i+yen<=N:
            dp[i+yen]=min(dp[i+yen],dp[i]+1)
    if N<=yen:break



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


print dp[N]

Solution (Python):

N=input()
dp=[ float("inf") for _ in range(N+1) ]
dp[0]=0


for k in range(1,10**5):
    yen=9**k
    for i in range(N+1):
        if i+yen<=N:
            dp[i+yen]=min(dp[i+yen],dp[i]+1)
    if N<=yen:break


for k in range(1,10**5):
    yen=6**k
    for i in range(N+1):
        if i+yen<=N:
            dp[i+yen]=min(dp[i+yen],dp[i]+1)
    if N<=yen:break


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


print dp[N]

Solution (Python):

N=input()
dp=[ float("inf") for _ in range(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)

for k in range(1,10**5):
    yen=6**k
    for i in range(N+1):
        if i+yen<=N:
            dp[i+yen]=min(dp[i+yen],dp[i]+1)
    if N<=yen:break


for k in range(1,10**5):
    yen=9**k
    for i in range(N+1):
        if i+yen<=N:
            dp[i+yen]=min(dp[i+yen],dp[i]+1)
    if N<=yen:break

print dp[N]

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

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

coin6 = [6**n for n in range(1,10) if 6**n <= N]
coin9 = [9**n for n in range(1,10) if 9**n <= N]

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

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

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

coin6 = [6**n for n in range(1,10) if 6**n <= N]
coin9 = [9**n for n in range(1,10) if 9**n <= N]

for i in range(N):
    dp[i+1] = min(dp[i+1], dp[i]+1)
    for j in coin6:
        if j+i <= N:
            dp[i+j]=min(dp[i+j],dp[i]+1)
    for j in coin9:
        if j+i <= N:
            dp[i+j]=min(dp[i+j],dp[i]+1)
print(dp[N])

Solution (Python):


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

dic = [None for i in range(n + 1)]
def get_ans(amount:int):
    if dic[amount] is not None:
        return dic[amount]

    if amount <= 0:
        return 0

    ans = amount

    for i in reversed(range(6)):
        num = pow(9, i)
        if num > amount:
            continue
        ret = get_ans(amount - num) + 1
        ans = min(ans, ret)

    for i in reversed(range(7)):
        num = pow(6, i)
        if num > amount:
            continue
        ret = get_ans(amount - num) + 1
        ans = min(ans, ret)

    dic[amount] = ans
    return ans

print(get_ans(n))

Solution (Python):
import math

N = int(input())
NMAX = 100010
dp = [float('inf')] * NMAX
dp[0] = 0
for i in range(1, N + 1):
    dp[i] = i
    if i >= 6:
        for j in range(1, int(math.log(NMAX, 6)) + 1):
            dp[i] = min(dp[i], dp[i - 6 ** j] + 1)

    if i >= 9:
        for j in range(1, int(math.log(NMAX, 9)) + 1):
            dp[i] = min(dp[i], dp[i - 9 ** j] + 1)

print(dp[N])

Solution (Python):


N=int(input())

lis=[]

temp=6
while temp<=N:
    lis.append(temp)
    temp*=6

temp=9
while temp<=N:
    lis.append(temp)
    temp*=9

lis.sort(reverse=True)

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

for item in lis:
    for i in range(N+1):
        if dp[i]!=10**9:
            if i+item<=N:
                dp[i+item]=min(dp[i]+1,dp[i+item])
            
ans=10**10
for index,item in enumerate(dp):
    ans=min(ans,item+N-index)
print(ans)

Solution (Python):
import bisect as bi

li6 = [6 ** i for i in range(7)]
li9 = [9 ** i for i in range(6)]

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


print(s69(int(input())))

Solution (Python):

n=int(input())


dp=[float('inf')]*(n+1)
dp[0]=0
l=[1,6,9]
for i in range(n+1):

    for j in range(3):
        num=1
        deposit=l[j]
        while i+deposit<=n:
            if deposit==1:
                dp[i+1]=min(dp[i+1],dp[i]+1)
                break
            dp[deposit+i]=min(dp[deposit+i],dp[i]+1)
            num+=1
            
            deposit=l[j]**num
print(dp[-1])

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

dp = [[10**10] * (n+1) for _ in range(4)]
for i in range(4):
    dp[i][0] = 0

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

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

Solution (Python):
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
def gcd(a,b):return fractions.gcd(a,b) 
def lcm(a,b):return (a*b) // fractions.gcd(a,b) 
def iin(): return int(input()) 
def ifn(): return float(input()) 
def isn(): return input().split() 
def imn(): return map(int, input().split()) 
def fmn(): return map(float, input().split()) 
def iln(): return list(map(int, input().split())) 
def iln_s(): return sorted(iln()) 
def iln_r(): return sorted(iln(), reverse=True) 
def fln(): return list(map(float, input().split())) 
def join(l, s=''): return s.join(l) 
def perm(l, n): return itertools.permutations(l, n) 
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) 
def comb(l, n): return itertools.combinations(l, n) 
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) 
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 
def m_add(a,b): return (a+b) % MOD

MAX_N = 110000

N = iin()

dp = [-1 for _ in range(MAX_N)]
dp[0] = 0

que = collections.deque()

que.append(0)

while (len(que) != 0):
    v = que.popleft()
    pow6 = 1
    while v+pow6 <= N:
        if dp[v+pow6] == -1:
            dp[v+pow6] = dp[v] + 1
            que.append(v+ pow6)
        pow6 *= 6
    pow9 = 1
    while v+pow9 <= N:
        if dp[v+pow9] == -1:
            dp[v+pow9] = dp[v] + 1
            que.append(v+pow9)
        pow9 *= 9
print(dp[N])

Solution (Python):
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
def gcd(a,b):return fractions.gcd(a,b) 
def lcm(a,b):return (a*b) // fractions.gcd(a,b) 
def iin(): return int(input()) 
def ifn(): return float(input()) 
def isn(): return input().split() 
def imn(): return map(int, input().split()) 
def fmn(): return map(float, input().split()) 
def iln(): return list(map(int, input().split())) 
def iln_s(): return sorted(iln()) 
def iln_r(): return sorted(iln(), reverse=True) 
def fln(): return list(map(float, input().split())) 
def join(l, s=''): return s.join(l) 
def perm(l, n): return itertools.permutations(l, n) 
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) 
def comb(l, n): return itertools.combinations(l, n) 
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) 
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 
def m_add(a,b): return (a+b) % MOD

MAX_N = 110000

N = iin()

dp = [10**10 for _ in range(MAX_N)]
dp[0] = 0

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

Solution (Python):
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
def gcd(a,b):return fractions.gcd(a,b) 
def lcm(a,b):return (a*b) // fractions.gcd(a,b) 
def iin(): return int(input()) 
def ifn(): return float(input()) 
def isn(): return input().split() 
def imn(): return map(int, input().split()) 
def fmn(): return map(float, input().split()) 
def iln(): return list(map(int, input().split())) 
def iln_s(): return sorted(iln()) 
def iln_r(): return sorted(iln(), reverse=True) 
def fln(): return list(map(float, input().split())) 
def join(l, s=''): return s.join(l) 
def perm(l, n): return itertools.permutations(l, n) 
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) 
def comb(l, n): return itertools.combinations(l, n) 
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) 
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 
def m_add(a,b): return (a+b) % MOD

MAX_N = 110000

N = iin()

dp = [10**10 for _ in range(MAX_N)]
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())
l = [1]
a = 6
b = 9
while True:
    if a > 100000:
        break
    else:
        l.append(a)
        l.append(b)
        a *= 6
        b *= 9

dp = [[10000000]*(n+1) for i in range(len(l)+1)]
dp[0][0] = 0
for i in range(len(l)):
    for j in range(n+1):
        if j < l[i]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = min(dp[i][j],dp[i+1][j-l[i]]+1)
print(dp[len(l)][n])

Solution (Python):
def knapsack(N,W,weight,value):
  
  dp=[[10**7 for i in range(W+1)] for j in range(N+1)]
  for i in range(W+1):
    dp[0][i]=i
  
  for i in range(N):
    for w in range(W+1):
      if weight[i]<=w: 
        dp[i+1][w]=min(dp[i+1][w-weight[i]]+value[i], dp[i][w])
      else:
        dp[i+1][w]=dp[i][w]
        
  
  return dp[N][W]

N = 12
W = int(input())
weight = [1,6,36,216,1296,7776,46656,9,81,729,6561,59049]
value = [1,1,1,1,1,1,1,1,1,1,1,1,1]

a = knapsack(N,W,weight,value)

print(a)

Solution (Python):
N = int(input())
 
h = [1]
 
t = []
i = 1
while True:
  t.append(6**i)
  i += 1
  if t[-1]>10000:
    break
h.extend(t)
 
t = []
i = 1
while True:
  t.append(9**i)
  i += 1
  if t[-1]>10000:
    break
h.extend(t)
 
h.sort()
 
DP = []
DP.append(0)
 
hlen = len(h)
for i in range(1,N+1):
  m = 999999
  for j in range(hlen):
    if i-h[j]<0:
      break
    else:
      if m>DP[i-h[j]] + 1:
        m = DP[i-h[j]] + 1
  DP.append(m)  
print(DP[N])

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

h = [1]

t = []
i = 1
while True:
  t.append(6**i)
  i += 1
  if t[-1]>10000:
    break
h.extend(t)

t = []
i = 1
while True:
  t.append(9**i)
  i += 1
  if t[-1]>10000:
    break
h.extend(t)

h.sort()

DP = []
DP.append((0, 0))

hlen = len(h)
for i in range(1,N+1):
  m = 999999
  p = 0
  for j in range(hlen):
    if i-h[j]<0:
      break
    else:
      if m>DP[i-h[j]][0] + 1:
        m = DP[i-h[j]][0] + 1
        p = h[j] + DP[i-h[j]][0]
  DP.append((m, p))  
print(DP[N][0])

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

arr = [N]
ans = 0
stop = 0
  

while arr:
  a = arr.pop(0)
  
  if a == -1:
    ans += 1
  
  done.append(a)
  Next = []
  if a-1 >= 0:
    Next.append(a-1)

  if a-46656 >= 0:
    Next.append(a-46656)
  elif a-7776 >= 0:
    Next.append(a-7776)
  elif a-1296 >= 0:
    Next.append(a-1296)
  elif a-216 >= 0:
    Next.append(a-216)
  elif a-36 >= 0:
    Next.append(a-36)
  elif a-6 >= 0:
    Next.append(a-6)

  if a-59049 >= 0:
    Next.append(a-59049)
  elif a-6561 >= 0:
    Next.append(a-6561)
  elif a-729 >= 0:
    Next.append(a-729)
  elif a-81 >= 0:
    Next.append(a-81)
  elif a-9 >= 0:
    Next.append(a-9)
    
  if -1 not in arr:
    arr.append(-1)   

  while Next:
    i = Next.pop(0)
    if i in done:
      continue
    elif i in arr:
      continue
    else:
      arr.append(i)
      if i == 0:
        stop = 1
        break
  if stop == 1:
    break

print(ans+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):
from collections import deque

N = int(input())
done = deque()

arr =  deque([N])
ans = 0
stop = 0
  

while arr:
  a = arr.popleft()
  
  if a == -1:
    ans += 1
  
  done.append(a)
  Next = deque()
  if a-1 >= 0:
    Next.append(a-1)

  if a-46656 >= 0:
    Next.append(a-46656)
  elif a-7776 >= 0:
    Next.append(a-7776)
  elif a-1296 >= 0:
    Next.append(a-1296)
  elif a-216 >= 0:
    Next.append(a-216)
  elif a-36 >= 0:
    Next.append(a-36)
  elif a-6 >= 0:
    Next.append(a-6)

  if a-59049 >= 0:
    Next.append(a-59049)
  elif a-6561 >= 0:
    Next.append(a-6561)
  elif a-729 >= 0:
    Next.append(a-729)
  elif a-81 >= 0:
    Next.append(a-81)
  elif a-9 >= 0:
    Next.append(a-9)
    
  if -1 not in arr:
    arr.append(-1)
    

  while Next:
    i = Next.pop()
    if i in done:
      continue
    elif i in arr:
      continue
    else:
      arr.append(i)
      if i == 0:
        stop = 1
        break
  if stop == 1:
    break

print(ans+1)

Solution (Python):
from functools import lru_cache

@lru_cache(maxsize=1000000)
def fx(n):
  if n == 0:
    return 0
  if n == 1:
    return 1
  arr = []
  cnt = 0
  
  if n < 6:
    b = fx(n-1)+1
    arr.append(b)
  while n-6**cnt >= 0:
    cnt += 1
  if cnt > 1:
    
    x = n-(6**(cnt-1))
    b = fx(x)+1
    arr.append(b)

  cnt = 0
  while n-9**cnt >= 0:
    cnt += 1
  if cnt > 1:
    x = n-(9**(cnt-1))
    b = fx(x)+1
    arr.append(b)
  
  return min(arr)
  
N = int(input())
print(fx(N))

Solution (Python):
from functools import lru_cache

@lru_cache(maxsize=1000)
def fx(n):
  if n == 0:
    return 0
  if n == 1:
    return 1
  arr = []
  cnt = 0
  
  if n < 6:
    b = fx(n-1)+1
    arr.append(b)
  while n-6**cnt >= 0:
    cnt += 1
  if cnt > 1:
    
    x = n-(6**(cnt-1))
    b = fx(x)+1
    arr.append(b)

  cnt = 0
  while n-9**cnt >= 0:
    cnt += 1
  if cnt > 1:
    x = n-(9**(cnt-1))
    b = fx(x)+1
    arr.append(b)
  
  return min(arr)
  
N = int(input())
print(fx(N))

Solution (Python):

n = int(input())




nums = [1]

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





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