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

def count(n, b):
    res = 0
    while n:
        res += n % b
        n //= b
    return res

n = int(sys.stdin.readline().rstrip())

def main():
    res = float('inf')
    for i in range(n + 1):
        res = min(res, count(i, 6) + count(n - i, 9))
    print(res)

if __name__ ==  '__main__':
    main()

Solution (Python):
import sys

def count(n, b):
    res = 0
    while n:
        n, r = divmod(n, b)
        res += r
    return res

n = int(sys.stdin.readline().rstrip())

def main():
    res = float('inf')
    for i in range(n + 1):
        res = min(res, count(i, 6) + count(n - i, 9))
    print(res)

if __name__ ==  '__main__':
    main()

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

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

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

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

dp = [0] * (n+1)
    
for i in range(1, n+1):
  dp[i] = dp[i-1] + 1
  for l6 in L6:
    if i - l6 >= 0:
      dp[i] = min(dp[i], dp[i - l6] + 1)
  for l9 in L9:
    if i - l9 >= 0:
      dp[i] = min(dp[i], dp[i - l9] + 1)
print(dp[n])

Solution (Python):




mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    n = int(input())
    def count_(num,x):
        i = 0
        while num > 0:
            i += num % x
            num //= x
        return i
    ans = n

    for j in range(n + 1):
        ans = min(ans,count_(j,6)+count_(n-j,9))
    print(ans)




if __name__ == '__main__':
  main()

Solution (Python):
n = int(input())
dp = [10**5]*(10**5+1)
dp[0] = 0
for i in range(n+1):
  if i >= 1:
    dp[i] = min(dp[i-1]+1,dp[i])
  if i >= 6:
    dp[i] = min(dp[i-6]+1,dp[i])
  if i >= 9:
    dp[i] = min(dp[i-9]+1,dp[i])
  if i >= 36:
    dp[i] = min(dp[i-36]+1,dp[i])
  if i >= 81:
    dp[i] = min(dp[i-81]+1,dp[i])
  if i >= 216:
    dp[i] = min(dp[i-216]+1,dp[i])
  if i >= 729:
    dp[i] = min(dp[i-729]+1,dp[i])
  if i >= 1296:
    dp[i] = min(dp[i-1296]+1,dp[i]) 
  if i >= 6561:
    dp[i] = min(dp[i-6561]+1,dp[i])
  if i >= 7776:
    dp[i] = min(dp[i-7776]+1,dp[i])
  if i >= 46656:
    dp[i] = min(dp[i-46656]+1,dp[i])
  if i >= 59049:
    dp[i] = min(dp[i-59049]+1,dp[i])
print(dp[n])

Solution (Python):
def cnt(n,p):
    tmp=0
    m=n
    while(m>0):
        tmp+=m%p
        m//=p
    return tmp
ans=10**15
N=int(input())
for i in range(N+1):
    ans=min(ans,cnt(i,6)+cnt(N-i,9))
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
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(1, 8):
    if i + pow(6, j) <= N: dp[i + pow(6, j)] = min(dp[i + pow(6, j)], dp[i] + 1)
    if i + pow(9, j) <= N: dp[i + pow(9, j)] = min(dp[i + pow(9, j)], dp[i] + 1)
print(dp[-1])

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

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

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

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

print(dp[-1])

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

six = 0
while True:
    if 6**(six+1) > n:
        break
    six += 1

nine = 0
while True:
    if 9**(nine+1) > n:
        break
    nine += 1

for a, b in zip([1, 6, 9], [1, six, nine]):
    for i in range(1, b+1):
        k = a**i
        for j in range(n):
            if j+k > n:
                break
            dp[j+k] = min(dp[j+k], dp[j]+1)
print(dp[n])

Solution (Python):
import math
import string
import collections
from collections import Counter
from collections import deque
import sys
sys.setrecursionlimit(2*10**5)
INF = 2**60


def readints():
    return list(map(int, input().split()))


def nCr(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor



dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]

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

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

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

def sieves_of_e(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n+1, i): is_prime[j] = False
    return is_prime

N = iin()

money = []
pow6 = 1
while pow6 <= N:
    money.append(pow6)
    pow6 *= 6
pow9 = 9
while pow9 <= N:
    money.append(pow9)
    pow9 *= 9
lm = len(money)
dp = [INF for _ in range(N+1)]
dp[0] = 0
for i in range(lm):
    for j in range(N+1):
        if j - money[i] >= 0:
            dp[j] = min(dp[j], dp[j-money[i]]+1)
print(dp[N])

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

def sieves_of_e(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n+1, i): is_prime[j] = False
    return is_prime

N = iin()


money = []
pow6 = 1
while pow6 <= N:
    money.append(pow6)
    pow6 *= 6
pow9 = 9
while pow9 <= N:
    money.append(pow9)
    pow9 *= 9
lm = len(money)
dp = [[INF for _ in range(N+1)] for _ in range(lm+1)]
dp[0][0] = 0
for i in range(lm):
    for j in range(N+1):
        dp[i+1][j] = dp[i][j]
        if j - money[i] >= 0:
            dp[i+1][j] = min(dp[i+1][j], dp[i+1][j-money[i]]+1)
print(dp[lm][N])

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

def sieves_of_e(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n+1, i): is_prime[j] = False
    return is_prime

N = iin()

dp = [-1 for _ in range(N+1)]
dp[0] = 0
queue = deque([0])

while len(queue) > 0:
    current = queue.popleft()
    
    pow6 = 1
    while current+pow6 <= N:
        if dp[current+pow6] == -1:
            queue.append(current+pow6)
            dp[current+pow6] = dp[current]+1
        pow6 *= 6

    pow9 = 1
    while current+pow9 <= N:
        if dp[current+pow9] == -1:
            queue.append(current+pow9)
            dp[current+pow9] = dp[current]+1
        pow9 *= 9
print(dp[N])

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

def sieves_of_e(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n+1, i): is_prime[j] = False
    return is_prime

N = iin()

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

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

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

def sieves_of_e(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n+1, i): is_prime[j] = False
    return is_prime

N = iin()

dp = [INF for _ in range(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):
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from decimal import *
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
INF = float('inf') 
def gcd(a,b):return fractions.gcd(a,b) 
def lcm(a,b):return (a*b) // fractions.gcd(a,b) 
def iin(): return int(sys.stdin.readline()) 
def ifn(): return float(sys.stdin.readline()) 
def isn(): return sys.stdin.readline().split() 
def imn(): return map(int, sys.stdin.readline().split()) 
def imnn(): return map(lambda x:int(x)-1, sys.stdin.readline().split()) 
def fmn(): return map(float, sys.stdin.readline().split()) 
def iln(): return list(map(int, sys.stdin.readline().split())) 
def iln_s(): return sorted(iln()) 
def iln_r(): return sorted(iln(), reverse=True) 
def fln(): return list(map(float, sys.stdin.readline().split())) 
def join(l, s=''): return s.join(l) 
def perm(l, n): return itertools.permutations(l, n) 
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) 
def comb(l, n): return itertools.combinations(l, n) 
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) 
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 
def m_add(a,b): return (a+b) % MOD
def print_list(l): print(*l, sep='\n')
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def No(): print('No')

def sieves_of_e(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n+1, i): is_prime[j] = False
    return is_prime

N = iin()

memo = [-1 for _ in range(N+1)]

def rec(n):
    if n == 0: return 0
    if memo[n] != -1: return memo[n]
    res = n
    pow6 = 1
    while pow6 <= n: 
        res = min(res, rec(n-pow6)+1)
        pow6 *= 6
    pow9 = 1
    while pow9 <= n: 
        res = min(res, rec(n-pow9)+1)
        pow9 *= 9
    memo[n] = res
    return memo[n]
print(rec(N))

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

print(dp[n])

Solution (Python):
import math
n=int(input())
l1=math.floor(math.log(n,6))
l2=math.floor(math.log(n,9))
dp=[i for i in range(n+1)]
for i in range(1,l1+1):
    for j in range(n):
        if j+6**i<n+1:
            dp[j+6**i]=min(dp[j]+1,dp[j+6**i])
for i in range(1,l1+1):
    for j in range(n):
        if j+9**i<n+1:
            dp[j+9**i]=min(dp[j]+1,dp[j+9**i])
print(dp[-1])

Solution (Python):
n = int(input())
F = [0]
for i in range(1, n+1):
    A = [F[i-1]+1]
    j = 1
    while i-6**j >= 0:
        A.append(F[i-6**j]+1)
        j += 1
    j = 1
    while i-9**j >= 0:
        A.append(F[i-9**j]+1)
        j += 1
    F.append(min(A))
print(F[n])

Solution (Python):
import math
n=int(input())
l1=math.ceil(math.log(n,6))
l2=math.ceil(math.log(n,9))
dp=[i for i in range(n+1)]
for i in range(1,l1+1):
    for j in range(n):
        if j+6**i<n+1:
            dp[j+6**i]=min(dp[j]+1,dp[j+6**i])
for i in range(1,l1+1):
    for j in range(n):
        if j+9**i<n+1:
            dp[j+9**i]=min(dp[j]+1,dp[j+9**i])
print(dp[-1])

Solution (Python):
import math
n=int(input())
l1=math.ceil(math.log(n,6))
l2=math.ceil(math.log(n,9))
dp=[i for i in range(n+1)]
for i in range(1,l1+1):
    for j in range(n):
        if j+6**i<n+1:
            dp[j+6**i]=min(dp[j]+1,dp[j+6**i])
for i in range(1,l1+1):
    for j in range(n):
        if j+9**i<n+1:
            dp[j+9**i]=min(dp[j]+1,dp[j+9**i])
print(dp[-1])

Solution (Python):
import numpy as np
N=int(input())
six=[1]
nine=[]
for i in range(1,N):
  six.append(6**i)
  nine.append(9**i)
  if 6**i>N:
    break
six=np.array(six)
nine=np.array(nine)
L=np.concatenate([six,nine])    
now=N
count=0
dp=np.ones(N+L.max()+1)*10**9
dp[1]=1
dp[0]=0

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

  
print(int(dp[N]))

Solution (Python):
import numpy as np
N=int(input())
six=[1]
nine=[]
for i in range(1,N):
  six.append(6**i)
  nine.append(9**i)
  if 6**i>N:
    break
six=np.array(six)
nine=np.array(nine)
L=np.concatenate([six,nine])    
now=N
count=0
dp=np.ones(N+L.max()+1)*np.inf
dp[1]=1
dp[0]=0

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

  
print(int(dp[N]))

Solution (Python):
import sys
sys.setrecursionlimit(10000)
def resolve():
    N = int(input())
    candidates = []
    x6 = 6
    x9 = 9
    while True:
        if x6 > N and x9 > N:
            break
        if x6 <= N:
            candidates.append(x6)
        if x9 <= N:
            candidates.append(x9)
        x6 = x6 * 6
        x9 = x9 * 9
    candidates.sort()
    
    dic = {}
    res = rec(candidates, N, dic)
    print(res)

def rec(ary, target, dic):
    
    if target in dic:
        return dic[target]
    if len(ary) < 1:
        return target
    if ary[0] > target:
        dic[target] = target
        return target
    counts = []
    for i in ary:
        if target - i < 0:
            continue
        counts.append(rec(ary, target - i, dic)+1)
    dic[target] = min(counts)
    return dic[target]
        

if '__main__' == __name__:
    resolve()

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

xlist=[1]
for d in range(1,10**9):
  if 6**d>100000:
    break
  xlist.append(6**d)
for d in range(1,10**9):
  if 9**d>100000:
    break
  xlist.append(9**d)
xlist.sort()


dp=[0]*(N+1)
for i in range(1,N+1):
  min_dp=10**9
  for x in xlist:
    if i-x<0:
      break
    min_dp=min(min_dp,dp[i-x])
  dp[i]=min_dp+1
  

print(dp[-1])

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

xlist=[1]
for d in range(1,10**9):
  if 6**d>100000:
    break
  xlist.append(6**d)
for d in range(1,10**9):
  if 9**d>100000:
    break
  xlist.append(9**d)
xlist.sort()


dp=[0,1]+[0]*(N-1)
for i in range(2,N+1):
  min_dp=10**9
  for x in xlist:
    if i-x>=0:
      min_dp=min(min_dp,dp[i-x])
  dp[i]=min_dp+1
  

print(dp[-1])

Solution (Python):
n = int(input())
L = [1]
for i in range(1, 6):
    L.append(pow(9, i))
for i in range(1, 7):
    L.append(pow(6, i))
L = sorted(L)
dp = [float("inf") for _ in range(n + 1)]
dp[0] = 0
for i in range(1, n + 1):
    for l in L:
        if i - l >= 0:
            dp[i] = min(dp[i], dp[i - l] + 1)
print(dp[n])

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

dp = [[0] * (n+1) for i in range(len(lis))]
for i in range(n+1):
    dp[0][i] = i

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

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

dp = [[0] * (n+1) for i in range(len(lis))]
for i in range(n+1):
    dp[0][i] = i

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

Solution (Python):
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math
from fractions import gcd

NN = 202020
MOD = 10**9+7
INF = float("inf")

n = int(input())
min_time = n

for i in range(n+1):
    v6, v9 = i, n-i
    count = 0
    while v6 > 0:
        count += v6 % 6
        v6 //= 6
    while v9 > 0:
        count += v9 % 9
        v9 //= 9
    min_time = min(min_time, count)

print(min_time)

Solution (Python):


n = int(input())

dp = [9999] * (200000 + 10)
offset = 100000
dp[0 + offset] = 0

coin = []
coin.append(1)
temp = 6
while temp <= 100000:
    coin.append(temp)
    temp *= 6
temp = 9
while temp <= 100000:
    coin.append(temp)
    temp *= 9



for i in range(1, len(dp) - offset):
    temp_min = 9999
    for c in coin:
        temp_min = min(temp_min, dp[i + offset - c])
    dp[i + offset] = temp_min + 1

print(dp[n + offset])

Solution (Python):
n = int(input())
F = [0]
for i in range(1, n+1):
    A = [F[i-1]+1]
    j = 1
    while i-6**j >= 0:
        A.append(F[i-6**j]+1)
        j += 1
    j = 1
    while i-9**j >= 0:
        A.append(F[i-9**j]+1)
        j += 1
    F.append(min(A))
print(F[n])

Solution (Python):
n=int(input())
def search(k,m):
    count=0
    while 0<k:
        count+=k%m
        k=k//m
    return count
ans=10**6
for i in range(n+1):
    
    ans=min(ans,search(i,9)+search(n-i,6))
    
    
print(ans)

Solution (Python):

import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue
from decimal import *


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

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

    @staticmethod
    def round_up(a, b):
        return -(-a // b)

    @staticmethod
    def is_prime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


def pop_count(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


MOD = int(1e09) + 7
INF = int(1e15)


def solve():
    N = Scanner.int()
    dp = [0 for _ in range(N + 1)]
    for i in range(1, N + 1):
        dp[i] = dp[i - 1] + 1
        n = 6
        while i - n >= 0:
            dp[i] = min(dp[i], dp[i - n] + 1)
            n *= 6
        n = 9
        while i - n >= 0:
            dp[i] = min(dp[i], dp[i - n] + 1)
            n *= 9
    print(dp[N])


def main():
    
    solve()


if __name__ == "__main__":
    main()

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

moneylist = [1]

money = 6

while money < 100000:
    moneylist.append(money)
    money = money*6

money = 9    

while money < 100000:
    moneylist.append(money)
    money = money*9
moneylist.sort()

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

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

Solution (Python):
def main():
    n = int(input())
    dp = [None]*(n+1)
    dp[0] = 0
    dp[1] = 1
    nl = list(sorted([6**i for i in range(10) if (6**i)<=n]+[9**i for i in range(1, 10) if (9**i)<=n]))
    for i in range(2, n+1):
        d = 10**15
        for j in nl:
            if j > i:
                break
            d = min(d, 1+dp[i-j])
        dp[i] = d
    print(dp[n])

if __name__ == "__main__":
    main()

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

def MIN(a, b):
    if a > b:
        return b
    else:
        return a

def main():
    N = int(input())
    yen6 = [6 ** i for i in range(1, 7) if 6 ** i <= N]
    yen9 = [9 ** i for i in range(1, 6) if 9 ** i <= N]

    if N < 6:
        print(N)
        exit()

    dp = [N] * (N + 1)
    for i in range(6):
        dp[i] = i
    for i in range(N + 1):
        for j in yen6:
            if i + j > N:
                break
            dp[i+j] = MIN(dp[i+j], dp[i] + 1)
        for j in yen9:
            if i + j > N:
                break
            dp[i+j] = MIN(dp[i+j], dp[i] + 1)
    print(dp[N])

if __name__ == '__main__':
    main()

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

def MIN(a, b):
    if a > b:
        return b
    else:
        return a

def main():
    N = int(input())
    yen6 = [6 ** i for i in range(1, 7) if 6 ** i <= N]
    yen9 = [9 ** i for i in range(1, 6) if 9 ** i <= N]

    if N < 6:
        print(N)
        exit()

    dp = [N] * (N + 1)
    for i in range(6):
        dp[i] = i
    for i in range(1, N + 1):
        for j in yen6:
            if i - j < 0:
                break
            dp[i] = MIN(dp[i], dp[i - j] + 1)
        for j in yen9:
            if i - j < 0:
                break
            dp[i] = MIN(dp[i], dp[i - j] + 1)
    print(dp[N])

if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 9)
from functools import lru_cache
def input(): return sys.stdin.readline().rstrip()

def main():
    N = int(input())
    yen = [6 ** i for i in range(1, 7)]
    yen += [9 ** i for i in range(1, 6)]
    yen = [i for i in yen if i <= N]
    yen.sort(reverse=True)

    def MIN(a, b):
        if a > b:
            return b
        else:
            return a

    @lru_cache(maxsize=None)
    def dfs(x, n, m):
        n += 1
        for y in yen:
            if n >= m:
                return n
            if y > x:
                continue
            if x - y < 6:
                return n + x - y
            m = MIN(dfs(x - y, n, m), m)
        return m

    print(dfs(N, 0, N))

if __name__ == '__main__':
    main()

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

for i in range(1,100010):
  dp[i]=float('inf')
  
for i in range(1,100010):
  power6=1
  while power6<=i:
    dp[i]=min(dp[i-power6]+1,dp[i])
    power6*=6
  power9=1
  while power9<=i:
    dp[i]=min(dp[i-power9]+1,dp[i])
    power9*=9

print(dp[n])

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

cands = [1]
for i in range(1, 7):
  if 6**i <= N:
    cands.append(6**i)
  if 9**i <= N:
    cands.append(9**i)

dp = [10**6] * (N+1)
dp[0] = 0
for i in range(1, N+1):
  for c in cands:
    if c <= i:
      dp[i] = min(dp[i], dp[i-c]+1)

print(dp[-1])

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

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

    a = 1
    while True:
        a *= 6
        if a > i:
            break
        q.append(1+dp[i-a])

    b = 1
    while True:
        b *= 9
        if b > i:
            break
        q.append(1+dp[i-b])

    dp.append(min(q))

print(dp[n])

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

for i in range(n+1):
    j = n-i

    a = j
    p = 0
    while a>0:
        p += a%6
        a = a//6

    b = i
    q = 0
    while b>0:
        q += b%9
        b = b//9

    ans = min(ans, p+q)

print(ans)