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

Solution (Python):
n = int(input())
min_time = [float('inf')] * (n+1)
min_time[0] = 0
for i in range(n):
    min_time[i+1] = min(min_time[i+1],min_time[i]+1)
    times_6 = 1
    while i+6**times_6<=n:
        min_time[i+6**times_6] = min(min_time[i+6**times_6],min_time[i]+1)
        times_6 += 1
    times_9 = 1
    while i+9**times_9<=n:
        min_time[i+9**times_9] = min(min_time[i+9**times_9],min_time[i]+1)
        times_9 += 1
print(min_time[-1])

Solution (Python):


import math

import itertools
from collections import deque
from collections import Counter
import heapq
from fractions  import gcd


n=int(input())
a=[0]*14
a[0]=1
a[8]=9
for i in range(1,8):
    a[i]=a[i-1]*6
for i in range(9,14):
    a[i]=a[i-1]*9
inf=10**6
dp=[[inf]*(n+1) for _ in range(15)]
dp[0][0]=0
for i in range(14):
    for j in range(n+1):
        dp[i+1][j]=min(dp[i][j],dp[i+1][j])
        if j+a[i]<n+1:
          dp[i+1][j+a[i]]=min(dp[i+1][j]+1,dp[i+1][j+a[i]])
print(dp[-1][-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):
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()

    
    l = [1]
    a = 6
    b = 9
    while a <= N or b <= N:
        if a < b:
            l.append(a)
            a *= 6
        else:
            l.append(b)
            b *= 9

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

    print(dp[-1])

if __name__ == '__main__':
    resolve()

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

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

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

print(dp[N])

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

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def get_num_draw(n, x):
    res = 0
    while n > 0:
        res += n % x
        n = n // x
    return res


def main():
    N = NI()
    ans = 10**10
    for i in range(0, N+1, 6):
        ans = min(get_num_draw(N-i, 9) + get_num_draw(i//6, 6), ans)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
N = int(input())
kouho = [1]
for i in range(1, 100):
    t = 6 ** i
    if t <= 10 ** 5:
        kouho.append(t)
    else:
        break
for i in range(1, 100):
    t = 9 ** i
    if t <= 10 ** 5:
        kouho.append(t)
    else:
        break


kouho.sort(reverse=True)
kouho_cnt = len(kouho)
INF = 10 ** 9
dp = [INF] * ((10 ** 5) + 1)
dp[0] = 0
for i in range(1, N + 1):
    for k in kouho:
        if i - k >= 0:
            dp[i] = min(dp[i], dp[i - k] + 1)

print(dp[N])

Solution (Python):
import sys
def I(): return int(sys.stdin.readline().rstrip())

N = I()

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

dp = [0]*(N+1)  
for i in range(N+1):
    if i == 0:
        continue
    else:
        a = N
        for j in A:
            if i >= j:
                a = min(a,dp[i-j]+1)
        dp[i] = a

print(dp[N])

Solution (Python):
n = int(input())
a_6 = [int(6**i) for i in range(1,10) if 6**i <= 10**5]
a_9 = [int(9**i) for i in range(1,10) if 9**i <= 10**5]
a = [1]
for i in a_6:
    a.append(i)
for i in a_9:
    a.append(i)
a.sort(reverse = True)
dp = [i for i in range(n+1)]
dp[0] = 0
for i in range(n+1):
    for j in a:
        if i+j <= n:
            dp[i+j] = min(dp[i+j],dp[i]+1)
print(dp[n])

Solution (Python):


N = int(input())

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

dp[0] = 0

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

print(dp[N])

Solution (Python):
n=int(input())
money=[1]
dp=[0]*(n+1)
dp[1]=1
m=6
i=1
while m<=n:
  money.append(m)
  i+=1
  m=6**i
m=9
i=1
while m<=n:
  money.append(m)
  i+=1
  m=9**i

for m in money:
  dp[m]=1

money.sort()
for i in range(1,n+1):
  for m in money:
    if i+m>=n+1:
      continue
    if dp[i]+1<=dp[i+m] or dp[i+m]==0:
      dp[i+m]=dp[i]+1
      
print(dp[n])

Solution (Python):

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

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


for n in range(N + 1):
    c = 0
    price_by_6 = n
    while price_by_6 > 0:
        c += price_by_6 % 6  
        price_by_6 //= 6
    price_by_9 = N - n
    while price_by_9 > 0:
        c += price_by_9 % 9  
        price_by_9 //= 9
    ans = min(ans, c)

print(ans)

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

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

lst.sort()

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

Solution (Python):
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n = INT()
a = [inf]*100001

a[0] = 0
for i in range(1,100001):
    a[i] = min(a[i], a[i-1]+1)
    j = 1
    while i - 6**j >= 0:
        a[i] = min(a[i], a[i-6**j]+1)
        j += 1
    j = 1
    while i - 9**j >= 0:
        a[i] = min(a[i], a[i-9**j]+1)
        j += 1

print(a[n])

Solution (Python):
n = int(raw_input())
dp = [j for j in range(n+1)] 
for i in range(1, n+1):
	for u in [6,9]:
		p = 1
		q = u ** p
		while((i  - q) >= 0):
			dp[i] = min(dp[i], 1 + dp[i - q])
			p += 1
			q = u ** p
print dp[n]

Solution (Python):
n = int(raw_input())
dp = [+float('inf')] * (n+1)
dp[0] = 0
for i in range(1, n+1):
	q = 1
	if i - q >= 0:
		dp[i] = min(dp[i], 1 + dp[i - q])
	for u in [6,9]:
		p = 1
		q = u ** p
		while((i  - q) >= 0):
			dp[i] = min(dp[i], 1 + dp[i - q])
			p += 1
			q = u ** p
print dp[n]

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

for n in range(N+1):
  c = 0
  t = n
  while t>0:
    c+=t%6
    t//=6
  t = N-n
  while t>0:
    c+=t%9
    t//=9
  a = min(a,c)
  
print(a)

Solution (Python):
n = int(input())
dp = [None] * (n+1)
dp[1] = 1
dp[0] = 0
sixs = [6]
nines = [9]
i = 1
while sixs[i-1] * 6 <= n:
    sixs.append(sixs[i-1]*6)
    i += 1

i = 1
while nines[i-1] * 6 <= n:
    nines.append(nines[i-1]*9)
    i += 1
for current in range(2, n+1):
    smin = n
    for six in sixs:
        if current - six >= 0 and dp[current-six] != None:
            smin = min(smin, dp[current-six] + 1)
    nmin = n
    
    for nine in nines:
        if current - nine >= 0 and dp[current-nine] != None:
            nmin = min(nmin, dp[current-nine] + 1)
    
    dp[current] = min(dp[current-1] + 1, nmin, smin)
print (dp[n])

Solution (Python):
import sys
import itertools

import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


N = int(input())

coins = [(9 ** i) for i in range(1, 7)] + [(6 ** i) for i in range(1, 8)] + [1]
dp = [INF] * (N + 1)
dp[0] = 0
for i in range(len(coins)):
    for j in range(N + 1):
        if j + coins[i] > N:
            continue
        dp[j + coins[i]] = min(dp[j + coins[i]], dp[j] + 1)
print(dp[N])

Solution (Python):
from functools import lru_cache

n = int(input())
@lru_cache(maxsize=None)
def func(n):
  if n < 6:
    return n
  a = []
  b = 6
  while(b<=n):
    a.append(b)
    b*=6
  b = 9
  while(b<=n):
    a.append(b)
    b*=9
  ret = n
  a.sort(reverse=True)
  for i in a:
    ret = min(ret,1+func(n-i))
  return ret
print(func(n))

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

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

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

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
ans = float("inf")
def sub(x, base):
    if x==0:
        return 0
    i = 0
    while pow(base, i+1)<=x:
        i += 1
    return sub(x-pow(base,i), base) + 1
for i in range(n+1):
    ans = min(ans, sub(i,6)+sub(n-i,9))
print(ans)

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):
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    N = int(input())

    X = [1]
    for i in range(1, 101):
        if 6**i > N:
            break
        X.append(6**i)
    for i in range(1, 101):
        if 9**i > N:
            break
        X.append(9**i)
    dp = [N+1] * (N+1)
    dp[0] = 0
    for i in range(N):
        for x in X:
            if i+x <= N:
                dp[i+x] = min(dp[i+x], dp[i] + 1)
    print(dp[N])


if __name__ == '__main__':
    main()

Solution (Python):
N=int(input())
from itertools import product
a=10**5
for p in product(range(9),repeat=5):
    n=N-sum([9**(i+1)*p[i] for i in range(5)])
    if n<0:continue
    b=sum(p)
    x=6**6
    while x>0:
        b+=n//x
        n%=x
        x//=6
    a=min(a,b)
print(a)

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

Solution (Python):
N=int(input())
inf=float("inf")

X=[inf]*(N+1)
X[0]=0

for x in range(1,N+1):
    X[x]=X[x-1]+1

    b=6
    while x>=b:
        X[x]=min(X[x],X[x-b]+1)
        b*=6

    c=9
    while x>=c:
        X[x]=min(X[x],X[x-c]+1)
        c*=9

print(X[-1])

Solution (Python):
n = int(input())
A = [1]+[pow(6,i) for i in range(1,7)]+[pow(9,i) for i in range(1,6)]
D = [0]+[-1]*n
for i in range(1,n+1):
    D[i] = D[i-1]+1
    for j in range(1,7):
        if pow(6,j)>i: break
        D[i] = min(D[i], D[i-pow(6,j)]+1)
    for j in range(1,6):
        if pow(9,j)>i: break
        D[i] = min(D[i], D[i-pow(9,j)]+1)
print(D[-1])

Solution (Python):
N = int(input())
dp = [0 for i in range(N + 1)]
divider = [1]

i = 6
while i <= N:
    divider.append(i)
    i *= 6

i = 9
while i <= N:
    divider.append(i)
    i *= 9


for x in divider:
    dp[x] = 1

for i in range(1, N + 1):
    if dp[i] == 0:
        poss = []
        for x in divider:
            if i - x >= 0:
                poss.append(dp[i - x] + 1)
        dp[i] = min(poss)

print(dp[N])

Solution (Python):
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
def main():
    n = int(input())
    nums = []
    n6 = 6
    while n6 <= n:
        nums.append(n6)
        n6 = n6 * 6
    n9 = 9
    while n9 <= n:
        nums.append(n9)
        n9 = n9 * 9
    nums.sort(reverse=True)
    dp = [i for i in range(2 * n + 1)]
    for num in nums:
        for j1 in range(n + 1):
            dp[j1+num] = min(dp[j1+num], dp[j1] + 1)
    print(dp[n])


if __name__ == '__main__':
    main()

Solution (Python):
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
def main():
    n = int(input())
    nums = []
    n6 = 6
    while n6 <= n:
        nums.append(n6)
        n6 = n6 * 6
    n9 = 9
    while n9 <= n:
        nums.append(n9)
        n9 = n9 * 9
    nums.sort(reverse=True)
    dp = [i for i in range(2 * n + 1)]
    for num in nums:
        for j1 in range(n + 1):
            dp[j1+num] = min(dp[j1+num], dp[j1] + 1)
    print(dp[n])


if __name__ == '__main__':
    main()

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

ans = 100000
for i in range(0,N+1,1):
    j = N - i

    icount = 0
    while i!=0:
        icount += (i%6)
        i=i//6

    jcount = 0
    while j!=0:
        jcount += (j%9)
        j=j//9

    ans = min(icount+jcount,ans)

print(ans)

Solution (Python):
import numpy as np

n = int(input())

dp = [0]*(n+1)

b = 6
c = 9
for i in range(1, n+1):
  if i>=b*6: b*=6
  if i>=c*9: c*=9
  if i < 6:
    dp[i] = i
  elif i < 9:
    dp[i] = min(dp[i-1]+1, dp[i-b]+1)
  else:
    dp[i] = min(dp[i-1]+1, dp[i-b]+1, dp[i-c]+1)
print(dp[-1])

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

a = []


a.append(1)


b = 6
while b <= N:
    a.append(b)
    b *= 6


b = 9
while b <= N:
    a.append(b)
    b *= 9

a.sort()

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

Solution (Python):
import sys


def resolve():
    readline = sys.stdin.readline

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

    N = int(readline())

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

resolve()

Solution (Python):
n=int(input())
dp=list(range(n+1))
dp[0]=0
a=[]
b=[]
i=1
while True:
  if 6**i>n:break
  a.append(6**i)
  i+=1
i=1
while True:
  if 9**i>n:break
  b.append(9**i)
  i+=1
for i in a:
  for j in range(i,n+1):
    dp[j]=min(dp[j],dp[j-i]+1)
for i in b:
  for j in range(i,n+1):
    dp[j]=min(dp[j],dp[j-i]+1)
print(dp[n])

Solution (Python):
def main():
    from collections import deque
    N = int(input())

    amounts = [1]
    mul6 = 6
    while mul6 <= N:
        amounts.append(mul6)
        mul6 *= 6
    mul9 = 9
    while mul9 <= N:
        amounts.append(mul9)
        mul9 *= 9

    distances = [-1]*(N+1)
    distances[0] = 0

    targets = deque([0])
    while targets:
        t = targets.popleft()
        d = distances[t]
        for a in amounts:
            if t + a <= N and distances[t+a] == -1:
                distances[t+a] = d+1
                targets.append(t+a)
    print(distances[N])




main()

Solution (Python):
def main():
    N = int(input())
    amounts = [1]
    lim = 10**6
    mul6 = 6
    while mul6 < lim:
        amounts.append(mul6)
        mul6 *= 6
    mul9 = 9
    while mul9 < lim:
        amounts.append(mul9)
        mul9 *= 9
    
    dp = [lim] * (N+1)
    dp[0] = 0
    for i in range(N):
        for a in amounts:
            if i+a <= N:
                dp[i+a] = min(dp[i+a],dp[i]+1)
    print(dp[N])

    



main()

Solution (Python):
from collections import deque
def main():
    N = int(input())
    divs = [59049, 46656, 7776, 6561, 1296, 729, 216, 81, 36, 9, 6, 1]
    dp = [0]*(10**6+1)
    def f(x):
        if x == 0:
            return 0
        if x < 0:
            return 10**6
        if dp[x]:
            return dp[x]
        else:
            res = 10**6
            for d in divs:
                res = min(res,f(x-d)+1)
            dp[x] = res
            return res
            

    print(f(N))
main()

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

def calc_dp(n):
    initial = 10**7
    dp=[initial for _ in range(100100)]
    dp[0] = 0

    for i in range(100001):
        count = 0
        while 6**count <= n:
            power_six = 6**count
            count += 1
            if i - power_six >= 0:
                dp[i] = min(dp[i],1 + dp[i-power_six])
                
        count = 1
        while 9**count <= n:
            power_nine = 9**count
            count += 1
            if i - power_nine >= 0:
                dp[i] = min(dp[i],1 + dp[i-power_nine])

    return dp[n]

print(calc_dp(N))

Solution (Python):
N = int(input())
ans = float('inf')
for i in range(N+1):
    j = i
    count = 0
    t=N-i
    while j > 0:
        count += j%6
        j=j//6
    while t > 0:
        count += t%9
        t=t//9
    ans = min(ans,count)
print(ans)

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

dp = [10 ** 9] * 100001
dp[0] = 1

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

print(dp[N] - 1)

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

dp = [10 ** 9] * 100001
dp[0] = 1

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

print(dp[N] - 1)

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

coin=[1]

for _ in [6,9]:
    __=_
    while __ <= N:
        coin.append(__)
        __=__*_
coin.sort()

dp=[[0]*(N+1) for c in coin]

for n in range(N):
    n += 1
    for c_idx,c in enumerate(coin):
        
        if c_idx==0:
            dp[c_idx][n] = dp[c_idx][n-c]+1
            
        elif n-c >= 0:
            dp[c_idx][n] = min(dp[c_idx-1][n],dp[c_idx][n-c]+1)
            
        else:
            dp[c_idx][n] = dp[c_idx-1][n]

ans=10**10
for c in range(len(coin)):
    if ans > dp[c][-1]:
        ans=dp[c][-1]
print(ans)

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

res = n

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

print(res)

Solution (Python):

def Format(X, n):
    X_dumy = X
    out = ''
    while X_dumy>0:
        out = str(X_dumy%n)+out
        X_dumy = int(X_dumy/n)
    return out


n=int(input())

ans=n
for i in range(n+1):
  j=n-i
  i,j=Format(i,6),Format(j,9)
  t=0
  for s in i:
    t+=int(s)
  for s in j:
    t+=int(s)
  ans=min(ans,t)
print(ans)

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

six = []
nine = []

now = 6
while now < 100001:
  six.append(now)
  now *= 6
  
now = 9
while now < 100001:
  nine.append(now)
  now *= 9  




def coin(n):
  if n < 6:
    return n
  else:
    index_six = bisect.bisect_right(six, n)
    index_nine = bisect.bisect_right(nine, n)
    
    
    if n - six[index_six - 1] >= 0:
      alpha = coin(n - six[index_six - 1]) + 1
    else:
      alpha = 10 ** 7
    if n - nine[index_nine - 1] >= 0:
      beta = coin(n - nine[index_nine - 1]) + 1
    else:
      beta = 10 ** 7
    return min(alpha, beta)
  
print(coin(N))

Solution (Python):
def main():
  N=int(input())
  values=[]
  val=6
  while val<=N:
    values.append(val)
    val*=6
  
  val=9
  while val<=N:
    values.append(val)
    val*=9
  values.append(1)
  values.sort()
  dp=[N]*(N+1)
  dp[0]=0
  for i in range(N):
    for v in values:
      if i+v>N:break
      dp[i+v]=min(dp[i]+1,dp[i+v])
  print(dp[N])
  pass
if __name__ == '__main__':
  main()

Solution (Python):
N = 10**6
n = int(input())

nine = [1, 9]
while True:
    t = nine[-1] * 9
    if t > N:
        break
    nine.append(t)

six = [1, 6]
while True:
    t = six[-1] * 6
    if t > N:
        break
    six.append(t)

dp = [N]*(n+1)
dp[0] = 0
for i in range(1, n+1):
    
    for j in nine:
        if i-j < 0:
            break
        dp[i] = min(dp[i], dp[i-j]+1)
    for j in six:
        if i-j < 0:
            break
        dp[i] = min(dp[i], dp[i-j]+1)

print(dp[n])

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

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

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

INF = float("inf")

memo = [float("inf")]*100005

def rec(n):
    if n==0:
        return 0
    if memo[n]!=float("inf"):
        return memo[n]
    res = float("inf")
    val = 1
    while val<=n:
        res = min(res,rec(n-val)+1)
        val*=6
    
    val = 1
    while val<=n:
        res = min(res,rec(n-val)+1)
        val*=9
    memo[n]=res
    return memo[n]

dp = [INF]*100005

def morau_dp():
    
    N = int(input())
    dp[0]=0
    for i in range(1,N+1):
        val = 1
        while val<=N:
            dp[i]=min(dp[i],dp[i-val]+1)
            val*=6
        
        val = 1
        while val<=N:
            dp[i] = min(dp[i],dp[i-val]+1)
            val*=9

    print(dp[N])


def kubaru_dp():
    
    N = int(input())
    dp[0]=0
    for i in range(0,N):
        val = 1
        while (i+val)<=N:
            dp[i+val] = min(dp[i+val],dp[i]+1)
            val*=6

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


if __name__ == "__main__":
    
    
    
    kubaru_dp()

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

INF = float("inf")

memo = [float("inf")]*100005

def rec(n):
    if n==0:
        return 0
    if memo[n]!=float("inf"):
        return memo[n]
    res = float("inf")
    val = 1
    while val<=n:
        res = min(res,rec(n-val)+1)
        val*=6
    
    val = 1
    while val<=n:
        res = min(res,rec(n-val)+1)
        val*=9
    memo[n]=res
    return memo[n]

dp = [INF]*100005

def morau_dp():
    
    N = int(input())
    dp[0]=0
    for i in range(1,N+1):
        val = 1
        while val<=N:
            dp[i]=min(dp[i],dp[i-val]+1)
            val*=6
        
        val = 1
        while val<=N:
            dp[i] = min(dp[i],dp[i-val]+1)
            val*=9

    print(dp[N])


if __name__ == "__main__":
    
    
    morau_dp()

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

memo = [float("inf")]*100005

def rec(n):
    if n==0:
        return 0
    if memo[n]!=float("inf"):
        return memo[n]
    res = float("inf")
    val = 1
    while val<=n:
        res = min(res,rec(n-val)+1)
        val*=6
    
    val = 1
    while val<=n:
        res = min(res,rec(n-val)+1)
        val*=9
    memo[n]=res
    return memo[n]

if __name__ == "__main__":
    N = int(input())
    print(rec(N))

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





def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))


def main():
	n=II()
	dp=list(range(10**5+1))
	x=[]
	a=6
	while a<10**5:
		x.append(a)
		a*=6
	a=9
	while a<10**5:
		x.append(a)
		a*=9
	x.sort()
	

	

	for i in x:
		for j in range(i,10**5+1):
			dp[j]=min(dp[j],dp[j-i]+1)
	print(dp[n])



if __name__ == "__main__":
	main()

Solution (Python):
n = int(input())
ans = pow(10, 10)

for i in range(n+1):
    cnt = 0
    j = n - i
    while i > 0:
        cnt += i % 6
        i //= 6

    while j > 0:
        cnt += j % 9
        j //= 9

    ans = min(ans, cnt)

print(ans)

Solution (Python):
def main():
  N=int(input())
  values=[]
  val=6
  while val<=N:
    values.append(val)
    val*=6
  
  val=9
  while val<=N:
    values.append(val)
    val*=9
  
  values.sort(reverse=True)
  dp=[N]*(N+1)
  dp[0]=0
  for value in values:
    for i in range(0,N-value+1):
      if dp[i] != N:
        dp[i+value]=min(dp[i]+1,dp[i+value])
        
  
  ans=10**10
  for index,item in enumerate(dp):
    ans=min(ans,item+N-index)
  print(ans)
  pass
if __name__ == '__main__':
  main()

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

def main():
    N = int(input())
    money = [1]
    for i in range(10):
        money.append(money[-1]*6)
    money.append(9)
    for i in range(9):
        money.append(money[-1]*9)
    
    dp = [INF] * (1 + N)
    dp[0] = 0
    for m in money:
        for j in range(m,N + 1):
            dp[j] = min(dp[j],dp[j - m] + 1)
    ans = dp[-1]
    print(ans)
if __name__ == '__main__':
    main()

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

dp=[None]*(n+1) 
dp[0]=0
for i in lst:
    if i<=n:
        dp[i]=1

for i in range(2,n+1):
    kouho=[]
    for j in lst:
        if i-j>=0:
            kouho.append(dp[i-j]+1)
    dp[i]=min(kouho)

print(dp[-1])

Solution (Python):
import sys
INFTY=sys.maxsize

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

def main(n):
    dp=[INFTY]*(n+1)
    dp[0]=0
    dp[1]=1
    for i in range(2,n+1):
        dp[i]=min(dp[i],dp[i-1]+1)  
        k=1
        while(i-6**k>=0):
            dp[i]=min(dp[i],dp[i-6**k]+1)
            k+=1
        k=1
        while(i-9**k>=0):
            dp[i]=min(dp[i],dp[i-9**k]+1)
            k+=1
    return dp[n]

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

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

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

ans = 10 ** 9 + 7
for i in range(N + 1):
    N6 = to_n(N - i, 6)
    N9 = to_n(i, 9)
    res = 0
    for j in N6:  res += int(j)
    for j in N9:  res += int(j)
    ans = min(res, ans)
print(ans)

Solution (Python):
N = int(input())
c = [1]
temp = 6
while(temp <= N):
    c.append(temp)
    temp *= 6
temp = 9
while(temp <= N):
    c.append(temp)
    temp *= 9
m = len(c)

dp = [10 ** 9 + 7 for _ in range(N + 1)]
dp[0] = 0
for i in range(m):
    for j in range(1, N + 1):
        if j - c[i] >= 0:
            dp[j] = min(dp[j], dp[j - c[i]] + 1)
print(dp[N])

Solution (Python):
N = int(input())
m = 10000000
def judge_1(t):
  c = 0
  while t>0:
    c += t%6
    t = t//6  
  return c
def judge_2(t):
  c = 0
  while t>0:
    c += t%9
    t = t//9  
  return c
for i in range(N+1):
  m = min(m, judge_1(i)+judge_2(N-i))
print(m)

Solution (Python):
N = int(input())
dp = [None]*(N+1)
a = 1
while a <= N:
    dp[a] = 1
    a *= 6
a = 1
while a <= N:
    dp[a] = 1
    a *= 9

def f(n):
    if dp[n]:
        return dp[n]
    a = 6
    while a <= n:
        a *= 6
    a //= 6
    b = 9
    while b <= n:
        b *= 9
    b //= 9
    ans = min([f(n-a), f(n-b)])+1
    dp[n] = ans
    return ans
print(f(N))

Solution (Python):
n=int(input())
l6=[6**i for i in range(7)]
l9=[9**i for i in range(1,6)]
m=l6+l9
m.sort()
inf=float("inf")
dp=[inf]*(10**5+1)
dp[0]=0
dp[1]=1
for i in range(1,n+1):
  for mi in m:
    if i-mi>=0:
      dp[i]=min(dp[i-mi]+1,dp[i])
print(dp[n])

Solution (Python):
import functools

import sys
import functools

sys.setrecursionlimit(100000)


def f(r, i):
    
    return r ** i


@functools.lru_cache(maxsize=None)
def solve(N, size):
    if size == -1:
        return N
    b = C[size]
    if N - b >= 0:
        return min(solve(N - b, size) + 1, solve(N, size - 1))
    else:
        return solve(N, size - 1)


if __name__ == "__main__":
    max_N = 10_0000
    N = int(input())

    A = [f(6, i) for i in range(1, 7) if f(6, i) <= N]
    B = [f(9, i) for i in range(1, 7) if f(9, i) <= N]
    C = A + B
    C.sort(reverse=True)
    print(solve(N, len(C) - 1))

Solution (Python):
def main():
    N = int(input())
    ans = 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
        ans = min(ans, cc)
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    N = int(input())
    dp = [-1]*(N + 1)
    dp[0] = 0
    multiples = [1]
    n = 9
    while n <= N:
        multiples.append(n)
        n *= 9
    n = 6
    while n <= N:
        multiples.append(n)
        n *= 6
    multiples.sort(reverse=True)
    
    for ratio in reversed(multiples):
        for i in range(N + 1):
            c = dp[i]
            if c == - 1:
                continue
            if i + ratio > N:
                continue
            if dp[i + ratio] == -1 or dp[i + ratio] > c + 1:
                dp[i + ratio] = c + 1
    
    print(dp[N])

if __name__ == '__main__':
    main()

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

l = [1]
i = 1
while 6 ** i <= 100000:
    l.append(6 ** i)
    i += 1
i = 1
while 9 ** i <= 100000:
    l.append(9 ** i)
    i += 1
l.sort()

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

print(dp[n])

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

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

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

print(dp[N])

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

Solution (Python):
from bisect import bisect_right

n = int(input())

l = [1]
i = 1
while 6 ** i <= 100000:
    l.append(6 ** i)
    i += 1
i = 1
while 9 ** i <= 100000:
    l.append(9 ** i)
    i += 1
l.sort()

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

print(dp[n])