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 solve(n):
    if n < 6:
        return n
    elif n < 9:
        return n - 5
    else:
        now_6 = 6
        while now_6 * 6 <= n:
            now_6 *= 6

        now_9 = 9
        while now_9 * 9 <= n:
            now_9 *= 9
        
        ans = float('inf')
        for i in range(n // now_6 + 1):
            cnt = i + (n - now_6*i) // now_9 + solve((n - now_6*i) % now_9)
            if cnt < ans:
                ans = cnt
        
        return ans

print(solve(int(input())))

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

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

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


num = [1]
for i in range(1, 7):
    num.append(6**i)
for i in range(1, 6):
    num.append(9**i)

for i in range(10**5 + 1):
    for n in num:
        
        if dp[i] != -1 and i + n <= 10**5:
            dp[i + n] = min(dp[i + n], dp[i] + 1)

print(dp[N])

Solution (Python):
N = int(input())
ans = 100000
for A in range(N+1):
    num = 0
    B = N-A
    while A != 0:
        num  += A % 6
        A = A//6
    while B != 0:
        num  += B % 9
        B = B//9
    ans = min(ans,num)
print(ans)

Solution (Python):
def main():
    N = int(input())
    cand = [1]
    dp = [float('inf')] * (N + 5)
    tmp = 6
    cnt = 1
    while tmp**cnt <= N:
        cand.append(tmp**cnt)
        cnt += 1
    tmp = 9
    cnt = 1
    while tmp**cnt <= N:
        cand.append(tmp**cnt)
        cnt += 1
    cand.sort()
    dp[0] = 0
    for i in range(N+1):
        for c in cand:
            if i + c <= N:
                dp[i+c] = min(dp[i+c], dp[i] + 1)
    print(dp[N])

if __name__ == "__main__":
    main()

Solution (Python):
import sys
import math
sys.setrecursionlimit(10**6)

N = int(input())

INF = 10**10

dp = [0]*(N+1)

for i in range(N+1):
    dp[i] = INF
    
W = [1,6,9]

def rec(v):
    if dp[v] < INF:
        return dp[v]
    if v == 0:
        dp[v] = 0
        return 0
    
    
    res = INF
    for w in range(3):
        for x in range(int(math.log(N+1,6))+1):
            n = W[w]**x
            if v<n:
                continue
            res = min(res,rec(v-n) + 1)
            
            dp[v] = res
    return res
rec(N)
print(dp[N])

Solution (Python):

import math
N = int(input())

INF = 10**10

dp = [0]*(N+1)

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

dp[0] = 0
W = [1,6,9]



for v in range(1,N+1):
    for w in range(3):
        for x in range(int(math.log(N+1,6))+1):
            
            n = W[w]**x
            if v-n < 0:
                continue
            dp[v] = min(dp[v],dp[v-n] + 1)
print(dp[N])

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

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

    return res


def solve(N):

    ans = 10 ** 5
    for i in range(N+1):
        tmp = fn(i, 6) + fn(N-i, 9)
        ans = min(ans, tmp)

    return ans


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

Solution (Python):


n = int(input())

ans = n

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

print(ans)

Solution (Python):



"""

ベンチマーク
コイン問題 (※ larger = False): http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4696859
E - Crested Ibis vs Monster (※ larger = True): https://atcoder.jp/contests/abc153/submissions/15396586

"""


def coin(larger=False, single=False):
    """
    ナップサックに入れる重さが W 丁度になる時の価値の最小値
    :param larger: False = (重さ = W)の時の最小価値
                   True  = (重さ =< W)の時の最小価値
    :param single: False = 重複あり

    dp[weight <= W+1] = 重さを固定した時の最小価値
    dp[W+1] = 重さがWより大きい時の最小価値
    """
    W2 = W + 1              
    dp_max = float("inf")   
    dp = [dp_max] * (W2 + 1)
    dp[0] = 0               

    for item in range(N):
        if single:
            S = range(W2, weight_list[item] - 1, -1)
        else:
            S = range(W2)
        for weight in S:
            dp[min2(weight + weight_list[item], W2)] = min2(dp[min2(weight + weight_list[item], W2)], dp[weight] + cost_list[item])
    if larger:
        return min(dp[w] for w in range(W, W2+1))
    else:
        return dp[W]


import sys
input = sys.stdin.readline


def max2(x, y):
    return x if x > y else y

def min2(x, y):
    return x if x < y else y

W = int(input())
cost_list = [1]
weight_list = [1]
p = 6
while p<=W:
    cost_list.append(1)
    weight_list.append(p)
    p *= 6
p = 9
while p<=W:
    cost_list.append(1)
    weight_list.append(p)
    p *= 9
N = len(weight_list)

print(coin(larger=False, single=False))

Solution (Python):
import sys
sys.setrecursionlimit(100000000)
n=int(input())
memo=[-1]*(10**7)
memo[0]=0
def rec(a:int):
    if a==0:
        return 0
    if memo[a]!=-1:
        return memo[a]
    res=100000
    for i in range(1,9):
        if 0<=a-6**i:
            res=min(res,rec(a-6**i)+1)
    for j in range(1,9):
        if 0<=a-9**j:
            res=min(res,rec(a-9**j)+1)
    res=min(res,rec(a-1)+1)

    memo[a] = res

    return res
print(rec(n))

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

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

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

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

import math
dp[1] = 1
for i in range(2, N+1):
    dp[i] = dp[i-1] + 1
    for j in range(math.floor(math.log(i, 6)) + 1):
        dp[i] = min(dp[i], dp[i - 6 ** j] + 1)
    for k in range(math.floor(math.log(i, 9) + 0.00000001) + 1):
        dp[i] = min(dp[i], dp[i - 9 ** k] + 1)


print(dp[N])

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

N=int(input())

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

Solution (Python):
n=int(input())
def f(x):
    ans=0
    while x>0:
        ans+=x%6
        x=x//6
    return ans
def g(x):
    ans=0
    while x>0:
        ans+=x%9
        x=x//9
    return ans
ans=n
for i in range(n+1): 
  ans=min(ans,f(i)+g(n-i))
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
def f(n):
    if dp[n] != -1:
        return dp[n]
    res = N
    for i in range(N):
        if n < 6**i:
            break
        res = min(res, f(n-6**i)+1)
    for i in range(N):
        if n < 9**i:
            break
        res = min(res, f(n-9**i)+1)
    dp[n] = res
    return res

N = int(input())
dp = [-1]*(N+1)
dp[0] = 0
f(N)
print(dp[N])

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

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

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

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

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

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

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

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

Solution (Python):
n=int(input())
def f(x):
    ans=0
    while x>0:
        ans+=x%6
        x=x//6
    return ans
def g(x):
    ans=0
    while x>0:
        ans+=x%9
        x=x//9
    return ans
ans=n
for i in range(n+1):
    ans=min(ans,f(i)+g(n-i))
print(ans)

Solution (Python):
n=int(input())
def f(x):
    ans=0
    while x>0:
        ans+=x%6
        x=x//6
    return ans
def g(x):
    ans=0
    while x>0:
        ans+=x%9
        x=x//9
    return ans
ans=n
for i in range(n+1):
    ans=min(ans,f(i)+g(n-i))
print(ans)

Solution (Python):
from collections import deque
n=int(input())
table=[-1]*100001
table[0]=0
d=deque()
d.append(0)
can=[]
can.append(1)
for i in range(1,50):
    if 6**i<=100000:
        can.append(6**i)
    else:
        break
    if 9**i<=100000:
        can.append(9**i)
while d:
    w=d.popleft()
    for i in can:
        if w+i>100000:
            continue
        if not table[w+i]==-1:
            continue
        table[w+i]=table[w]+1
        d.append(w+i)
print(table[n])

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

dp = [0]*(n+10)

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

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

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

print(dp[n])

Solution (Python):
import numpy as np

N = int(input())



def main(n):
    dp = []
    for i in range(10**5+1):
        dp.append(i)
    dp = np.array(dp)
    powers = [1]
    i = 1
    while True:
        if 6**i>10**5:
            break
        powers.append(6**i)
        if 9**i<=10**5:
            powers.append(9**i)
        i += 1
    powers.sort()
    for i in range(1,10**5+1):
        for j in range(len(powers)):
            if powers[j]>i:
                break
            dp[i] = min(dp[i],dp[i-powers[j]]+1)

    print(dp[n])            

if __name__=="__main__":
    main(N)

Solution (Python):
def main3():
    import sys
    sys.setrecursionlimit(100000000)

    N=int(input())
    dp=[-1 for n in range(N+1)]
    dp[0]=0
    dp[1]=1
    def rec(x,dp):
        if x==1:
            return dp[1]
        elif x==0:
            return dp[0]
        else:
            l=[]
            i=0
            j=0
            while 9**(i+1)<=x:
                i+=1
            while 6**(j+1)<=x:
                j+=1
            for k in reversed(range(i+1)):
                tmp=x-9**k
                if dp[tmp]!=-1:
                    l.append(dp[tmp]+1)
                else:
                    l.append(rec(tmp,dp)+1)
            for k in reversed(range(j+1)):
                tmp=x-6**k
                if dp[tmp]!=-1:
                    l.append(dp[tmp]+1)
                else:
                    l.append(rec(tmp,dp)+1)
            dp[x]=min(l)
            return dp[x]

    return rec(N,dp)
        
if __name__=="__main__":
    print(main3())

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

Solution (Python):
from collections import deque
n = int(input())

dp = [-1 for _ in range(10**6)]
dp[0] = 0

que = deque([0])

while que:
    v = que.popleft()
    j6 = 1
    while v+j6 <= n:
        if dp[v+j6] == -1:
            dp[v+j6] = dp[v]+1
            que.append(v+j6)
        j6 *= 6
            
    j9 = 1
    while v+j9 <= n:
        if dp[v+j9] == -1:
            dp[v+j9] = dp[v]+1
            que.append(v+j9)
        j9 *= 9
            
print(dp[n])

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

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

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

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

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

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

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


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

mini = n

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

Solution (Python):
def f(a,x):
    l=[]
    while x!=0:
        l.append(x%a)
        x//=a
    return sum(l)

def main():
    N=int(input())
    MIN=100000
    for k in range(N+1):
        MIN=min(MIN,f(9,k)+f(6,(N-k)))
    return MIN

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

Solution (Python):
import sys;      from decimal import Decimal
import math;     from itertools import combinations, product
import bisect;   from collections import Counter, deque, defaultdict


MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def lcm(a: int, b: int) -> int: return (a * b) // math.gcd(a, b)

import numpy as np
from numba import njit, i8

@njit(i8(i8))
def dp(N):
    dp = np.full(100005, INF, dtype=np.int64)
    dp[0] = 0
    
    for n in range(1, N + 1):
        pow6 = 1
        while pow6 <= n:
            dp[n] = min(dp[n], dp[n - pow6] + 1)
            pow6 *= 6
        pow9 = 1
        while pow9 <= n:
            dp[n] = min(dp[n], dp[n - pow9] + 1)
            pow9 *= 9
    
    return dp[n]

def Main():
    n = read_int()
    print(dp(n))    

if __name__ ==  '__main__':
    Main()

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

dp=[0]


for i in range(1,n+1):
    c = []
    c.append(dp[i-1]+1)
    p6=1
    while i >=6**p6:
        c.append(dp[i-6**p6]+1)
        p6 +=1

    p9=1
    while i >=9**p9:
        c.append(dp[i-9**p9]+1)
        p9 +=1

    dp.append(min(c))

print(dp[n])

Solution (Python):
import math

n = int(input())

dp = [n] * (n+1)

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

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

for i in range(1, n+1):
    dp[i] = min(dp[i-1]+1, dp[i])
    for x in range(1, p+10):
        y = pow(6, x)
        if i - y >= 0:
            dp[i] = min(dp[i-y] + 1, dp[i])
        else:
            break
    for x in range(1, q+10):
        y = pow(9, x)
        if i - y >= 0:
            dp[i] = min(dp[i-y] + 1, dp[i])
        else:
            break

print(dp[n])

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

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

print(dp[N])

Solution (Python):
import math
power_6 = [6 ** i for i in range(int(math.log(100000, 6)) + 1)]
power_9 = [9 ** i for i in range(int(math.log(100000, 9)) + 1)]
p = list(set(power_6 + power_9))
p.sort()
p.append(100001)

N = int(input())
 
idx = 0
cnt = [0]
i = 1
while i < N + 1:
  if p[idx] <= i < p[idx + 1]:
    c = 0
    if idx == 0:
      cnt.append(i)
    else:
      c = [cnt[i - p[j]] + 1 for j in range(idx + 1)]
      cnt.append(min(c))
    i += 1
  else:
    idx += 1

print(cnt[N])

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

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

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

Solution (Python):
import math
N=int(input())
dp=[math.inf for _ in range(N+1)]
dp[0]=0
for i in range(1,N+1):
	p=1
	q=1
	while p<=i:
		dp[i]=min(dp[i],dp[i-p]+1)
		p*=6
	while q<=i:
		dp[i]=min(dp[i],dp[i-q]+1)
		q*=9
print(dp[N])

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

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

inf=float('inf')
dp=[inf for _ in range(100000+1)]
dp[0]=0
dp[1]=1

for x in range(1,100001):
  for b in a:
    if b<=x:
      dp[x]=min(dp[x],dp[x-b]+1)
      
print(dp[n])

Solution (Python):
import math


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    N = read_int()
    dp = [math.inf]*(N+1)
    dp[0] = 0
    for i in range(N):
        if i+1 <= N:
            dp[i+1] = min(dp[i+1], dp[i]+1)
            six = 6
            while i+six <= N:
                dp[i+six] = min(dp[i+six], dp[i]+1)
                six *= 6
            nine = 9
            while i+nine <= N:
                dp[i+nine] = min(dp[i+nine], dp[i]+1)
                nine *= 9
    return dp[N]


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

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

patterns = []
patterns.append(1)

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

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

dp = [float('inf')] * (N + 1)
dp[0] = 0
for n in range(1, N + 1):
    for p in patterns:
        if n - p < 0:
            continue

        dp[n] = min(dp[n - p] + 1, dp[n])


print(dp[-1])

Solution (Python):
n=int(input())
tab=[10**8 for i in range(n+1)]
tab[0]=0

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

print(tab[-1])

Solution (Python):


n = int(input())

ans = [-1]*(n+1)

ans[0] = 0
for i in range(1, n+1):
    num = i
    data = ans[i-1]+1
    for j in range(8):
        index = i-6**j
        if index < 0:
            break
        data = min(data, ans[index]+1)
    for j in range(8):
        index = i-9**j
        if index < 0:
            break
        data = min(data, ans[index]+1)
    ans[i] = data
print(ans[-1])

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

dp = [math.inf] * (n+1)

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

print(dp[n])

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

INF = 10 ** 9


def base(x, y):
    ret = 0
    while x >= y:
        ret += x % y
        x //= y
    ret += x
    return ret
        

def main():
    ans = INF
    for i in range(N + 1):
        v = base(i, 6) + base(N - i, 9)
        ans = min(ans, v)
    print(ans)


if __name__ == "__main__":
    main()

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

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

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

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

print(dp[-1])

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

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

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

print(dp[-1])

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

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

Solution (Python):



def main():
    n = int(input())
    dp = [float('inf') for _ in range(n + 100)]
    dp[0] = 0

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

        six = 6

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

        nine = 9

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

    print(dp[n])


if __name__ == '__main__':
    main()

Solution (Python):



def main():
    n = int(input())
    dp = [float('inf') for _ in range(n + 100)]
    dp[0] = 0

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

        six = 6

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

        nine = 9

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

    print(dp[n])


if __name__ == '__main__':
    main()

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

N = int(input())

ss = set()
n = 6
while n <= 10**5:
    ss.add(n)
    n *= 6
n = 9
while n <= 10**5:
    ss.add(n)
    n *= 9

dp = [None] * (N+1)

def rec(n):
    if dp[n] is not None:
        return dp[n]
    tmp = n
    for s in ss:
        if s > n: continue
        if s == n:
            tmp = 1
            break
        tmp = min(tmp, 1 + rec(n-s))
    dp[n] = tmp
    return tmp

print(rec(N))

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


dp = [float('inf')] * (N + 1)
dp[0] = 0
operates = sorted([1, 6, 36, 216, 1296, 7776, 46656, 9, 81, 729, 6561, 59049])
for i in range(N):
    for ope in operates:
        if i + ope > N:
            break
        dp[i + ope] = min(dp[i + ope], dp[i] + 1)

print(dp[N])

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

dp = [0] * 100001

dp[1] = 1

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

print(dp[N])

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def f(n, a):
    ans = 0
    while n > 0:
        ans += n % a
        n //= a
    return ans


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

    ans = INF
    for i in range(N + 1):
        ans = min(ans, f(i, 6) + f(N - i, 9))

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

    amt = [1]
    a = 6
    while a <= N:
        amt.append(a)
        a *= 6
    a = 9
    while a <= N:
        amt.append(a)
        a *= 9

    dp = [INF] * (N + 1)
    dp[0] = 0
    for i in range(1, N + 1):
        for a in amt:
            if i >= a and dp[i] > dp[i - a]:
                dp[i] = dp[i - a] + 1

    print(dp[N])

    return


if __name__ == '__main__':
    main()

Solution (Python):
def sinsuuton(X, n): 
    if (int(X/n)):
        return sinsuuton(int(X/n), n)+str(X%n)
    return str(X%n)
def sinsuutoo10(X,n): 
    return sum([ X[-i-1]*n**i for i in range(len(X)) ])
n=int(input())
ans=float("inf")
for i in range(n+1):
    t=i
    now=0
    t6= sinsuuton(t, 6)
    now+= sum([int(i) for i in t6])
    t=n-i
    t9= sinsuuton(t, 9)
    now+= sum([int(i) for i in t9])
    ans=min(ans,now)

print(ans)

Solution (Python):


def main():
	n = int(input())
	dp = [0 for i in range(n+4)]
	dp[0]=0
	for i in range(1, n+2):
		p = 1
		dp[i]=1000000000000000
		while i>=p:
			dp[i]=min(dp[i] , dp[i-p]+1)
			p =p*9
		p=1
		while i>=p:
			dp[i]=min(dp[i] , dp[i-p]+1)
			p = p*6
	print(dp[n])
if __name__=="__main__":
	main()

Solution (Python):

def main():
	n = int(input())
	dp = [0 for i in range(n+4)]
	dp[0]=0
	for i in range(1, n+2):
		p = 1
		dp[i]=1000000000000000
		while i>=p:
			dp[i]=min(dp[i] , dp[i-p]+1)
			p =p*9
		p=1
		while i>=p:
			dp[i]=min(dp[i] , dp[i-p]+1)
			p = p*6
	print(dp[n])
if __name__=="__main__":
	main()

Solution (Python):
N = int(input())
Cash = sorted([1]+[6**T for T in range(1,7)]+[9**T for T in range(1,6)])
DPList = [0]*(N+1)
for TN in range(1,N+1):
    DPList[TN] = min(DPList[TN-TC]+1 if TN>=TC else 1000000 for TC in Cash)
print(DPList[N])

Solution (Python):
from collections import deque
n = int(input())
cnt = 0
d = {n:0}
q = deque([n])
while q[0] > -5:
    t = q.popleft()
    cnt = d[t]
    
    a = 1
    b = 1
    while 6**a <= t:
        a += 1
    while 9**b <= t:
        b += 1
    a -= 1
    b -= 1
    
    if t-6**a in d:
        if d[t-6**a] > cnt+1:
            d[t-6**a] = cnt+1
            q.append(t-6**a)
    else:
        d[t-6**a] = cnt+1
        q.append(t-6**a)
    if t-9**b in d:
        if d[t-9**b] > cnt+1:
            d[t-9**b] = cnt+1
            q.append(t-9**b)
    else:
        d[t-9**b] = cnt+1
        q.append(t-9**b)
    
print(d[0])

Solution (Python):
def sub_cnt(c, b):
    cnt = 0
    for i in b:
        while c >= i:
            c -= i
            cnt += 1
    return cnt

n = int(input())

b6 = [6**i for i in range(6, -1, -1)]
b9 = [9**i for i in range(5, -1, -1)]

ans = 10**9
n9 = n // 9
for c9 in range(n9+1):
    cnt = 0
    cn = n - c9*9
    c6 = cn // 6
    c1 = cn % 6
    
    cnt += sub_cnt(c9, b9)
    cnt += sub_cnt(c6, b6)
    cnt += c1
    ans = min(ans, cnt)
print(ans)

Solution (Python):
def sub_cnt(c, b):
    cnt = 0
    for i in b:
        while c >= i:
            c -= i
            cnt += 1
    return cnt

n = int(input())

b6 = [6**i for i in range(6, -1, -1)]
b9 = [9**i for i in range(5, -1, -1)]

ans = 10**9
n9 = n // 9
for c9 in range(n9+1):
    cnt = 0
    cn = n - c9*9
    c6 = cn // 6
    c1 = cn % 6
    
    cnt += sub_cnt(c9, b9)
    cnt += sub_cnt(c6, b6)
    cnt += c1
    ans = min(ans, cnt)
print(ans)

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

a=1

lst=[]

while a<=n:
  dp[a]=1
  lst+=[a]
  a*=6

a=1

while a<=n:
  dp[a]=1
  lst+=[a]
  a*=9

for i in range(n):
  if dp[i]!=None:
    for j in lst:
      if i+j<=n:
        if dp[i+j]!=None:
          dp[i+j]=min(dp[i+j],dp[i]+1)
        else:
          dp[i+j]=dp[i]+1

print(dp[n])

Solution (Python):
import math

n = int(input())
t = 100000 + 10

dp = [10**18] * (t+10)
dp[0] = 0

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

for i in range(t-1):
    s = t-i
    for j in range(int(math.log(s, 9)+1)):
        dp[i+9**j] = min(dp[i+9**j], dp[i]+1)
    for k in range(int(math.log(s, 6)+1)):
        dp[i+6**k] = min(dp[i+6**k], dp[i]+1)


print(dp[n])

Solution (Python):
from itertools import product

n = int(input())

pow6 = [pow(6, i + 1) for i in range(6)]
pow9 = [pow(9, i) for i in range(6)][::-1]

ans = n
for l in product(range(6), repeat=6):
    cnt = sum(l)
    num = n - sum(pi * li for pi, li in zip(pow6, l))
    if num >= 0:
        tmp = 0
        while num > 0:
            if pow9[tmp] > num:
                tmp += 1
            elif pow9[tmp] <= num:
                num -= pow9[tmp]
                cnt += 1
        ans = min(ans, cnt)
print(ans)

Solution (Python):
from itertools import product

n = int(input())

pow6 = [pow(6, i + 1) for i in range(6)]
pow9 = [pow(9, i) for i in range(6)][::-1]

ans = n
for l in product(range(6), repeat=6):
    cnt = sum(l)
    num = n - sum(pi * li for pi, li in zip(pow6, l))
    if num >= 0:
        tmp = 0
        while num > 0:
            if pow9[tmp] > num:
                tmp += 1
            elif pow9[tmp] <= num:
                num -= pow9[tmp]
                cnt += 1
        ans = min(ans, cnt)
print(ans)

Solution (Python):

        
def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()

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


    




                
if __name__ == '__main__':
    main()

Solution (Python):
from functools import lru_cache

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

if __name__ == "__main__":
    main()

Solution (Python):
n=int(input())
import bisect
l=[1,6,9,36,81,216,729,1296,6561,7776,46656,59049]
def draw(x,y):
    ind=bisect.bisect_right(l,x)-1
    if ind==0:
        return y+x
    else:
        y += 1
        x1=x-l[ind]
        x2=x-l[ind-1]
        if x1==0 or x2==0:
            return y
        else:
            return(min(draw(x1,y),draw(x2,y)))
print(draw(n,0))

Solution (Python):
n=int(input())
ans=n
for i in range(n+1):
    c=0
    t=i
    while(t>0):
        c+=(t%6)
        t=(t//6)
    t=n-i
    while(t>0):
        c+=(t%9)
        t=(t//9)
    if ans>c:
        ans=c
print(ans)

Solution (Python):
import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy
INF = 10**9

if __name__ == "__main__":
    n = int(input())
    m = [1]
    dp = [101010]*201010
    t = 6
    q = 9
    while t<=n:
        m.append(t)
        t*=6
    while q<=n:
        m.append(q)
        q*=9
    for i in m:
        dp[i] = 1
    
    for i in range(1,n):
        for j in m:
            dp[i+j] = min(dp[i+j],dp[i]+1)
    print(dp[n])

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


dp = [101010] * 201010
money = [1]
t = 6
q = 9
while t <= N:
    money.append(t)
    t*=6
while q <= N:
    money.append(q)
    q*=9

for m in money:
    dp[m] = 1

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

print(dp[N])

Solution (Python):
from math import log

N=int(input())

dp = [0]*(N+1)

e6 = 0
e9 = 0
for i in range(1,N+1):
  for j in range(e6,12):
    if 6**j>i:
      e6 = j-1
      break
  for j in range(e9,12):
    if 9**j>i:
      e9 = j-1
      break
  dp[i] = min(dp[i-1],dp[i-int(6**e6)],dp[i-int(9**e9)])+1
  
print(dp[-1])