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



Sample input:
127


Sample output:
4

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)

def main():
    n = int(input().strip())
    dp = [[0] * (n+1) for _ in range(15)]
    coins = [0] + [6**i for i in range(8)] + [9 ** i for i in range(1, 7)]
    for i in range(1, n+1):
        dp[0][i] = 10**10
    for i in range(1, 15):
        for j in range(n+1):
            if j - coins[i] < 0:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = min(dp[i-1][j], dp[i][j-coins[i]] + 1)
    print(dp[14][n])
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())

inf = 1000000000
DP = [inf for _ in range(1000000)]
DP[0] = 0

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def main():
    N = int(input())
    ans = N
    for i in range(N+1):# 6^pで何円引き出すか
        count = 0
        tmp = i
        while tmp > 0:
            count += tmp % 6
            tmp //= 6
        tmp = N - i
        while tmp > 0:
            count += tmp % 9
            tmp //= 9
        ans = min(ans, count)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
mn = 10**6
for m9 in range(n+1):
    cnt = 0
    m6 = n-m9
    while m9>0:
        i = 0
        while m9>=9**i:
            if 9**(i+1)<=m9:
                i+=1
            else:
                r = m9//(9**i)
                m9 -= r*(9**i)
                cnt += r
                i = 0
    while m6>0:
        i = 0
        while m6>=6**i:
            if 6**(i+1)<=m6:
                i+=1
            else:
                r = m6//6**i
                m6 -= r*6**i
                cnt += r
                i = 0
    if cnt < mn:
        mn = cnt

print(mn)

Submission status: Accepted

Solution code:
N = int(input())
dp = list(range(N+1))

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

Submission status: Accepted

Solution code:
N = int(input())
dp=list(range(N+1))

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

print(dp[N])

Submission status: Accepted

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

print(ans)

Submission status: Accepted

Solution code:
n = int(input())

dp = [0] * (n + 1)

for i in range(1, n + 1):
    dp[i] = dp[i - 1] + 1
    power = 6
    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])

Submission status: Accepted

Solution code:
max_n = 100000

N = int(input())

dp = [N for _ in range(N+1)]
dp[0] = 0
for n in range(1, N+1):
    for pow6 in range(n+1):
        if 6 ** pow6 <= n:
            dp[n] = min(dp[n], dp[n - 6 ** pow6] + 1)
        else:
            break

    for pow9 in range(n+1):
        if 9 ** pow9 <= n:
            dp[n] = min(dp[n], dp[n - 9 ** pow9] + 1)
        else:
            break
print(dp[N])

Submission status: Accepted

Solution code:
n=int(input())
ans=[0]*(n+1)
for i in range(1,n+1):
    ans[i] = ans[i-1]+1
    m6 = 6
    m9 = 9
    while i>=m6:
        ans[i] = min(ans[i],ans[i-m6]+1)
        m6 *= 6
    while i>=m9:
        ans[i] = min(ans[i],ans[i-m9]+1)
        m9 *= 9
print(ans[-1])

Submission status: Accepted

Solution code:

max_n = 110000

N = int(input())

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

    for pow9 in range(n+1):
        if 9 ** pow9 <= n:
            dp[n] = min(dp[n], dp[n - 9 ** pow9] + 1)
        else:
            break

# print(dp)
print(dp[N])

Submission status: Accepted

Solution code:
N = int(input())

def f(n):
    L = [1]
    c = 1
    while 6**c <= n:
        L.append(6**c)
        c += 1
    c = 1
    while 9**c <= n:
        L.append(9**c)
        c += 1
    return L

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

for i in range(N):
    L = f(i+1)
    temp = dp[i+1-L[0]]
    for j in range(len(L)):
        if temp > dp[i+1-L[j]]:
            temp = dp[i+1-L[j]]
    dp[i+1] = temp+1
    
print(dp[N])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**5)

N = int(input())

def rec(N, m) :
    if N < 6 :
        return N + m
    
    
    a, b = float('inf'), float('inf')
    six = 6
    while six * 6 <= N :
        six *= 6
    if N >= six :
        a = rec(N - six, m + 1)
    
    nine = 9
    while nine * 9 <= N :
        nine *= 9
    if N >= nine :
        b = rec(N - nine, m + 1)
    
    return min(a, b)
        
print(rec(N, 0))

Submission status: Accepted

Solution code:
N = int(input())
A = [1]
for k in range(1,7):
    A.append(6**k)
for k in range(1,6):
    A.append(9**k)
dp = [[0 for _ in range(len(A))] for _ in range(N+1)]
for i in range(N+1):
    dp[i][0] = i
for j in range(len(A)):
    dp[1][j] = 1
for i in range(2,N+1):
    for j in range(1,len(A)):
        if i>=A[j]:
            dp[i][j] = min(dp[i][j-1],dp[i-A[j]][j]+1)
        else:
            dp[i][j] = dp[i][j-1]
print(dp[N][len(A)-1])

Submission status: Accepted

Solution code:
n=int(input());print(min(sum(i//9**j%9+(n-i)//6**j%6for j in range(7))for i in range(n+1)))

Submission status: Accepted

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

# N以下の6と9のべき乗リストを作ってDP適用
c = [1]
t = 6
while t <= N:
    c.append(t)
    t *= 6
t = 9
while t <= N:
    c.append(t)
    t *= 9
    
def chmin(a, b):                            #最小値に置き換える関数の定義
    if a > b:
        return b
    else:
        return a

for i in range(1, N+1):                     #dp[i]=i円とするようにする（dp[0]=0、dp[N+1]=N円）
    for t in c:                             #ｃのリストの中だけ繰り返す       
        dp[i] = chmin(dp[i], dp[i-t]+1)     #ｃのリストにあれば+1
            
print(dp[N])

Submission status: Accepted

Solution code:
s=input()
a=int(s)
list=[]
list.append(1)
list.append(6)
list.append(9)
list.append(36)
list.append(81)
list.append(216)
list.append(729)
list.append(1296)
list.append(6561)
list.append(7776)
list.append(59049)
list.append(46656)
pp=[]
def money(x,y):
  for i in range(12):
    b=x//list[i]
    if b==0:
      continue
    if i%2==1:
      if 0<b<6:
        if x%list[i]==0:
          pp.append(y+b)
        else:
          if y>20:
            break
          money(x-list[i],y+1)
    elif i%2==0:
      if i!=0:
        if 0<b<9:
          if x%list[i]==0:
            pp.append(y+b)
          else:
            if y>20:
              break
            money(x-list[i],y+1)
      else:
        if 0<b<6:
          pp.append(y+b)
money(a,0)
print(min(pp))

Submission status: Accepted

Solution code:

import sys
input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
# A = [ int(input()) for _ in range(N) ]
##############################

N = int(input())

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

#print(dp)


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

        pow6 *= 6

    pow9 = 9
    while pow9 <= N:
        if i >= pow9:
            dp[i] = min(dp[i], dp[i-pow9]+1)

        pow9 *= 9

print(dp[N])

Submission status: Accepted

Solution code:
N = int(input())
INF = 10**6
dp = [INF] * (max(9, N)+1)
dp[0] = 0
for i in range(N):
  n = m = 0
  while i+9**n <= N:
    dp[i+9**n] = min(dp[i+9**n], dp[i] + 1)
    n += 1
  while i+6**m <= N:
    dp[i+6**m] = min(dp[i+6**m], dp[i] + 1)
    m += 1
print(dp[N])

Submission status: Accepted

Solution code:
n = int(input())

counter_min = n

for i in range(n+1):
  counter = 0
  n_six = i
  n_nine = n-i

  # 6
  j = 1
  while True:
    if  n_six >= 6**j:
      j += 1
    else:
      div_n = 6**(j-1)
      break
  
  while n_six > 0:
    counter += n_six // div_n
    n_six %= div_n
    div_n //= 6 
    
  # 9
  j = 1
  while True:
    if  n_nine >= 9**j:
      j += 1
    else:
      div_n = 9**(j-1)
      break
        
  while n_nine > 0:
    counter += n_nine // div_n
    n_nine %= div_n
    div_n //= 9
  
  counter_min = min(counter, counter_min)

print(counter_min)

Submission status: Accepted

Solution code:
N = int(input())
yen6, yen9 = [1], [1]
[x for x in yen6 if yen6[-1] <= N and (yen6.append(yen6[-1]*6) or True)]
[x for x in yen9 if yen9[-1] <= N and (yen9.append(yen9[-1]*9) or True)]

yen = sorted(yen6[1:-1] + yen9[1:-1])
dp = [0]
for i in range(1, N+1):
    temp = 1 + dp[i-1]
    for y in yen:
        if i < y:
            break
        if temp > 1 + dp[i-y]:
            temp = 1 + dp[i-y]
    dp.append(temp)

print(dp[-1])

Submission status: Accepted

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


tup=((1,6,9,6**2,9**2,6**3,9**3,6**4,9**4,6**5,6**6,9**5))

for i in range(1,n+1):
    for j in tup:
        if i-j<0:
            break
        dp[i]=min(dp[i],dp[i-j]+1)
print(dp[-1])

Submission status: Accepted

Solution code:
# DP(貰うDP)
INF = float('inf')

N = int(input())

c = [1]
t = 6
while t <= N:
    c.append(t)
    t *= 6
t = 9
while t <= N:
    c.append(t)
    t *= 9

dp = [0] * (N + 1)
for i in range(1, N + 1):
    t = INF
    for j in c:
        if i - j >= 0 and t > dp[i - j] + 1:
            t = dp[i - j] + 1
    dp[i] = t
print(dp[N])

Submission status: Accepted

Solution code:
# DP(配るDP)
INF = float('inf')

N = int(input())

c = [1]
t = 6
while t <= N:
    c.append(t)
    t *= 6
t = 9
while t <= N:
    c.append(t)
    t *= 9

dp = [INF] * (N + 1)
dp[0] = 0
for i in range(N):
    for j in c:
        if i + j <= N and dp[i + j] > dp[i] + 1:
            dp[i + j] = dp[i] + 1
print(dp[N])

Submission status: Accepted

Solution code:
# DP(配るDP)
INF = float('inf')

N = int(input())

c = [1]
t = 6
while t <= N:
    c.append(t)
    t *= 6
t = 9
while t <= N:
    c.append(t)
    t *= 9

dp = [INF] * (N + 1)
dp[0] = 0
for i in range(N):
    t0 = dp[i] + 1
    for j in c:
        t1 = i + j
        if t1 <= N and dp[t1] > t0:
            dp[t1] = t0
print(dp[N])

Submission status: Accepted

Solution code:
# DP(配るDP)
INF = float('inf')

N = int(input())

c = [1]
t = 6
while t <= N:
    c.append(t)
    t *= 6
t = 9
while t <= N:
    c.append(t)
    t *= 9

dp = [INF] * (N + 1)
dp[0] = 0
for i in range(N):
    t0 = dp[i] + 1
    for j in c:
        t1 = i + j
        if t1 <= N and dp[t1] > t0:
            dp[t1] = t0
        if t1 == N:
            break
print(dp[N])

Submission status: Accepted

Solution code:
# DP(配るDP)
INF = float('inf')

N = int(input())

c = [1]
t = 6
while t <= N:
    c.append(t)
    t *= 6
t = 9
while t <= N:
    c.append(t)
    t *= 9

dp = [INF] * (N + 1)
dp[0] = 0
for i in range(N):
    t0 = dp[i]
    for j in c:
        t1 = i + j
        if t1 <= N and dp[t1] > t0 + 1:
            dp[t1] = t0 + 1
        if t1 == N:
            break
print(dp[N])

Submission status: Accepted

Solution code:
# DP(配るDP)
INF = float('inf')

N = int(input())

c = [1]
t = 6
while t <= N:
    c.append(t)
    t *= 6
t = 9
while t <= N:
    c.append(t)
    t *= 9

dp = [INF] * (N + 1)
dp[0] = 0
for i in range(N):
    for j in c:
        t = i + j
        if t <= N and dp[t] > dp[i] + 1:
            dp[t] = dp[i] + 1
        if t == N:
            break
print(dp[N])

Submission status: Accepted

Solution code:
# DP(配るDP)
INF = float('inf')

N = int(input())

c = [1]
t = 6
while t <= N:
    c.append(t)
    t *= 6
t = 9
while t <= N:
    c.append(t)
    t *= 9

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

Submission status: Accepted

Solution code:
n = int(input())

INF = 100010
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 = 6
    while i + j <= n:
        dp[i + j] = min(dp[i + j], dp[i] + 1)
        j *= 6
    
    j = 9
    while i + j <= n:
        dp[i + j] = min(dp[i + j], dp[i] + 1)
        j *= 9

print(dp[n])

Submission status: Accepted

Solution code:
pow_6 = [6**i for i in range(11)]
pow_9 = [9**i for i in range(11)]
N = int(input())
log = [0]*N
def ans(n):
  if n in pow_6 or n in pow_9:
    return 1
  else:
    num6 = 0
    while pow_6[num6]<n:
      num6 += 1
    num6 -= 1
    num9 = 0
    while pow_9[num9]<n:
      num9 += 1
    num9 -= 1
    if log[n-pow_6[num6]]!=0:
      x = log[n-pow_6[num6]]
    else:
      x = ans(n-pow_6[num6])
      log[n-pow_6[num6]] = x
    if log[n-pow_9[num9]]!=0:
      y = log[n-pow_9[num9]]
    else:
      y = ans(n-pow_9[num9])
      log[n-pow_9[num9]] = y
    return min(x+1,y+1)
print(ans(N))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def main():
    N = int(input())
    ind = [1]
    tmp = 6
    while tmp <= N:
        ind.append(tmp)
        tmp *= 6
    tmp = 9
    while tmp <= N:
        ind.append(tmp)
        tmp *= 9
    ind = sorted(ind)
    INF = int(1e9)
    dp = [INF] * (N+1)
    dp[0] = 0
    for i in range(1, N+1):
        for t in ind:
            if i - t >= 0:
                dp[i] = min(dp[i], dp[i-t]+1)
            else:
                break
    # print(dp[:20])
    print(dp[N])
    


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import math
import itertools

N = int(input().split()[0])

# 6を使うパターンを列挙
i = 0
p_6_list = []
while 6 ** i <= N:
    p_6_list.append(6 ** i)
    i += 1

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

p_6_gen = list(itertools.product(range(0, 6), repeat=len(p_6_list)))
min_count = float("inf")

for p_6 in p_6_gen:
    x = sum([x * i for x, i in zip(p_6_list, list(p_6))])
    c = sum(list(p_6))

    if c >= min_count:
        # この時点ですでに最小記録更新できないとわかるので、
        # あとの計算は実施しない
        continue

    balance = N - x
    if balance < 0:
        continue

    for y in reversed(p_9_list):
        # 大きい方から払えるだけ払う
        y_count = balance // y
        balance -= y * y_count
        c += y_count
        if balance == 0:
            break

    min_count = min(min_count, c)

ans = min_count
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
cnt = n
ans = n

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

print(ans)

Submission status: Accepted

Solution code:
ref = [6, 36, 216, 1296, 7776, 46656, 9, 81, 729, 6561, 59049]
N = int(input())
dp = list(range(N+1))
for x in ref:
	for i in range(x, N+1):
		y = dp[i-x] + 1
		if y < dp[i]:
			dp[i] = y
print(dp[N])

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, deque

input = sys.stdin.readline

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

def main():
    N = int(input())
    f_inf = float('inf')
    # DP テーブルを初期化　(最小化問題なので INF に初期化)
    MAX_N = 110000
    dp = [f_inf] * MAX_N
    dp[0] = 0
    for i in range(1, N+1):
        for j in range(N):
            pow6 = 6 ** j
            if pow6 > N:
                break
            dp[i] = min(dp[i], dp[i-pow6] + 1)
        for j in range(N):
            pow9 = 9 ** j
            if pow9 > N:
                break
            dp[i] = min(dp[i], dp[i-pow9] + 1)
    print(dp[N])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, deque

input = sys.stdin.readline

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

def main():
    N = int(input())
    f_inf = float('inf')
    # DP テーブルを初期化　(最小化問題なので INF に初期化)
    MAX_N = 110000
    dp = [f_inf] * MAX_N
    dp[0] = 0
    for i in range(1, N+1):
        for j in range(N):
            pow6 = 6 ** j
            if pow6 > N:
                break
            dp[i] = chmin(dp[i], dp[i-pow6] + 1)
        for j in range(N):
            pow9 = 9 ** j
            if pow9 > N:
                break
            dp[i] = chmin(dp[i], dp[i-pow9] + 1)
    print(dp[N])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
dp = [-1 for i in range(n+1)]
c = [1]
for i in [6,9]:
    c += [i**j for j in range(1,10) if i**j <=10**5]
# print(c)
for i in range(n+1):
    # print(i)
    if i == 0:
        dp[0] = 0
    else:
        cand = [dp[i-j]+1 for j in c if i-j>=0]
        # print('candidate',cand)
        dp[i] = min(cand)
print(dp[n])

Submission status: Accepted

Solution code:
lists=[]
emptylists=[]
numbers=int(input())

for nums in range(numbers+3):
    
    if nums<6:
        lists.append(int(nums))
         
    elif nums==6 or nums==36 or nums==216 or nums==1296 or nums==7776 or nums==46656:
        lists.append(1)
        
    elif nums==9 or nums==81 or nums==729 or nums==6561 or nums==59049:
        lists.append(1)
        
    else:
        power6=0
        power9=0
        for k in range(7):
            if 6**(k)< nums <6**(k+1):
                power6=k
                break   
                
        for j in range(6):
            if 9**(j) <nums< 9**(j+1):
                power9=j
                break
        add=min(min(lists[nums-6**(k)]+1 for k in range(0,power6+1)),min(lists[nums-9**(j)]+1 for j in range(0,power9+1)))
        lists.append(add)
print(lists[numbers])

Submission status: Accepted

Solution code:
N=int(input())

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

for i in range(2,N+1):
  L=[M[i-1]+1]
  j=0
  while i-6**j>=0:
    L.append(M[i-6**j]+1)
    j+=1
  j=0
  while i-9**j>=0:
    L.append(M[i-9**j]+1)
    j+=1
  M[i]=min(L)
#print(M)

print(M[N])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


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

    dp = [float('inf')]*(N+1)
    dp[0] = 0
    for i in range(N+1):
        t = 1
        while t<=i:
            dp[i] = min(dp[i], dp[i-t]+1)
            t *= 6
        t = 9
        while t<=i:
            dp[i] = min(dp[i], dp[i-t]+1)
            t *= 9
    
    print(dp[N])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
dp = [0] * (10 ** 5 + 10)
dp[0] = 0
for i in range(1, (10 ** 5) + 10):
    dp[i] = 10 ** 5 + 1
    p = 1
    while p <= i:
        dp[i] = min(dp[i], dp[i - p] + 1)
        p *= 6

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

print(dp[N])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import itertools
N = int(input())
result = 10**18
for six in itertools.product(range(6), repeat=6):
    ans = 0
    SUM = 0
    for i in range(1, 7):
        SUM += (6**i) * six[i-1]
    if SUM <= N:
        ans += sum(six)
        rem = N-SUM
        for j in range(1, 6):
            if rem >= 9**(6-j):
                ans += rem // (9**(6-j))
                rem -= (rem // (9**(6-j))) * (9**(6-j))
        ans += rem
        result = min(ans, result)
print(result)

Submission status: Accepted

Solution code:
n = int(input())
res = n
for i in range(n+1):
    cnt = 0
    t = i
    while t > 0:
        cnt += t % 6
        t //= 6
    t = n - i
    while t > 0:
        cnt += t % 9
        t //= 9

    res = min(res, cnt)

print(res)

Submission status: Accepted

Solution code:
n=int(input())

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

for i in range(n+1):
    power=1
    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])

Submission status: Accepted

Solution code:
from bisect import bisect_right

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


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

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

    """
    i円分を6**xxx で、　残りを９**yyyと１*zzzで構成する。これらを全通り試す
    """

    ans = N
    for i in range(N+1):
        cnt = 0
        sum_six = i
        sum_nine = N-i
        while sum_six > 0:
            idx = bisect_right(sixs, sum_six) - 1
            tmp = sum_six // sixs[idx]
            cnt += tmp
            sum_six -= tmp * sixs[idx]

        while sum_nine > 0:
            idx = bisect_right(nines, sum_nine) - 1
            tmp = sum_nine // nines[idx]
            cnt += tmp
            sum_nine -= tmp * nines[idx]

        ans = min(ans, cnt)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import bisect as bi

def ref(n):
  if n < 6:
    return n
  else:
    s6 = l6[bi.bisect(l6, n)-1]
    s9 = l9[bi.bisect(l9, n)-1]
    return min(n//s6 + ref(n%s6), 1+ref(n-s9))

l6 = [6**i for i in range(7)]
l9 = [9**i for i in range(6)]
print (ref(int(input())))

Submission status: Accepted

Solution code:
N = int(input())

# 1, 6, 9 の階乗の組み合わせの合計が N
ans = N
for i in range(N + 1):
    cnt = 0
    total = i
    while total > 0:
        cnt += total % 6
        total //= 6
    j = N - i
    while j > 0:
        cnt += j % 9
        j //= 9
    ans = min(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline

# 整数bをa進数で表現した時の各桁の和
# (ex. 7,6 => (6**1)*1 + (6**0)*1 => 1+1=2
def func(n,a):
    x = 0
    while n > 0:
        x += n%a
        n //= a
    return x

def main():
    N = int(input())
    mi = N
    for i in range(N+1):
        mi = min(mi, func(i,6) + func(N-i,9))
    print(mi)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
cnt = float('inf')
for i in range(0,n+1):
  j=n-i
  temp=0
  while i:
    temp+=i%9
    i//=9
  while j:
    temp+=j%6
    j//=6
  cnt=min(temp,cnt)
    
print(cnt)

Submission status: Accepted

Solution code:
n = int(input())

ls = []
k = 1
while True:
    k *= 6
    if k > n:
        break
    ls.append([k, 6])

k = 1
while True:
    k *= 9
    if k > n:
        break
    ls.append([k, 9])
ls.append([1, 1])
ls.sort(key=lambda x: x[0], reverse=True)

res = float('inf')


def dfs(x, count, index):
    global res
    if count > res:
        return
    if index == len(ls):
        if x == 0:
            res = min(res, count)
        return
    k, base = ls[index]
    m = min(x // k, max(base - 1, 5))
    if (m + 1) * k < x:
        return
    for i in range(m, -1, -1):
        dfs(x - i * k, count + i, index + 1)


dfs(n, 0, 0)
print(res)

Submission status: Accepted

Solution code:
def base(x,p):
    if int(x/p) >= 1:
        return base(int(x/p),p)+str(x%p)
    return str(x%p)
n = int(input())
c = 10**9
for i in range(n+1):
  c = min(c,sum(list(map(int,(base(i,6)+base(n-i,9))))))
print(c)

Submission status: Accepted

Solution code:
import sys

if sys.platform =='ios':
    sys.stdin=open('input_file.txt')
   
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)

Submission status: Accepted

Solution code:
n = int(input())

xs_0 = [1]
i = 1
while True:
    if 6 ** i > n:
        break
    xs_0.append(6 ** i)
    i += 1
i = 1
while True:
    if 9 ** i > n:
        break
    xs_0.append(9 ** i)
    i += 1

xs = sorted(xs_0)

counts = [0]
for i in range(1, n+1):
    opts = [_ for _ in xs if _ <= i]
    tmps = []
    for opt in opts:
        tmp = counts[i-opt] + 1
        tmps.append(tmp)
    counts.append(min(tmps))

print(counts[-1])

Submission status: Accepted

Solution code:
N = int(input())

dp = [10**9 for _ in range(N+1)] # 0円からN円までのリスト
dp[0] = 0

for i in range(1, N+1): # i円払う最小手数を入れる
    dp[i] = min(dp[i], dp[i-1] + 1)

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

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

ans = dp[N]
print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
N = int(input())
dp = [999999] * (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])

Submission status: Accepted

Solution code:
N = int(input())
inf = 10 ** 6
dp = [inf] * (N + 1)
dp[0] = 0
for i in range(N):
  if i + 1 <= N:
    dp[i + 1] = min(dp[i] + 1, dp[i + 1])
  for j in range(1, 8):
    if i + 6 ** j <= N:
      dp[i + 6 ** j] = min(dp[i] + 1, dp[i + 6 ** j])
  for j in range(1, 7):
    if i + 9 ** j <= N:
      dp[i + 9 ** j] = min(dp[i] + 1, dp[i + 9 ** j])
print(dp[N])

Submission status: Accepted

Solution code:
import sys
import numpy as np


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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())

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

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = [6**i for i in range(7)]
q = [9**j for j in range(6)]
m = {}

def b(n):
  if n < 6:
    return n
  elif n in m:
    return m[n]
  else:
    m_s = max(i for i in s if i<=n)
    m_q = max(j for j in q if j<=n)
    ms = n - m_s
    mq = n - m_q
    m[n] = min(b(ms)+1, b(mq)+1)
    return m[n]

print(b(n))

Submission status: Accepted

Solution code:
N = int(input())
ans = []

for i in range(N + 1):
    count = 0
    n_f = N - i
    n_s = i
    while n_f != 0:
        count += n_f % 6
        n_f //= 6
    while n_s != 0:
        count += n_s % 9
        n_s //= 9
    ans.append(count)

print(min(ans))

Submission status: Accepted

Solution code:
N = int(input())

A = [1]
tmp = 6
while tmp < 10**5:
    A.append(tmp)
    tmp *= 6
tmp = 9
while tmp < 10**5:
    A.append(tmp)
    tmp *= 9

Ans = [float("inf")] * (10**5+1)
Ans[0] = 0

for i in range(1,10**5+1):
    tmp = float("inf")
    for j in A:
        if i-j >= 0:
            if tmp > Ans[i-j] + 1:
                tmp = Ans[i-j] + 1
    Ans[i] = tmp
print(Ans[N])

Submission status: Accepted

Solution code:
n = int(input())

res = float('inf')
for i in range(0, n + 1):
    cnt = 0
    t = i
    while t > 0:
        cnt += t % 6
        t //= 6
    t = n - i
    while t > 0:
        cnt += t % 9
        t //= 9
    res = min(res, cnt)
print(res)

Submission status: Accepted

Solution code:
N = int(input())
li=[6,9,36,81,216,729,1296,6561,7776,46656,59049]
dp = [i for i in range(100010)]
for a in li:
    for x in range(a,N+1):
        dp[x] = min(dp[x],dp[x-a]+1)
print(dp[N])

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

n = inp()
dp = [mod for i in range(2*n)]
dp[0] = 0
p_6 = []
p_9 = []
tmp = 1
while tmp <= n:
    p_6.append(tmp)
    tmp *= 6
tmp = 1
while tmp <= n:
    p_9.append(tmp)
    tmp *= 9


for i in range(n):
    for j in p_6:
        if i+j <= n:
            dp[i+j] = min(dp[i+j],dp[i]+1)
    for k in p_9:
        if i+k <= n:
            dp[i+k] = min(dp[i+k],dp[i]+1)

print(dp[n])

Submission status: Accepted

Solution code:
# ABC099 C - Strange Bank 
N = int(input())
 
ans = N
for i in range(N+1):
    count = 0
    t = i
    while t:
        count += t%6
        t //= 6
    t = N-i
    while t:
        count += t%9
        t //= 9
    ans = min(ans, count)
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
ls=[i for i in range(N+1)]
cand=[1]
x=6
while (x<=N):
  cand.append(x)
  x*=6
x=9
while (x<=N):
  cand.append(x)
  x*=9
cand.sort()
for i in range(1,N+1):
  y=N
  for e in cand:
    if e>i: break
    if ls[i-e]<y:y=ls[i-e]
  ls[i]=y+1
print(ls[N])

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate
import sys



def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LIM(): return list(map(lambda x:int(x) - 1, sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def LIRM(n): return [LIM() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 1000000007

n = I()




def recur(c, i):
    if c < i:
        return c
    ret = 1
    while ret * i <= c:
        ret *= i
    else:
        return min((recur(c - ret, 6) + 1), (recur(c - ret, 9) + 1))



print(min(recur(n, 6), recur(n, 9)))