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):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7


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

for i in range(2, N+1):
	L = [6**x for x in range(int(log2(i)/log2(6))+1)] + [9**x for x in range(1, int(log2(i)/log2(9))+1)]
	dp[i] = min([dp[i-y] for y in L]) + 1

print(dp[N])

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

INF = 10**8

def rec(x, memo):
    if x == 0: return 0
    if memo[x] != -1: 
        return memo[x]
    
    res = INF
    pow6 = 1
    while x - pow6 >= 0:
        res = min(res, rec(x-pow6, memo)+1)
        pow6*=6
    
    pow9 = 1
    while x - pow9 >= 0:
        res = min(res, rec(x-pow9, memo)+1)
        pow9*=9

    memo[x] = res
    return res

n = int(input())
memo = [-1]*(n+1)
print(rec(n, memo))

Solution (Python):
n = int(input())
dp = [200000] * (n+10)
dp[0] = 0
for i in range(1,n+1):
    dp[i] = min(dp[i-1]+1, dp[i])
    
    six = 6
    while i - six >= 0:
        dp[i] = min(dp[i-six]+1, dp[i])
        six *= 6 

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

print(dp[n])

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

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

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

print(dp[n])

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

Solution (Python):
n = int(input())
pow6s = [6, 36, 216, 1296, 7776, 46656]
pow9s = [9, 81, 729, 6561, 59049]
coins = sorted([1] + pow6s + pow9s)
dp = [n+1] * (n+1)
dp[0] = 0
dp[1] = 1
for i in range(len(coins)):
    c = coins[i]
    ndp = dp[:]
    for j in range(n+1):
        if j-c >= 0:
            ndp[j] = min(dp[j], ndp[j-c] + 1)
    dp = ndp
print(dp[-1])

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
n = int(input())
pow6s = [6, 36, 216, 1296, 7776, 46656]
pow9s = [9, 81, 729, 6561, 59049]
dp = [-1] * (n+1)
def dfs(n):
    if n == 0:
        return 0
    if dp[n] != -1:
        return dp[n]
    mincount = n + 1
    for p6 in pow6s:
        if n-p6 >= 0:
            mincount = min(mincount, dfs(n-p6) + 1)
    for p9 in pow9s:
        if n-p9 >= 0:
            mincount = min(mincount, dfs(n-p9) + 1)
    
    dp[n] = min(mincount, dfs(n-1) + 1)
    return dp[n]

print(dfs(n))

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


def saiki(tgt, i, count, ans):
    if i == 0 or tgt == 0:
        ans = min(tgt+count, ans)
        return ans

    num = tgt//temp[i]
    while num >= 0:
        nn = tgt - num*temp[i]
        ans = saiki(nn, i-1, count+num, ans)
        if ans < count+num:
            return ans
        num -= 1
    return ans


temp = [1]
a = 1
while n >= 6**a:
    temp.append(6**a)
    a += 1

b = 1
while n >= 9**b:
    temp.append(9**b)
    b += 1

temp.sort()

print(saiki(n, len(temp)-1, 0, 10**9))

Solution (Python):












c = [1] + [6**i for i in range(1,7)] + [9**i for i in range(1,6)]

Inf = int(1e18)

n = int(input())
dp = [Inf] * (n + 1)
dp[0] = 0


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

print(dp[n])

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

N = int(open(0).read())
p = [59049, 46656, 7776, 6561, 1296, 729, 216, 81, 36, 9, 6, 1]

mem = [0] * (N+1)
def dp(n):
    global mem
    if n <= 0:
        return 0
    elif mem[n]:
        return mem[n]
    else:
        mem[n] = min([dp(n-x) + 1 for x in p if n - x >= 0])
        return mem[n]
print(dp(N))

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



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

INF = 10 ** 10

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

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

Solution (Python):
def tmp_ans(total_cost, six_cost):
    res = 0
    tmp = n
    t = six_cost
    while t > 0:
        res += t % 6
        t //= 6
    t = total_cost - six_cost
    while t > 0:
        res += t % 9
        t //= 9
    return res

n = int(input())
ans = n
for x in range(n+1):
    ans = min(ans, tmp_ans(n, x))
print(ans)

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

Solution (Python):



import sys
readline = sys.stdin.readline

N = int(readline())

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

for i in range(len(dp)):
  n = 6
  while i + n < len(dp):
    if dp[i + n] > dp[i] + 1:
      dp[i + n] = dp[i] + 1
    n *= 6
  n = 9
  while i + n < len(dp):
    if dp[i + n] > dp[i] + 1:
      dp[i + n] = dp[i] + 1
    n *= 9
print(dp[N])

Solution (Python):
dp=[1000000 for i in range(100010)]
dp[0]=0
for n in range(1,100010):
  power=1
  while(power<=n):
    dp[n]=min(dp[n],dp[n-power]+1)
    power*=6
  power=1
  while(power<=n):
    dp[n]=min(dp[n],dp[n-power]+1)
    power*=9

i=int(input())
print(dp[i])

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

for i in range(n):
    dp[i+1] = min(dp[i+1],dp[i] + 1)
    cou = 1
    while True:
        if i + 6**cou <= n:
            dp[i+6**cou] = min(dp[i+6**cou],dp[i]+1)
            cou += 1
        elif i + 6**cou > n:
            break
    cou = 1
    while True:
        if i + 9**cou <= n:
            dp[i+9**cou] = min(dp[i+9**cou],dp[i]+1)
            cou += 1
        elif i + 9**cou > n:
            break
print(dp[n])

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

P = [1]

for i in range(1, N):
    if 6**i > N:
        break
    P.append(6**i)

for i in range(1, N):
    if 9**i > N:
        break
    P.append(9**i)

P.sort()

DP = [float('inf')] * (N + 1)
DP[0] = 0
for i in range(N):
    for p in P:
        if i + p > N:
            break
        DP[i+p] = min(DP[i+p], DP[i] + 1)
print(DP[N])

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

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

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

print(dp[n])

Solution (Python):
N = int(input())
A = [1, 6, 6**2, 6**3, 6**4, 6**5, 6**6, 9, 9**2, 9**3, 9**4, 9**5]
dp = [1000000] * 300000
dp[0] = 0

for i in range(N):
    for a in A:
        d = dp[i] + 1
        dp[i + a] = min(dp[i + a], d)

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 amount in range(1,N+1):
	for coin in coin_list[::-1]:
	    if amount-coin >= 0: dp[amount] = min(dp[amount], dp[amount-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 amount in range(1,N+1):
		if amount-coin >= 0: dp[amount] = min(dp[amount], dp[amount-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 amount in range(1,N+1):
	for coin in coin_list:
	    if amount-coin >= 0: dp[amount] = min(dp[amount], dp[amount-coin]+1)
 
print(dp[N])

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

dp = [-1]*(N+1)
dp[0] = 0
dp[1] = 1
for i in range(1, N+1):
    if dp[i] == -1:
        dp[i] = dp[i-1] + 1
        k = 6
        while i >= k:
            dp[i] = min(dp[i], dp[i-k]+1)
            k *= 6
        l = 9
        while i >= l:
            dp[i] = min(dp[i], dp[i-l]+1)
            l  *= 9
print(dp[N])

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

Solution (Python):
import numpy as np

n = int(input())
def solve(n):
    f = [float('inf') for _ in range(n+1)]
    f[0] = 0
    for i in range(1, n+1):
        f[i] = f[i-1] + 1
        k = 6
        l = 9
        while k <= i:
            f[i] = min(f[i], f[i-k] + 1)
            k *= 6
        while l <= i:
            f[i] = min(f[i], f[i-l] + 1)
            l *= 9
    print(f[n])
solve(n)

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
from collections import defaultdict
from collections import deque
from functools import lru_cache






MOD = 10**9+7
INF = float('inf')






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)



def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i])*n**i for i in range(len(str(X))))


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





N = I()

L = set()

for i in range(1000):
  if 6**i <= 100000:
    L.add(6**i)
  else:
    break
for i in range(1000):
  if 9**i <= 100000:
    L.add(9**i)
  else:
    break

count = 1
bag = {N}

while True:
  new_bag = set()
  for i in bag:
    for l in L:
      left = i - l
      if left == 0:
        print(count)
        exit()
      elif left > 0:
        new_bag.add(left)
  bag = new_bag
  count += 1

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

dp = list(range(0, N+1))

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

print(dp[-1])

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

dp = [10**100]*(N + 10**6)
dp[0] = 0
delta = [1, 6, 6**2, 6**3, 6**4, 6**5, 6**6, 9, 9**2, 9**3, 9**4, 9**5]
for i in range(0, N):
    for d in delta:
        dp[i+d] = min(dp[i+d], dp[i] + 1)
print(dp[N])

Solution (Python):
n = int(input())
inf = float('inf')
dp = [inf]*(n+1)
dp[0] = 0
a = 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],dp[i-b]+1)
    else:
        dp[i] = min(dp[i],dp[i-b]+1,dp[i-c]+1)
print(dp[n])

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

def VI(N, init=0):
  return [init for _ in range(N)]
def VVI(N, M, init=0):
  return [[init for _ in range(M)] for _ in range(N)]

def VD(N, init=0.0):
  return [init for _ in range(N)]
def VVD(N, M, init=0.0):
  return [[init for _ in range(M)] for _ in range(N)]

def Decimal(x):
  print("{0:.10f}".format(x))

class Pair:
  def __init__(self, x=0, y=0):
    self.first = x
    self.second = y

  def __repr__(self):
    return '{0} {1}'.format(self.first, self.second)

  def __lt__(self, pi):
    return self.first < pi.second

def POW(x, n):
  ret = 1
  while n:
    if n&1:
      ret *= x
    x *= x
    n >>= 1
  return ret

MAX_N = int(1e5+5)

dp = VI(MAX_N, MAX_N)
dp[0] = 0
dp[1] = 1

for i in range(2, MAX_N):
  dp[i] = min(dp[i], dp[i-1]+1)
  for j in range(10):
    six = POW(6, j)
    if six > i:
      break
    else:
      dp[i] = min(dp[i], dp[i-six]+1)

  for j in range(10):
    nine = POW(9, j)
    if nine > i:
      break
    else:
      dp[i] = min(dp[i], dp[i-nine]+1)

N = int(input().rstrip())
print(dp[N])

Solution (Python):
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial
from bisect import bisect_left 

sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

N = int(input())
INF = 10**18

res = 0
dp = [INF]*(10*N)
dp[0] = 0
for i in range(0, N):
    dp[i+1] = min(dp[i+1], dp[i]+1)

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

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

print(dp[N])

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()

from collections import defaultdict, deque, Counter
from sys import exit
import heapq
import math
import fractions
import copy
from itertools import permutations
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

N = getN()

num = [1]
sixsta = 6
while sixsta < 100000:
    num.append(sixsta)
    sixsta *= 6

ninesta = 9
while ninesta < 100000:
    num.append(ninesta)
    ninesta *= 9
num.sort()

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

Solution (Python):
n = int(input())
list_c = [9 ** i for i in range(6)]
list_c += [6 ** i for i in range(1, 7)]
list_c.sort()

dp = [float('inf')] * (n + 1)
dp[0] = 0
for i in range(n):
    for c in list_c:
        if i + c <= n:
            dp[i + c] = min(dp[i + c], dp[i] + 1)

print(dp[-1])

Solution (Python):


import sys

import math




























def main():
    mod = 1000000007                
    inf = float('inf')              
    
    sys.setrecursionlimit(10**6)    
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())

    def div_n(divisor, num):
        """
        >>> div_n(9, 9**2)
        2
        >>> div_n(9, 9**2-1)
        1
        """
        candidate = int(math.log(num, divisor))
        if pow(divisor,(candidate+1)) == num:
            return candidate+1
        else:
            return candidate
    
    
    n = ii()

    dp = [i for i in range(n+1)]
    for i in range(6, n+1):
        
        dp[i] = min(dp[i], dp[i - pow(6, div_n(6,i))] + 1, dp[i - pow(9, div_n(9,i))] + 1)
    
    print(dp[n])



if __name__ == "__main__":
    
    
    main()

Solution (Python):
import sys
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    N = int(readline())
    coin = [6**i for i in range(10) if 6**i <= N]
    coin += [9**i for i in range(10) if 9**i <= N]
    coin.sort()
    dp = [INF]*(N+1)
    dp[0]=0
    for c in coin:
        for i in range(N+1):
            if i>=c:
                dp[i] = min(dp[i-c]+1, dp[i])
    print(dp[-1])


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import numpy as np
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    N = int(readline())
    coin = [6**i for i in range(10) if 6**i <= N]
    coin += [9**i for i in range(10) if 9**i <= N]

    dp = np.zeros(N+1,dtype=np.int32)
    dp += MOD
    dp[0] = 0
    for c in coin:
        for _ in range(9):
            dp[c:] = np.minimum(dp[:-c]+1, dp[c:])
    print(dp[-1])


if __name__ == '__main__':
    main()

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

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

Solution (Python):
N=int(input())
ans=float("Inf")
for i in range(N+1):
   k=N-i
   k2=i
   six=0
   nine=0
   while k2>0:
      six+=k2%6
      k2//=6
   while k>0:
      nine+=k%9
      k//=9
   ans=min(ans,six+nine)
print(ans)

Solution (Python):
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N = int(input())

dp = [N] * (N + 1)
dp[0] = 0
for i in range(N):
    dp[i + 1] = min(dp[i + 1], dp[i] + 1)
    six = 6
    nine = 9
    for p in range(10):
        if i + six <= N:
            dp[i + six] = min(dp[i + six], dp[i] + 1)
        if i + nine <= N:
            dp[i + nine] = min(dp[i + nine], dp[i] + 1)
        six *= 6
        nine *= 9

print(dp[N])

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

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

def solve():
    inf=10**7
    dp=[inf]*(n+1)
    dp[0]=0
    
    for i in range(1,n+1):
        power=1
        while power<=i:
            dp[i]=min(dp[i],dp[i-power]+1)
            power*=6
    

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

print(solve())

Solution (Python):
n=int(input())
dp=[10**18]*(n+1)
dp[n]=0
for i in range(5,0,-1):
    for j in range(n,0,-1):
        if j-9**i>=0:
            dp[j-9**i]=min(dp[j-9**i],dp[j]+1)

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

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























dp = [0]*(n+1)
moto = []
a = 1
while a <= n:
    a *= 6
    if a <= n:
        moto.append(a)
a = 1
while a <= n:
    a *= 9
    if a <= n:
        moto.append(a)

for i in range(1, n+1):
    tar = [dp[i-1]+1]
    for j in moto:
        if i >= j:
            tar.append(dp[i-j]+1)
    dp[i] = min(tar)
print(dp[n])

Solution (Python):
def ninebank(val):
    left = val
    ret = 0
    div = 9 ** 5
    while div > 0:
        ret += left // div
        left = left % div
        div = div // 9
    return ret


def sixbank(val):
    left = val
    ret = 0
    div = 6 ** 10
    while div > 0:
        ret += left // div
        left = left % div
        div = div // 6
    return ret


n = int(input())
ret = 10 ** 10
for i in range(n+1):
    x = ninebank(i)
    y = sixbank(n - i)
    ret = min(ret, x + y)
print(ret)

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

for i in range(1, n + 1):
    dp[i] = dp[i - 1] + 1
    mlp6 = 6
    while i - mlp6 >= 0:
        dp[i] = min(dp[i], dp[i - mlp6] + 1)
        mlp6 *= 6
    mlp9 = 9
    while i - mlp9 >= 0:
        dp[i] = min(dp[i], dp[i - mlp9] + 1)
        mlp9 *= 9
print(dp[-1])

Solution (Python):









INF = 100100100


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

    memo = [INF] * (N + 100)
    memo[0] = 0

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

    print(memo[N])


if __name__ == '__main__':
    main()

Solution (Python):









INF = 100100100


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

    memo = [INF] * (N + 1)
    memo[0] = 0

    for i in range(1, N + 1):
        for nine in range(1, i + 1):
            if 9**nine > i:
                break
            memo[i] = min(memo[i], memo[i - 9**nine] + 1)
        for six in range(1, i + 1):
            if 6**six > i:
                break
            memo[i] = min(memo[i], memo[i - 6**six] + 1)
        memo[i] = min(memo[i], memo[i - 1] + 1)

    print(memo[N])


if __name__ == '__main__':
    main()

Solution (Python):





import sys



sys.setrecursionlimit(100000)
INF = 100100100

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


def f(n):

    
    if n == 0:
        return 0

    
    if not memo[n] == -1:
        return memo[n]

    ans = INF

    
    for i in range(1, n):
        if 9 ** i > n:
            break
        ans = min(ans, f(n - 9**i) + 1)

    
    for i in range(1, n):
        if 6 ** i > n:
            break
        ans = min(ans, f(n - 6**i) + 1)

    
    ans = min(ans, f(n - 1) + 1)

    
    memo[n] = ans
    return ans


def main():

    print(f(N))


if __name__ == '__main__':
    main()

Solution (Python):





import sys



sys.setrecursionlimit(100000)
INF = float('inf')

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


def f(n):

    
    if n == 0:
        return 0

    
    if not memo[n] == INF:
        return memo[n]

    ans = INF

    
    for i in range(1, n):
        if 9 ** i > n:
            break
        ans = min(ans, f(n - 9**i) + 1)

    
    for i in range(1, n):
        if 6 ** i > n:
            break
        ans = min(ans, f(n - 6**i) + 1)

    
    ans = min(ans, f(n - 1) + 1)

    
    memo[n] = ans
    return ans


def main():
    print(f(N))


if __name__ == '__main__':
    main()

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

    
    
    list = [1]
    list.extend([6 ** i for i in range(1, 7)])
    list.extend([9 ** i for i in range(1, 6)])

    dp = [float("inf")] * 100001
    dp[0] = 0

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

    print(dp[N])

if __name__ == "__main__":
    main()

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

pow6 = [6**i for i in range(1,7)]
pow9 = [9**i for i in range(1,6)]

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

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

    for x in pow6:
        if i+1 - x < 0: break
        dp[i+1] = min(dp[i+1], dp[i+1 - x]+1)
    
    for x in pow9:
        if i+1 - x < 0: break
        dp[i+1] = min(dp[i+1], dp[i+1 - x]+1)
    
print(dp[N])

Solution (Python):
import sys
def I(): return int(sys.stdin.readline().rstrip())
N = I()
dp = [float('INF')]*(N+1)
dp[0] = 0
for i in range(1,N+1):
    dp[i] = dp[i-1]+1
    num6,num9 = 6,9
    while i-num6>=0:
        dp[i] = min(dp[i],dp[i-num6]+1)
        num6 *= 6
    while i-num9>=0:
        dp[i] = min(dp[i],dp[i-num9]+1)
        num9 *= 9
print(dp[-1])

Solution (Python):
import sys
def I(): return int(sys.stdin.readline().rstrip())
N = I()
dp = [float('INF')]*(N+1)
dp[0] = 0
for i in range(1,N+1):
    dp[i] = dp[i-1]+1
    num6,num9 = 6,9
    while 0<=i-num6<=N:
        dp[i] = min(dp[i],dp[i-num6]+1)
        num6 *= 6
    while 0<=i-num9<=N:
        dp[i] = min(dp[i],dp[i-num9]+1)
        num9 *= 9
print(dp[-1])

Solution (Python):

N = int(input())
dp = [float('inf')]*100010
dp[0] = 0

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

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

print(dp[N])

Solution (Python):
import math,numpy, collections

n = int(input())
ans = n
cnt = 0
for i in range(n+1):
    cnt = 0
    x = i
    while x >0:
        cnt += x%6
        x = x//6
    y = n-i
    while y >0:
        cnt += y%9
        y = y//9
    ans = min(ans,cnt)

print(ans)

Solution (Python):
import numpy as np
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)
  for j in range(1,n+1):
    if i-6**j<0: break
    dp[i]=min(dp[i],dp[i-6**j]+1)
    if i-9**j<0: continue
    dp[i]=min(dp[i],dp[i-9**j]+1)
  

print(dp[n])

Solution (Python):
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

n = ni()

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

Solution (Python):
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)
    for j in range(n):
        if i + 6 ** (j + 1) <= n:
            dp[i + 6 ** (j + 1)] = min(dp[i + 6 ** (j + 1)], dp[i] + 1)
        else:
            break
    for k in range(n):
        if i + 9 ** (k + 1) <= n:
            dp[i + 9 ** (k + 1)] = min(dp[i + 9 ** (k + 1)], dp[i] + 1)
        else:
            break

print(dp[n])

Solution (Python):
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)
    for j in range(n):
        if i + 6 ** (j + 1) <= n:
            dp[i + 6 ** (j + 1)] = min(dp[i + 6 ** (j + 1)], dp[i] + 1)
        else:
            break
        for k in range(n):
            if i + 9 ** (k + 1) <= n:
                dp[i + 9 ** (k + 1)] = min(dp[i + 9 ** (k + 1)], dp[i] + 1)
            else:
                break

print(dp[n])

Solution (Python):

import math



def base_10_n(x, n):
    if x == 0:
        return 0
    tmpx = x
    a = int(math.log(x, n))
    ans = 0
    for i in range(a, -1, -1):
        ans += tmpx // n**i
        tmpx %= n**i
    ans += tmpx
    return ans


def s(n, r):
    if n == 0:
        return 0
    return n % r + s(n // r, r)


def main():
    N = int(input())
    ans = 10**12
    for j in range(N+1):
        
        
        c = s(j,6)
        d = s(N-j,9)
        ans = min(ans, c+d)
    print(ans)


if __name__ == "__main__":
    main()

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


list=[99999]*(N+1)
list[0]=0
list[1]=1

max6end =True
i=0
while max6end:
    if N <= 6**i :
        max6=i
        max6end=False
    i+=1
max9end =True
i=0
while max9end:
    if N <= 9**i :
        max9=i
        max9end=False
    i+=1
    

for n in range(1,N+1):
    list[n]=list[n-1]+1
    for i in range(1,max6+1):
        if n < 6**i:
            break
        else:
            if list[n] >= list[n-6**i]+1:
                list[n]=list[n-6**i]+1
    for i in range(1,max9+1):
        if n < 9**i:
            break
        else:
            if list[n] >= list[n-9**i]+1:
                list[n]=list[n-9**i]+1
print(list[N])

Solution (Python):
N = int(input())
tannis = [1]

i = 1
while 6**i <= N:
    tannis.append(6**i)
    i += 1

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

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

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


print(dp[N])

Solution (Python):
from functools import reduce
N = int(input())
amounts = sorted(sum(([6 ** (i + 1), 9 ** i] for i in range(6)), []))
account = 1 << N
times = 0
while (times := times + 1) and not (account := reduce(lambda a, b: a | b, [account >> amount for amount in amounts])) & 1:
    pass
print(times)

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

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

Solution (Python):
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n = inn()
mn = BIG
for i in range(0,n+1,9):
    j = n-i
    sm = 0
    k = i
    while k>0:
        sm += k%9
        k //= 9
    k = j
    while k>0:
        sm += k%6
        k //= 6
    mn = min(mn,sm)
print(mn)