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:
n=int(input())
c=[1]
i=1
while (6**i)<=100000:
    c.append(6**i)
    i+=1
i=1
while (9**i)<=100000:
    c.append(9**i)
    i+=1
c.sort(reverse=True)
dp=[[0]*(n+1) for _ in range(len(c)+1)]
dp[0]=[i for i in range(n+1)]

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

print(dp[-1][-1])

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 % 9
        t //= 9
    t = N - i
    while t > 0:
        cnt += t % 6
        t //= 6
    ans = min(ans, cnt)

print(ans)

Submission status: Accepted

Solution code:
N = int(input())

ans = N
for v9 in range(N + 1):
    cnt = 0
    t = v9
    w = 9 ** 5
    while t >= 9:
        if t >= w:
            cnt9, t = divmod(t, w)
            cnt += cnt9
        w //= 9
    t = N - (v9 - t)
    w = 6 ** 7
    while t >= 6:
        if t >= w:
            cnt6, t = divmod(t, w)
            cnt += cnt6
        w //= 6
    ans = min(ans, cnt + t)

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
s=set()
s.add(1)
a=6
while a<=n:
  s.add(a)
  a*=6
b=9
while b<=n:
  s.add(b)
  b*=9
dp=[10**9]*(n+1)
dp[0]=0
dp[1]=1
for i in range(n+1):
  for t in s:
    if i+t<=n:
      dp[i+t]=min(dp[i+t],dp[i]+1)
print(dp[n])

Submission status: Accepted

Solution code:
def solve():
    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)
    return res

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

Submission status: Accepted

Solution code:
cand = [1]
MAX = 10**5 +1
for c in (6,9):
  coin = 1
  while 1:
    coin *= c
    if coin <= MAX:
      cand.append(coin)
    else:
      break
cand.sort()

dp = [float('inf') for i in range(MAX)]
dp[0] = 0
n = int(input())
for i in range(n):
  for c in cand:
    if i+c < MAX:
      dp[i+c] = min(dp[i+c], dp[i]+1)
print(dp[n])

Submission status: Accepted

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

for i in range(1,n+1):
    DP[i]=DP[i-1]+1
    for num in (6,9):
        cnt=1
        while num**cnt<=i:
            DP[i]=min(DP[i],DP[i-num**cnt]+1)
            cnt +=1

print(DP[n])

Submission status: Accepted

Solution code:
n = int(input())

res = n
for i in range(0, n+1):
    cnt = 0
    val = i
    while val > 0:
        cnt += val % 6
        val //= 6
    val = n - i
    while val > 0:
        cnt += val % 9
        val //= 9
    if res > cnt:
        res = cnt

print(res)

Submission status: Accepted

Solution code:
n = int(input())
dp=[100000]*100003
dp[0] = 0
for i in range(1,n+1):
    p = 1
    while p <= i:
        dp[i] = min(dp[i], dp[i - p] + 1)
        p *= 6
    q = 1
    while q <= i:
        dp[i] = min(dp[i], dp[i - q] + 1)
        q *= 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):
    for j in range(7):
        if i+6**j>n:
            continue
        dp[i+6**j]=min(dp[i+6**j],dp[i]+1)
        if i+9**j<=n:
            dp[i+9**j]=min(dp[i+9**j],dp[i]+1)
print(dp[n])

Submission status: Accepted

Solution code:
from collections import deque


max_n = 110000
dp = [-1] * max_n  # -1を未探索とする
dp[0] = 0  # 初期条件の設定
n = int(input())
que = deque([])
que.append(dp[0])
while que:
    v = que.popleft()
    pow = 1
    while v + pow <= n:
        if dp[v + pow] == -1:
            dp[v + pow] = dp[v] + 1
            que.append(v + pow)
        pow *= 6
    pow = 1
    while v + pow <= n:
        if dp[v + pow] == -1:
            dp[v + pow] = dp[v] + 1
            que.append(v + pow)
        pow *= 9
# print(dp)
print(dp[n])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
a = [1]
q = [10000000000000 for _ in range(n+1)]
q[0] = 0

for i in range(6):
    a.append(6**(i+1))
for i in range(5):
    a.append(9**(i+1))
    
a.sort()

for i in range(1,n+1):
    for j in range(12):
        x = a[j]
        if i-x >= 0:
            q[i] = min(q[i] , q[i-x] + 1)
            
print(q[n])

Submission status: Accepted

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

Submission status: Accepted

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

for i in range(1,n+1):
    DP[i]=DP[i-1]+1
    for P in (6,9):
        cnt=1
        while P**cnt<=i:
            DP[i]=min(DP[i-1]+1,DP[i-P**cnt]+1,DP[i])
            cnt +=1
            
print(DP[n])

Submission status: Accepted

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

for i in range(1,n+1):
    DP[i]=DP[i-1]+1
    for P in (6,9):
        cnt=1
        while P**cnt<=i:
            DP[i]=min(DP[i-1]+1,DP[i-P**cnt]+1,DP[i])
            cnt +=1

print(DP[n])

Submission status: Accepted

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

for i in range(1,n+1):
    DP[i]=DP[i-1]+1
    for point in (6,9):
        cnt=1
        while point**cnt<=i:
            DP[i]=min(DP[i-1]+1,DP[i-point**cnt]+1,DP[i])
            cnt +=1
            
print(DP[n])

Submission status: Accepted

Solution code:

import numpy as np

inf=10**7
n=int(input())
coin=[6**x for x in range(10)]
coin+=[9**x for x in range(1,10)]

dp=[0]*(n+1)
for (i,x) in enumerate(dp):
    dp[i]+=inf
dp[0]=0


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

Submission status: Accepted

Solution code:

inf=10**7
n=int(input())

ad=[6**x for x in range(10)]
ad2=[9**x for x in range(1,10)]
ad.extend(ad2)

a=[inf]*(n+1)
a[0]=0
for i in range(n+1):
    for x in ad:
        if(x+i<=n):a[x+i]=min(a[x+i],a[i]+1)



print(a[n])

Submission status: Accepted

Solution code:
import sys
import os


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

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

    ret = N
    for n in range(N+1):
        cnt = 0
        i = n

        while (i > 0):
            cnt += i % 6
            i //= 6

        j = N - n
        while (j > 0):
            cnt += j % 9
            j //= 9

        ret = min(cnt, ret)

    print(ret)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
n = int(input())
dp = [0]
for i in range(1, n+1):
    now = []
    k = 1
    while i >= k:
        now.append(dp[i-k]+1)
        k *= 6
    k = 1
    while i >= k:
        now.append(dp[i-k]+1)
        k *= 9
    dp.append(min(now))
print(dp[-1])

Submission status: Accepted

Solution code:
n=int(input())
nl=[9**i for i in range(1,6)][::-1]
sl=[6**i for i in range(1,7)][::-1]
a=n
for i in range(n+1):
    totals=0
    ps=i
    for j in sl:
        if ps >= j:
            totals+=ps//j
            ps= ps-ps//j*j
    totaln=0
    pn=n-i
    for k in nl:
        if pn >=k:
            totaln+= pn //k
            pn=pn-pn//k*k
    a=min(a,totals+totaln+ps+pn)
print(a)

Submission status: Accepted

Solution code:
n=int(input())
nl=[9**i for i in range(1,6)][::-1]
sl=[6**i for i in range(1,7)][::-1]
tl=[]
for i in range(n+1):
    totals=0
    ps=i
    for j in sl:
        if ps >= j:
            totals+=ps//j
            ps= ps-ps//j*j
    totaln=0
    pn=n-i
    for k in nl:
        if pn >=k:
            totaln+= pn //k
            pn=pn-pn//k*k
    tl.append(totals+totaln+ps+pn)
print(min(tl))

Submission status: Accepted

Solution code:
N = int(input())

def calculate(n):

    indexes = [0]
    for i in range(n):
        indexes.append(0)


    for index in range(1,n+1):
        pow6 = 6
        pow9 = 9
        pows = []
        if index == 6:
            indexes[index] = 1
            continue
        elif index == 9:
            indexes[index] = 1
            continue
        elif index < 9:
            indexes[index] = index
            continue
        else:
            while pow6 <= index:
                pows.append(indexes[index - pow6] + 1)
                pow6 = pow6 * 6
            while pow9 <= index:
                pows.append(indexes[index - pow9] + 1)
                pow9 = pow9 * 9

            pows.append(indexes[index - 1] + 1)

            indexes[index] = min(pows)



    print(indexes[n])
calculate(N)

Submission status: Accepted

Solution code:
n=int(input())
def k(a,b):
    ans=0
    while (a!=0):
        ans+=a%b
        a//=b
    return ans
res=10**10
for i in range(n+1):
    res=min(res,k(i,9)+k(n-i,6))
print(res)

Submission status: Accepted

Solution code:
n = int(input())
ans = n
# 6**k　円を6回引き出すのは 6**(k+1)で代用できる.
# よって A円を引き出すには, 6**k 円を(A//6**i)%6 回引き出せば良い.
for i in range(n+1):
    # 6, 6**2, 6**3, ... で計i円, 
    # 9, 9**2, 9**3, ... で計n-i円引き出す.
    cnt, p6, p9 = 0, i, n-i
    while p6 > 0:
        cnt += p6 % 6
        p6 //= 6
    while p9 >0:
        cnt += p9 %9
        p9 //= 9
    if cnt < ans:
        ans = cnt
print(ans)

Submission status: Accepted

Solution code:
pow9 = [1, 9, 81, 729, 6561, 59049]
pow6 = [1, 6, 36, 216, 1296, 7776, 46656]
memo={1:1}
def cand(n):
    if memo.get(n):
        return memo[n]
    else:
        for c in pow6[::-1]:
            if c == n:
                memo[n] = 1
                return 1
            elif c < n:
                a = 1 + cand(n - c)
                break
        for c in pow9[::-1]:
            if c == n:
                return 1
            elif c < n:
                b = 1 + cand(n - c)
                break
        memo[n] = min(a,b)
        return memo[n]
n = int(input())
print(cand(n))

Submission status: Accepted

Solution code:
n = int(input())
inf = 10**9
dp = [inf for i in range(n+1)]
dp[0] = 0
for i in range(n):
    if dp[i] != inf:
        #1円引き出す場合
        dp[i+1] = min(dp[i] + 1, dp[i+1])
        num = 6
        while i + num <= n:
            dp[i + num] = min(dp[i] + 1, dp[i+num])
            num *= 6
        num = 9
        while i + num <= n:
            dp[i + num] = min(dp[i] + 1, dp[i+num])
            num *= 9

print(dp[n])

Submission status: Accepted

Solution code:
n = int(input())

dp = [i for i in range(101010)]

#dp[i] = i円払うのに必要な最小値
#6ˆn円,0<=i<=Nにおいて、dp[i+6ˆn] = min(dp[i+6ˆn] ,dp[i]+1)  


t = 7
while True:
    for i in range(101010):
        if 6**t+(i+1) < 101010:
            dp[6**t+(i)] = min(dp[6**t+(i)], dp[i] + 1) 
    t -= 1
    if t == 0:
        break


t = 7
while True:
    for i in range(101010):
        if 9**t+(i+1) < 101010:
            dp[9**t+(i)] = min(dp[9**t+(i)], dp[i] + 1)
    t -= 1
    if t == 0:
        break

i = 0
while i+1 < 101010:
    dp[i+1] = min(dp[i+1],dp[i]+1)
    i += 1

#print(dp)
print(dp[n])

Submission status: Accepted

Solution code:
N=int(input())
l=[i for i in range(100010)]
p=[6**i for i in range(1,7)]+[9**j for j in range(1,6)]
p.sort()

for c in p:
  if c>N:break
  for i in range(c, N+1):
    l[i] = min(l[i],l[i-c]+1)
print(l[N])

Submission status: Accepted

Solution code:
n = int(input())

dp = [i for i in range(101010)]

#dp[i] = i円払うのに必要な最小値
#6ˆn円,0<=i<=Nにおいて、dp[i+6ˆn] = min(dp[i+6ˆn] ,dp[i]+1)  

#6の倍数
t = 10
while True:
    for i in range(101010):
        if 6**t+(i+1) < 101010:
            dp[6**t+(i)] = min(dp[6**t+(i)], dp[i] + 1) 
    t -= 1
    if t == 0:
        break

#9の倍数
t = 10
while True:
    for i in range(101010):
        if 9**t+(i+1) < 101010:
            dp[9**t+(i)] = min(dp[9**t+(i)], dp[i] + 1)
    t -= 1
    if t == 0:
        break

i = 0
while i+1 < 101010:
    dp[i+1] = min(dp[i+1],dp[i]+1)
    i += 1

#print(dp)
print(dp[n])

Submission status: Accepted

Solution code:
def dfs(cc,t):
    global ans
    if t >= ans:
        return -1
    if t < ans:
        for i in range(6, 0, -1):
            if cc >= 9**i and t + cc//(9**i) < ans: 
                dfs(cc - 9**i, t + 1)
            if cc >= 6**i and t + cc//(6**i) < ans:
                dfs(cc - 6**i, t + 1)
    if ans > t + cc:
        ans = t + cc
        
N = int(input())
ans = N
dfs(N, 0)
print(ans)

Submission status: Accepted

Solution code:
N = int(input()) 
DP = [10000000]*(2*N+1)
DP[0] = 0
for i in range(0, N+1):
  DP[i+1] = min(DP[i+1],DP[i]+1)
  s = 6
  while s <= N:
    DP[i + s] = min(DP[i + s],DP[i]+1) 
    s = s*6
  n = 9
  while n <= N:
    DP[i + n] = min(DP[i + n],DP[i]+1)  
    n = n*9
print(DP[N])

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

from math import log, floor

def main():
  n = int(input())
  min = 10**10
  for i in range(n+1):
    cc = 0
    t = i
    while t > 0:
      cc += (t%6)
      t//=6
    t = n - i
    while t > 0:
      cc += (t%9)
      t//=9
    if min > cc:
      min = cc
  print(min)

if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
N = int(input())

def six_p(n) :
    temp = 0
    for i in reversed(range(7)) :
        temp += n//(6**i)
        n = n%(6**i)
    return temp

def nin_p(n) :
    temp = 0
    for i in reversed(range(6)) :
        temp += n//(9**i)
        n = n%(9**i)
    return temp

ans = 10**6
for i in range(N+1):
    ans = min(ans, six_p(i)+nin_p(N-i))

print(ans)

Submission status: Accepted

Solution code:
n = int(input())

dp = [0] * (n + 1)
for i in range(n):
     if i in range(5):
          dp[i+1] = i + 1
     else:
          j = 1
          k = 1
          a = [100001]
          b = [100001]
          while i + 1 - 6**j >= 0:
              a += [dp[i + 1 - 6**j]]
              j += 1
          while i + 1 - 9**k >= 0:
              b += [dp[i + 1 - 9**k]]
              k += 1
          dp[i + 1] = min(dp[i],min(a),min(b)) + 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())
ans=N
for i in range(N+1):
    cnt=0 #カウント初期化
    t=i
    while t>0:    #tが正の時，カウントにtを6で割ったあまりを足す．そしてtは6で割った商に更新
        cnt+=t%6
        t//=6
    j=N-i #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())

inf = n + 100
dp = [inf] * (n+1)
dp[0] = 0
for i in range(n):
    if i <= n-1:
        dp[i+1] = min(dp[i+1], dp[i] + 1)

    cnt6 = 6
    while True:
        if i + cnt6 <= n:
            dp[i + cnt6] = min(dp[i + cnt6], dp[i] + 1)
            cnt6 *= 6
        else:
            break

    cnt9 = 9
    while True:
        if i + cnt9 <= n:
            dp[i + cnt9] = min(dp[i + cnt9], dp[i] + 1)
            cnt9 *= 9
        else:
            break

print(dp[n])

Submission status: Accepted

Solution code:
n = int(input())
INF = 10**5
answer = INF
for i in range(n+1):
    money = i
    cnt = 0
    while money > 0:
        cnt += money % 6
        money //= 6

    money = n-i
    while money > 0:
        cnt += money % 9
        money //= 9
    if answer > cnt:
        answer = cnt
print(answer)

Submission status: Accepted

Solution code:
n = int(input())
INF = 10**5
answer = INF

for i in range(n+1):
    cost = i
    ans = 0
    for p in range(8):
        ans += (cost // 6**p) % 6

    cost = n-i
    for q in range(7):
        ans += (cost // 9**q) % 9
    if answer > ans:
        answer = ans
print(answer)

Submission status: Accepted

Solution code:
N = int(input())

def calculate(n):

    memo =  [0 for i in range(N+1)] # 0-N

    for index in range(1,n+1):
        pow6 = 6
        pow9 = 9
        if index < 6:
            memo[index] = index
        elif index == 6:
            memo[index] = 1
        elif index == 9:
            memo[index] = 1
        else:
            values = []

            while pow6 <= index:
                values.append(1 + memo[index - pow6])
                pow6 = pow6 * 6

            while pow9 <= index:
                values.append(1 + memo[index - pow9])
                pow9 = pow9 * 9

            values.append(1+memo[index-1])
            minValue = min(values)

            memo[index] = minValue

    return memo

result = calculate(N)
print(result[N])

Submission status: Accepted

Solution code:
import math,sys
sys.setrecursionlimit(20000000)
N = int(input())
memo = [-1 for i in range(110000)]
def calculate(n):

    if n == 0:
        memo[n] = 0
        return 0

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

    res = n

    pow6Num = 1
    while pow6Num*6 <= n:
        pow6Num = pow6Num * 6
        res = min(res, calculate(n - pow6Num) + 1)


    pow9Num = 1
    while pow9Num*9 <= n:
        pow9Num = pow9Num * 9
        res = min(res, calculate(n - pow9Num) + 1)

    memo[n] = int(res)
    return int(res)



result = calculate(N)
print(memo[N])

Submission status: Accepted

Solution code:
n=int(input())

dp=[0]*(n+1)

for i in range(n+1):
    cnt=0
    j=i
    for exp6 in range(6,0,-1):
        curcnt=j//(6**exp6)
        j-=curcnt*(6**exp6)
        cnt+=curcnt
    dp[i]=j+cnt

for i in range(9**6):
    j=i
    paynine=0
    cnt=0
    exp9=1
    while j>0:
        bit=j%9
        j//=9
        cnt+=bit
        paynine+=bit*(9**exp9)
        exp9+=1
    
    if paynine>n:
        break

    dp[n]=min(dp[n],dp[n-paynine]+cnt)

print(dp[n])

Submission status: Accepted

Solution code:
N = int(input())

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

for i in range(1, N+1):
    dp[i] = 100001
    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())
dp=[10**9 for i in range(N+1)]
dp[0]=0
for i in range(N+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[-1])

Submission status: Accepted

Solution code:
N=int(input())
ans=N
for i in range(N+1):
    cnt=0
    t=i
    #print('===6===', i)
    while t>0:
        cnt+=t%6
        t//=6
    #print("cnt : {0}, t : {1}".format(cnt, t))
    j=N-i
    #print('====7===', i)
    while j>0:
        cnt+=j%9
        j//=9
    #print("cnt : {0}, t : {1}".format(cnt, t))
    #print(i, ans, cnt)
    ans = min(ans,cnt)
print(ans)

Submission status: Accepted

Solution code:
def cash(a,N):
    ans = 0
    for i in reversed(range(len(a))):
        num = N//a[i]
        N -= a[i]*num
        ans += num
    return ans


N = int(input())

cash6 = []
cash9 = []
for i in range(1000):
    tmp = 6**i
    if tmp>N:
        break
    cash6.append(tmp)
for j in range(1000):
    tmp = 9**j
    if tmp>N:
        break
    cash9.append(tmp)

ans = 1e9
for i in range(N+1):
    ans = min(ans,cash(cash6,i)+cash(cash9,N-i))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

LIMIT = 100000

unit = [1]
for a in [6, 9]:
    b = a
    while b <= LIMIT:
        unit.append(b)
        b *= a
unit.sort(reverse=True)


unit_num = len(unit)
unit = [0] + unit

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

for i in range(1, unit_num+1):
    for j in range(n+1):
        if j - unit[i] >= 0:
            dp[i][j] = min(dp[i-1][j], dp[i-1][j-unit[i]] + 1, dp[i][j-unit[i]] + 1)
        else:
            dp[i][j] = dp[i-1][j]          
print(dp[-1][-1])

Submission status: Accepted

Solution code:
n = int(input())

LIMIT = 100000

unit = [1]
for a in [6, 9]:
    b = a
    while b <= LIMIT:
        unit.append(b)
        b *= a
unit.sort()


unit_num = len(unit)
unit = [0] + unit

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

for i in range(1, unit_num+1):
    for j in range(n+1):
        if j - unit[i] >= 0:
            dp[i][j] = min(dp[i-1][j], dp[i-1][j-unit[i]] + 1, dp[i][j-unit[i]] + 1)
        else:
            dp[i][j] = dp[i-1][j]          
print(dp[-1][-1])

Submission status: Accepted

Solution code:
# BFS
from collections import deque

N=int(input())

dp = [-1] * 200005;
q = deque()

g = [1]
a = 6
while a <= 100000:
  g.append(a)
  a *= 6
a = 9
while a <= 100000:
  g.append(a)
  a *= 9
g.sort(reverse=True)

dp[0] = 0
q.append(0)

while len(q) > 0:
  v = q.popleft()
  if v == N: break
  for j in g:
    if dp[v+j] != -1: continue
    if v+j > N: continue
    dp[v+j] = dp[v] + 1
    q.append(v+j)

print(dp[N])

Submission status: Accepted

Solution code:
# 配るDP

N=int(input())

dp = [100000] * 200005;

g = [1]
a = 6
while a <= 100000:
  g.append(a)
  a *= 6
a = 9
while a <= 100000:
  g.append(a)
  a *= 9
g.sort(reverse=True)

dp[0] = 0
for i in range(N):
  for j in g:
    dp[i+j] = min( dp[i+j], dp[i]+1 )

print(dp[N])

Submission status: Accepted

Solution code:
import math

dp = [float('inf') for _ in range(200000)]
withdraw = []

N = int(input())

#引き出し可能な金額の配列にする
withdraw.append(1)

for i in range(20):
    if 100000 >= 6**i:
        withdraw.append(6**i)
    if 100000 >= 9**i:
        withdraw.append(9**i)

withdraw = sorted(list(set(withdraw)))

dp[0] = 0

for i in range(N+1):
    for j in withdraw:
        dp[i+j] = min(dp[i+j],dp[i]+1)
        
print(dp[N])

Submission status: Accepted

Solution code:
# Author: cr4zjh0bp
# Created: Mon Mar  2 00:21:30 UTC 2020
import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni = lambda: int(ns())
nin = lambda y: [ni() for _ in range(y)]
na = lambda: list(map(int, stdin.readline().split()))
nan = lambda y: [na() for _ in range(y)]
ns = lambda: stdin.readline().rstrip()
nsn = lambda y: [ns() for _ in range(y)]
ncl = lambda y: [list(ns()) for _ in range(y)]
nas = lambda: stdin.readline().split()

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

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

print(dp[N])

Submission status: Accepted

Solution code:
n=int(input())

k9=5
k6=6
n9=9**k9
smin=n
for i9 in range(n9):
    ii9=i9
    s=0
    m=0
    astr=""
    for ii in range(1,k9+2):
        r9=ii9%9
        ii9=(ii9-r9)//9    
        s=s*9+r9
        m=m+r9
        astr=astr+str(r9)
#    print("i9",i9,"astr",astr,"s",s,"m",m)
    
    nr=n-s
    nr1=nr
#    print("nr",nr,"m",m)
    
    if nr==0:
        snra=m
#        print(nr,m)
    elif nr>0:
        snra=m
        for jj in range(k6,-1,-1):
            nra=nr1//(6**jj)
            nr1=nr1%(6**jj)
            snra=snra+nra
#        print("jj",jj,"nra",nra,"nr1",nr1)
    if smin>snra:
        smin=snra
print(smin)

Submission status: Accepted

Solution code:
n = int(input())

def f(n, c):
    res = 0
    while n > 0:
        res += n%c
        n //= c
    return res

l = []
for i in range(n+1):
    l.append(f(i,9)+f(n-i,6))
print(min(l))

Submission status: Accepted

Solution code:
N = int(input())

dp = [None for _ in range(N+1)]
dp[0] = 0
for i in range(1, N+1):
    dp[i] = 100001
    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())

def solve(num, c):
    Result = 0
    while num > 0:
        Result += num%c
        num //= c
    return Result

result = []
for i in range(n+1):
    result.append(solve(i, 9)+ solve(n-i, 6))
print(min(result))

Submission status: Accepted

Solution code:
n = int(input())
dp = [i for i in range(n+1)]  # dp table 最初は全て1円で払う
for j in range(1, n+1):
    power = 1
    while power <= j:
        dp[j] = min(dp[j], dp[j - power] + 1)
        power *= 6
    power = 1
    while power <= j:
        dp[j] = min(dp[j], dp[j - power] + 1)
        power *= 9
print(dp[n])

Submission status: Accepted

Solution code:
n = int(input())
dp = [0 for _ in range(n+1)]
for i in range(1, n+1):  # iは金額
    dp[i] = i  # 初期化
    power = 1  # 累乗を初期化
    while power <= i:  # 累乗より小さい値の時はループに入る
        dp[i] = min(dp[i], dp[i - power] + 1)  # 漸化式
        power *= 6  # 6の累乗を更新
    power = 1  # 累乗を初期化
    while power <= i:  # 累乗より小さい時はループい入る
        dp[i] = min(dp[i], dp[i - power] + 1)  # 漸化式
        power *= 9  # 9の累乗を更新
print(dp[n])

Submission status: Accepted

Solution code:
#099_C
n=int(input())
def Count(x,p):
    res=0
    while x:
        res+=x%p
        x=x//p
    return res

ans=10**6+1
for i in range(0,n+1):
    ans=min(ans,Count(i,6)+Count(n-i,9))
    
print(ans)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    money = [6 ** i for i in range(7)] + [9 ** i for i in range(1, 6)]
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        dp[i] = min(dp[i - j] + 1 for j in money if i - j >= 0)
    print(dp[n])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    money = sorted([6 ** i for i in range(7)] + [9 ** i for i in range(1, 6)], reverse=True)
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        dp[i] = min(dp[i - j] + 1 for j in money if i - j >= 0)
    print(dp[n])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    money = sorted([6 ** i for i in range(7)] + [9 ** i for i in range(1, 6)], reverse=True)
    dp = [0] + [1000000] * n
    for i in range(1, n + 1):
        dp[i] = min(dp[i], *[dp[i - j] + 1 for j in money if i - j >= 0])
    print(dp[n])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#strange bank
n=int(input())
dp=[10**10 for i in range(200000)]
dp[0]=0
for i in range(1,100001):
    for j in range(9):
        num=3**j
        if i>=6**j and dp[i-6**j]+1<dp[i]:
            dp[i]=dp[i-6**j]+1
        if i>=9**j and dp[i-9**j]+1<dp[i]:
            dp[i]=dp[i-9**j]+1
print(dp[n])

Submission status: Accepted

Solution code:
# coding: utf-8

def get_pow(target: int, base: int):
    ans = 0
    current = base
    for i in range(1, target + 1):
        if current > target:
            break
        ans = i
        current *= base
    return ans


dic = {}


def get_ans(remain: int):
    if remain in dic:
        return dic[remain]
    if remain < 6:
        return max(0, remain)
    ans = remain

    pos9 = get_pow(remain, 9)
    for i in reversed(range(1, pos9 + 1)):
        ret = get_ans(remain - pow(9, i)) + 1
        ans = min(ans, ret)

    pow6 = get_pow(remain, 6)
    for i in reversed(range(1, pow6 + 1)):
        ret = get_ans(remain - pow(6, i)) + 1
        ans = min(ans, ret)

    dic[remain] = ans
    return ans


n = int(input().rstrip())
print(get_ans(n))

Submission status: Accepted

Solution code:
n = int(input())
INF = 10 ** 8
dp = [INF] * 100010
dp[0] = 0

for i in range(1, n + 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())
dp = [float('inf') for i in range(n+1)]
dp[0] = 0
for i in range(1,n+1):
    ngo = 1
    while ngo <= i:
        dp[i] = min(dp[i],dp[i-ngo]+1)
        ngo *= 6
    ngo = 1
    while ngo <= i:
        dp[i] = min(dp[i],dp[i-ngo]+1)
        ngo *= 9
print(dp[n])

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc099/tasks/abc099_c
L = [59049,46656,7776,6561,1296,729,216,81,36,9,6]
maxi = 100000
N = int(input())
memo = [0,1,2,3,4,5] + [-1 for _ in range(maxi)]
def f(n):
    if memo[n]!=-1:
        return memo[n]
    res = N
    for l in L:
        if n>=l:
            res = min(res,f(n-l)+1)
    memo[n] = res
    return res
print(f(N))

Submission status: Accepted

Solution code:
N=int(input())
a=[1,6,36,216,1296,7776,46656,9,81,729,6561,59049]
a=sorted(a)
dp=[-1]*(N+1)
dp[0]=0
for i in range(N):
    m=[]
    for j in range(len(a)):
        if(a[j]<=i+1):
            m.append(dp[(i+1)-a[j]]+1)
    dp[i+1]=min(m)
print(dp[N])

Submission status: Accepted

Solution code:
N = int(input())

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

unit = []
for i in range(1, 2**32):
    if 6 ** i > N:
        break
    unit.append(6 ** i)
for i in range(1, 2**32):
    if 9 ** i > N:
        break
    unit.append(9 ** i)

for v in unit:
    dp[v] = 1

for i in range(2, N+1):
    num = dp[i]
    for v in unit:
        num = min(num, dp[v] + dp[i - v])
    dp[i] = num

print(dp[N])

Submission status: Accepted

Solution code:
N = int(input())

roku = kyu = 1
h_list = [1]

while(roku<N):
    roku *= 6
    h_list.append(roku)

while(kyu<N):
    kyu *= 9
    h_list.append(kyu)

#print(h_list)

FIN = 10**7
dp = [FIN]*(N+1)
dp[0] = 0
for i in range(1, N+1):
    for j in range(len(h_list)):
        if h_list[j] <= i:
            dp[i] = min(dp[i], dp[i-h_list[j]]+1)
            #print(dp)

print(dp[N])

Submission status: Accepted

Solution code:
N = int(input())

lst = []
cnt = 1
while True:
    lst.append(6**cnt)
    if N < lst[-1]:
        lst.pop()
        break
    else:
        cnt += 1
cnt = 1
while True:
    lst.append(9**cnt)
    if N < lst[-1]:
        lst.pop()
        break
    else:
        cnt += 1
lst.append(1)
lst.sort()
i = 0
DP = [100000]*100001
DP[0] = 0
for i in range(100001):
    for add in lst:
        if i+add <= N:
            DP[i+add] = min(DP[i+add],DP[i]+1)
print(DP[N])

Submission status: Accepted

Solution code:
n = int(input())

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

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


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

print(dp[-1])

Submission status: Accepted

Solution code:
n=int(input())

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