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
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
    
    
def main():
    N = I()
    L = [1]
    temp = 1
    while temp <= N:
        temp *= 6
        L.append(temp)
    temp = 1
    while temp <= N:
        temp *= 9
        L.append(temp)
    L.sort()
    D = [i for i in range(N+1)]
    for i in L[1:]:
        for j in range(i, N+1):
            D[j] = min(D[j], D[j-i]+1)
    print(D[N])

if __name__ == "__main__":
    main()

Solution (Python):
import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
    
    
def main():
    N = I()
    L = [1]
    temp = 1
    while temp <= N:
        temp *= 6
        L.append(temp)
    temp = 1
    while temp <= N:
        temp *= 9
        L.append(temp)
    L.sort()
    D = [i for i in range(N+1)]
    for i in L[1:]:
        for j in range(i, N+1):
            D[j] = min(D[j], D[j-i]+1)
    print(D[N])

if __name__ == "__main__":
    main()

Solution (Python):
def solve():
    n = int(input())
    dp = [True] + [False]*(n+1)
    way = [1] + [6**i for i in range(1,9) if 6**i <= n] + [9**i for i in range(1,7) if 9**i <= n]
    loop_counter = 0
    while True:
        loop_counter += 1
        newdp = [False] * (n+1)
        for w in way:
            for i in range(w, n+1):
                if newdp[i]: continue
                if dp[i-w]: newdp[i] = True
                if newdp[n]: 
                    return loop_counter
        dp = [x for x in newdp]

print(solve())

Solution (Python):
n = int(input())
index6, index9, num6, num9 = 0, 0, 0, 0
INF = float('inf')    
a = [INF for _ in range(n+1)]
a[n] = 0

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

Solution (Python):
n = int(input())
index6, index9, num6, num9 = 0, 0, 0, 0
INF = float('inf')    
a = [INF for _ in range(n+1)]
a[n] = 0

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

Solution (Python):
n=int(input())
dp=[0]*(n+1)
for i in range(n+1):
  t=i
  count=0
  while t>0:
    count+=t%6
    t//=6
  t=n-i
  while t>0:
    count+=t%9
    t//=9
  dp[i]=count
print(min(dp))

Solution (Python):
n=int(input())
dp=[0]*(n+1)
for i in range(n+1):
  t=i
  count=0
  while t>0:
    count+=t%6
    t//=6
  t=n-i
  while t>0:
    count+=t%9
    t//=9
  dp[i]=count
print(min(dp))

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

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

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



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


print(dp[-1])

Solution (Python):
import sys



def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    n = input_int()
    dp = [0] * (n + 1)  

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


if __name__ == "__main__":
    main()

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

Solution (Python):
import numpy as np

n = int(input())

dp = np.full((n + 1), n + 1, dtype = int)
dp[0] = 0

loop = 0
while dp[n] > n:
    tmp1 = np.full(n + 1, n + 1, dtype = int)
    tmp6 = np.full(n + 1, n + 1, dtype = int)
    tmp9 = np.full(n + 1, n + 1, dtype = int)    
    tmp1[1:] = dp[: -1] + 1
    j = 1
    while 6 ** j <= n:
        tmp6_pre = tmp6
        tmp6[6 ** j:] = dp[:-6 ** j] + 1
        tmp6 = np.minimum(tmp6_pre, tmp6)
        j += 1
    k = 1
    while 9 ** k <= n:
        tmp9_pre = tmp9
        tmp9[9 ** k:] = dp[: -9 ** k] + 1
        tmp9 = np.minimum(tmp9_pre, tmp9)
        k += 1
    tmp1 = np.minimum(tmp1, tmp6)
    tmp1 = np.minimum(tmp1, tmp9)
    dp = np.minimum(dp, tmp1)
    loop += 1
print(dp[n])

Solution (Python):
def main():
    N = int(input())
    INF = float('inf')
    dp = [INF] * (N+1)
    dp[0] = 0
    for n in range(1, N+1):
        dp[n] = 1 + dp[n-1]
        for k in range(1, 8):
            p = 6**k
            if n-p >= 0:
                dp[n] = min(dp[n], dp[n-p] + 1)
            p = 9**k
            if n-p >= 0:
                dp[n] = min(dp[n], dp[n-p] + 1)
    
    ans = dp[N]
    print(ans)


if __name__ == "__main__":
    main()

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

A = [1]

for i in range (1, 7):
	A.append(6**i)

for i in range (1, 6):
	A.append(9**i)
    
A = sorted(A)
import math
DP = [math.inf]*1000001
DP[0] = 0

for i in range (0, 1000001):
	for j in range (0, 12):
		if i+A[j] < 1000001:
			if  DP[i]+1 < DP[i+A[j]]:
				DP[i+A[j]] = DP[i]+1
print(DP[N])

Solution (Python):
from collections import deque

N = int(input())
units = set()
i = 0
while 6 ** i <= N:
    units.add(6 ** i)
    i += 1
i = 0
while 9 ** i <= N:
    units.add(9 ** i)
    i += 1
units = sorted(units)

mins = list(range(N + 1))
for i in range(1, len(units)):
    unit = units[i]
    for j in range(N):
        if j + unit < len(mins) and mins[j] + 1 < mins[j + unit]:
            mins[j + unit] = mins[j] + 1
print(mins[N])

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

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

Solution (Python):
def main():
    N = int(input())
    dp = [N] * (N+1)
    dp[0] = 0

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



if __name__ == "__main__":
    main()

Solution (Python):
n = int(input())
dp = [0] * (10**6+5)
for i in range(1, n+1):
  dp[i] = float("inf")
  power = 1
  while True:
    if i - power < 0:
      break
    dp[i] = min(dp[i], dp[i-power] + 1)
    power *= 6
  power = 1
  while True:
    if i - power < 0:
      break
    dp[i] = min(dp[i], dp[i-power] + 1)
    power *= 9
print(dp[n])

Solution (Python):
N=int(input())
INF=10**10
dp=[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)
    j=1
    while i+6**j<=N:
        dp[i+6**j]=min(dp[i+6**j],dp[i]+1)
        j+=1
    j=1
    while i+9**j<=N:
        dp[i+9**j]=min(dp[i+9**j],dp[i]+1)
        j+=1
print(dp[N])

Solution (Python):






N = int(input())





ans = N
for i in range(N+1):
    x = 0
    y = i
    while y:
        x += y%6
        y //= 6
    y = N-i
    while y:
        x += y%9
        y //= 9
    ans = min(x, ans)
print(ans)

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

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

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

print(dp[n])

Solution (Python):

import sys
sys.setrecursionlimit(100000)  

def func(n):
    if n==0:
        return 0 
    if memo[n] != -1:
        return memo[n] 

    res = n

    for i in range(1,n+1):
        pow6 = 6 ** i
        if pow6 > n:
            break
        res = min(res, func(n-pow6)+1)

    for i in range(1,n+1):
        pow9 = 9 ** i
        if pow9 > n:
            break
        res = min(res, func(n-pow9)+1)

    memo[n] = res
    return res


N = int(input())

max_n = 110000
memo = [-1] * max_n
ans = func(N)
print(ans)

Solution (Python):


def count(val1, val2):
    digit = 1
    while digit*val2 <= val1:
        digit *= val2

    res = 0
    while digit!=1:
        cnt = int(val1 // digit)
        val1 -= digit*cnt
        res += cnt
        digit /= val2

    return res,val1


N = int(input())
ans = N

for i in range(0,N+1):
    n = i
    m = N - i
    res = 0

    cnt, nn = count(n, 9)
    n = nn
    res += cnt

    cnt, mm = count(m, 6)
    m = mm
    res += cnt

    res += n + m
    ans = min(ans, int(res))

print(ans)

Solution (Python):


def count(val1, val2):
    digit = 1
    while val1 >= (val2 ** digit):
        digit += 1

    res = 0
    while digit!=0:
        cnt = int(val1 // val2 ** digit)
        val1 -= (val2 ** digit)*cnt
        res += cnt
        digit -= 1

    return res,val1


N = int(input())
ans = N

for i in range(0,N+1):
    n = i
    m = N - i
    res = 0

    cnt, nn = count(n, 9)
    n = nn
    res += cnt

    cnt, mm = count(m, 6)
    m = mm
    res += cnt

    res += n + m
    ans = min(ans, res)

print(ans)

Solution (Python):


N = int(input())

ans = N
for i in range(N+1):
    n = i
    m = N - i
    res = 0

    nine = 1
    while nine*9 <= n:
        nine *= 9
    while nine != 1:
        res += n // nine
        n %= nine
        nine /= 9
    res += n

    six = 1
    while six*6 <= m:
        six *= 6
    while six != 1:
        res += m // six
        m %= six
        six /= 6
    res += m

    ans = min(ans, int(res))

print(ans)

Solution (Python):
from functools import *
@lru_cache(maxsize=None) 
def f(x):
  if x==0:return 0
  s=10000000000000000
  for u in [1]+[6**i for i in range(1,11)]+[9**i for i in range(1,11)]:
    if x-u>=0:
      s=min(s,f(x-u)+1)
  return s
for i in range(1,100001):f(i)
print(f(int(input())))

Solution (Python):


def count(val1, val2):
    num = 1
    while True:
        if val1 < (val2 ** num):
            break
        num += 1

    cnt = 0
    digit = num
    while True:
        if val1 >= val2 ** digit:
            val1 -= val2 ** digit
            cnt += 1
        else:
            digit -= 1
        
        if digit== 0:
            break

    return cnt,val1


N = int(input())
ans = N

for i in range(0,N+1):
    n = i
    m = N - i
    res = 0

    cnt, nn = count(n, 9)
    n = nn
    res += cnt

    cnt, mm = count(m, 6)
    m = mm
    res += cnt

    res += n + m
    ans = min(ans, res)

print(ans)

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


dp = [0] * (N + 1)

MAX = 10 ** 8

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

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

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

    dp[i] = min(dp1, dp6, dp9)

print(dp[N])

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

dp = [10**5]*(N+1)
dp[0] = 0
dp[1] = 1
s = 6
n = 9
for i in range(2,N+1):
    if 6*s <= i:
        s *= 6
    if 9*n <= i:
        n *= 9
    if i < 6:
        dp[i] = dp[i-1]+1
    elif i < 9:
        dp[i] = min(dp[i-1], dp[i-s])+1
    else:
        dp[i] = min(dp[i-1], dp[i-s], dp[i-n])+1
print(dp[N])

Solution (Python):

_INPUT = """\
127
"""
"""
K = int(input())
H, W, K = map(int, input().split())
a = list(map(int, input().split()))
xy = [list(map(int, input().split())) for i in range(N)]
p = tuple(map(int,input().split()))
"""
def main():
    N = int(input())

    dp = [float('inf')] * (N+1)
    dp[0] = 0
    a,b,c = 1,6,9

    for i in range(N+1):
        if i >= b*6:
            b *= 6
        if i >= c*9:
            c *= 9
        if i < b:
            dp[i] = i
        elif i < c:
             dp[i] = min(dp[i-1]+1, dp[i-b]+1)
        else:
            dp[i] = min(dp[i-1]+1,dp[i-b]+1,dp[i-c]+1)
    
    print(dp[N])
            
            
if __name__ == '__main__':
    import io
    import sys
    import math
    import itertools
    from collections import deque

    
    main()

Solution (Python):
N=int(input())
cnt=[0 for _ in range(N+1)]
for i in range(1,N+1):
    cnt[i]=cnt[i-1]+1
    a=6
    while i-a>=0:
        cnt[i]=min(cnt[i],cnt[i-a]+1)
        a*=6
    a=9
    while i-a>=0:
        cnt[i]=min(cnt[i],cnt[i-a]+1)
        a*=9
print(cnt[N])

Solution (Python):
def getval():
    n = int(input())
    return n

def main(n):
    dp = [0]
    arr = [1]
    a1 = 6
    a2 = 9
    for i in range(1,100):
        if a1**i<=n:
            arr.append(a1**i)
        else:
            break
    for i in range(1,100):
        if a2**i<=n:
            arr.append(a2**i)
        else:
            break
    arr.sort()
    
    for i in range(1,n+1):
        temp = i 
        for j in arr:
            if j>i:
                break
            temp = min(temp,dp[i-j]+1)
        dp.append(temp)

    print(dp[n])

if __name__=="__main__":
    n = getval()
    main(n)

Solution (Python):
N = int(input())
l = [0] * (10**5+1)
nums = [0]
for i in range(N):
  tmp = []
  flag = False
  for k in nums:
    if l[k+1] == 0:
      l[k+1] = l[k]+1
      tmp.append(k+1)
    for j in range(1, N):
      if k+6**j <= N:
        if l[k+6**j] == 0:
          l[k+6**j] = l[k]+1
          tmp.append(k+6**j)
      else:
        break
    for j in range(1, N):
      if k+9**j <= N:
        if l[k+9**j] == 0:
          l[k+9**j] = l[k]+1
          tmp.append(k+9**j)
      else:
        break
    if l[N] > 0:
      flag = True
      break
  if flag:
    break
  else:
    nums = tmp
print(l[N])

Solution (Python):
def main():
    n = int(input())
    INF = 10 ** 12
    dp = [INF] * (n + 1)
    dp[0] = 0

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

    print(dp[-1])


if __name__ == "__main__":
    main()

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())
x=[10000]*(n+2)
x[0]=0
a=[6**i for i in range(1,7)]
b=[9**i for i in range(1,6)]
c=[1]
c=a+b+c
c.sort()
for i in range(1,n+2):
    for j in c:
        if i-j>=0:
            x[i]=min(x[i],x[i-j]+1)
        else:
            break
print(x[n])

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

ans = N
for i in range(N+1):
    x = 0
    y = i
    while y:
        x += y%6
        y //= 6
    y = N-i
    while y:
        x += y%9
        y //= 9
    ans = min(x, ans)

print(ans)

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

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

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

print(dp[N])

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

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

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

print(dp[N])

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

lst = [1, 6, 9, 6**2, 9**2, 6**3, 9**3, 6**4, 9**4, 6**5, 6**6, 9**5]
dp = [N+1] * (N+1)
dp[0] = 0
for i in range(1, N+1):
    for j in lst:
        if j <= i:
            
            dp[i] = min(dp[i], dp[i-j]+1)
print(dp[-1])

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

lst = [1, 6, 9, 6**2, 9**2, 6**3, 9**3, 6**4, 9**4, 6**5, 6**6, 9**5]
dp = [N+1] * (N+1)
dp[0] = 0
for i in range(1, N+1):
    for j in lst:
        if j <= i:
            
            dp[i] = min(dp[i], dp[i-j]+1)
print(dp[-1])

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

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

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

ans = INF
for i in range(len(dp) - 1, -1, -1):
  money = dp[i] + N - i
  if ans > money:
    ans = money
        
print(ans)

Solution (Python):
N = int(input())
ans = [0] * 100001
for i in range(6):
    ans[i] = i
s = 6
n = 9
for i in range(6,N+1):
    p = i%3
    if p != 0:
        ans[i] =  ans[i-p] + p
    else:
        if i == s*6:
            s *= 6
        if i == n*9:
            n *= 9
        ans[i] = min(ans[i-s]+1,ans[i-n]+1)
print(ans[N])

Solution (Python):
import sys
from sys import exit
from collections import deque
from copy import deepcopy
from bisect import bisect_left, bisect_right, insort_left, insort_right
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import gcd, sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod=MOD):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
    def list(self):
        l = []
        for k in self:
            l.extend([k]*self[k])
        return l
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]
def pf(x,mode='counter'):
    C = counter()
    p = 2
    while x>1:
        k = 0
        while x%p==0:
            x //= p
            k += 1
        if k>0:
            C.add(p,k)
        p = p+2-(p==2) if p*p<x else x
    if mode=='counter':
        return C
    S = set([1])
    for k in C:
        T = deepcopy(S)
        for x in T:
            for i in range(1,C[k]+1):
                S.add(x*(k**i))
    if mode=='set':
        return S
    if mode=='list':
        return sorted(list(S))



N=intput()
c=[-1]*(N+1)
c[0]=0
for i in range(1,N+1):
    ans=c[i-1]+1
    tmp=6
    while i-tmp>=0:
        ans=min(ans,c[i-tmp]+1)
        tmp*=6
    tmp=9
    while i-tmp>=0:
        ans=min(ans,c[i-tmp]+1)
        tmp*=9
    c[i]=ans
print(c[N])

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

dp = [n]*100010
dp[0] = 0
pow69 = [6**i for i in range(1,7)] + [9**i for i in range(1,6)]

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

print(dp[n])

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

INF = float("inf")

dp = [INF]*100010
dp[0] = 0

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

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

print(dp[n])

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

INF = float("inf")

dp = [INF]*100010
dp[0] = 0

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

for i in range(1,n+1):
    for p6 in pow6:
        dp[i] = min(dp[i],dp[i-p6]+1)
    for p9 in pow9:
        dp[i] = min(dp[i],dp[i-p9]+1)
print(dp[n])

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

dp=[0]*N
for i in range(10):
  if 6**i-1 < N:
    dp[6**i-1] = 1
for i in range(10):
  if 9**i-1 < N:
    dp[9**i-1] = 1


for k in range(1,N):
  if dp[k] != 1:
    dp_list = []
    for j in range(10):
      if k >= 6**j:
        dp_list.append(dp[k-6**j])
      if k >= 9**j:
        dp_list.append(dp[k-9**j])
  
    dp[k] = 1+min(dp_list)

print(dp[N-1]%1000000007)

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

dp=[float('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
  
  power=1
  while(power<=i):
    dp[i]=min(dp[i],dp[i-power]+1)
    power*=9

print(dp[n])

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

dp=[float('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
  
  power=1
  while(power<=i):
    dp[i]=min(dp[i],dp[i-power]+1)
    power*=9

print(dp[n])

Solution (Python):
N=int(input())
A=[1,6,36,6**3,6**4,6**5,6**6,9,81,9**3,9**4,9**5]
B=[0]+[N]*N
i=0
while i<=N:
    for a in A:
        if a+i<=N:
            B[a+i]=min(B[a+i],B[i]+1)
    i+=1
print(B[N])

Solution (Python):
from bisect import bisect_right
N = int(input())
L = {1}
m = 6
n = 9
while m <= N:
    L.add(m)
    m *= 6
while n <= N:
    L.add(n)
    n *= 9
L = list(L)
L.sort()


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

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


print(dp[N])

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

dp = [N] * (N+1)

dp[0] = 0

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

print(dp[N])

Solution (Python):

def main():
    import numpy as np

    N = int(input())

    can = [1]
    limit = 100
    for i in range(1, limit):
        six = 6 ** i
        if six <= N:
            can.append(six)
        nine = 9 ** i
        if nine <= N:
            can.append(nine)
        if six > N and nine > N:
            break

    INF = 10 ** 9
    dp = np.full(N + 1, INF, dtype=np.int32)
    dp[0] = 0
    for c in can:
        for _ in range(9):
            dp[c:] = np.minimum(dp[c:], dp[:-c] + 1)
    print(dp[-1])


if __name__ == '__main__':
    main()

Solution (Python):

def main():
    N = int(input())
    
    can_six = []
    can_nine = []
    limit = 100
    for i in range(1, limit):
        six = 6 ** i
        if six <= N:
            can_six.append(six)
        nine = 9 ** i
        if nine <= N:
            can_nine.append(nine)
        if six > N and nine > N:
            break
    can = sorted([1] + can_six + can_nine)

    INF = 10 ** 9
    dp = [INF] * (N + 1)
    dp[0] = 0
    for n in range(N + 1):
        for draw in can:
            if n - draw < 0:
                break
            dp[n] = min(dp[n], dp[n - draw] + 1)
    print(dp[-1])


if __name__ == '__main__':
    main()

Solution (Python):

import sys

sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read


sys.setrecursionlimit(10**7)

from itertools import product, accumulate, combinations, product







INF = 1 << 50
EPS = 1e-8
mod = 10 ** 9 + 7

def run():
    N = int(input())
    nines = [9 ** i for i in range(1, 10) if 9 ** i <= N]
    sixes = [6 ** i for i in range(1, 10) if 6 ** i <= N][::-1]
    L = len(nines)
    
    min_ans = INF
    for K in product(range(9), repeat = L):
        
        ans = 0
        s = 0
        for k, x in zip(K, nines):
            if k:
                ans += k
                s += x * k
        

        if s > N:continue
        resid = N - s
        
        for six in sixes:
            
            tmp = resid // six
            if tmp:
                ans += tmp
                resid -= six * tmp
        
        
        
        ans += resid
        min_ans = min(min_ans,ans)

    print(min_ans)

if __name__ == "__main__":
    run()

Solution (Python):
import sys



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


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

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

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

    for i in range(N):
        c = number[i]
        for g in G:
            if i+g <=N:
                number[i+g] =min(c+1,number[i+g])
    print(number[N])



if __name__ == "__main__":
    main()

Solution (Python):
import sys



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


def main():
    ans = int(input())
    N=100000
    i = 1
    r = 6
    k = 9
    G = [1]
    while r <= N:
        G.append(k)
        G.append(r)
        k *= 9
        r *= 6

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

    for i in range(N):
        c = number[i]
        for g in G:
            if i+g <=N:
                number[i+g] =min(c+1,number[i+g])
    print(number[ans])



if __name__ == "__main__":
    main()

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()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
import random
import string
from copy import deepcopy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

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





N = getN()

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

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



def dijkstra(n, start):
    dist = [float('inf')] * n
    pos = [(0, start)]
    heapify(pos)
    dist[start] = 0

    while len(pos):
        cost, u = heappop(pos)

        if dist[u] < cost:
            continue
        
        for i in range(len(coin)):
            if u + coin[i] >= n:
                continue
            if dist[u] + 1 < dist[u + coin[i]]:
                dist[u + coin[i]] = dist[u] + 1
                heappush(pos, (dist[u] + 1, u + coin[i]))

    return dist

print(dijkstra(N + 1, 0)[N])

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

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

Solution (Python):
N=int(input())
dp=[0]*(100000+1)
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-a]+1,dp[i-b]+1)
  else:
    dp[i]=min([dp[i-a]+1,dp[i-b]+1,dp[i-c]+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%6
    t//=6
  j=N-i
  while j>0:
    cnt+=j%9
    j//=9
  ans=min(ans,cnt)
print(ans)

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