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:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(100000)  # RecursionError対策

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)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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)

Submission status: Accepted

Solution code:
from functools import *
@lru_cache(maxsize=None) # memoization
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)#min coins, coins dp
  return s
for i in range(1,100001):f(i)
print(f(int(input()))) # answer

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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)

Submission status: Accepted

Solution code:
N = int(input())

# dp[i]: ちょうどi円を引き出すために必要な操作の最小回数
dp = [0] * (N + 1)

MAX = 10 ** 8

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

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

    # 9, 9 ** 2, 9 ** 3,...
    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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
# input here
_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

    # sys.stdin = io.StringIO(_INPUT)
    main()

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
N = int(input())

# dp[i] := i円引き出すのに必要な最小操作回数
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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:
            # print(i, j, i-j)
            dp[i] = min(dp[i], dp[i-j]+1)
print(dp[-1])

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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

#dp
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)

Submission status: Accepted

Solution code:
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=[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())
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])

Submission status: Accepted

Solution code:
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()
# print(L)

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)
print(dp[N])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
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()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
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()

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal
#from numba import jit

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)
    #print(nines, sixes)
    min_ans = INF
    for K in product(range(9), repeat = L):
        #print(K, '----------------')
        ans = 0
        s = 0
        for k, x in zip(K, nines):
            if k:
                ans += k
                s += x * k
        #print(ans, s)

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

    print(min_ans)

if __name__ == "__main__":
    run()

Submission status: Accepted

Solution code:
import sys


# \n
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()

Submission status: Accepted

Solution code:
import sys


# \n
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()

Submission status: Accepted

Solution code:
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

#############
# Main Code #
#############

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

# NlogNダイクストラ
# これも最短経路を求める問題
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

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

Submission status: Accepted

Solution code:
# 6**6 < 10**5 < 6**7
# 9**5 < 10**5 < 9**6

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
# dp[i] = 合計i円引き出すために必要な引出し回数
dp = [10**9 for _ in range(10 ** 5 + 1)]
dp[0] = 0

# 引き出せる金額のリスト
num = [1]
for i in range(1, 7):
    num.append(6**i)
for i in range(1, 6):
    num.append(9**i)

for i in range(10**5 + 1):
    for n in num:
        # 遷移元が存在する and 遷移先が存在する場合
        if dp[i] != -1 and i + n <= 10**5:
            dp[i + n] = min(dp[i + n], dp[i] + 1)

print(dp[N])

Submission status: Accepted

Solution code:
N = int(input())
ans = 100000
for A in range(N+1):
    num = 0
    B = N-A
    while A != 0:
        num  += A % 6
        A = A//6
    while B != 0:
        num  += B % 9
        B = B//9
    ans = min(ans,num)
print(ans)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    cand = [1]
    dp = [float('inf')] * (N + 5)
    tmp = 6
    cnt = 1
    while tmp**cnt <= N:
        cand.append(tmp**cnt)
        cnt += 1
    tmp = 9
    cnt = 1
    while tmp**cnt <= N:
        cand.append(tmp**cnt)
        cnt += 1
    cand.sort()
    dp[0] = 0
    for i in range(N+1):
        for c in cand:
            if i + c <= N:
                dp[i+c] = min(dp[i+c], dp[i] + 1)
    print(dp[N])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import math
sys.setrecursionlimit(10**6)

N = int(input())

INF = 10**10

dp = [0]*(N+1)

for i in range(N+1):
    dp[i] = INF
    
W = [1,6,9]

def rec(v):
    if dp[v] < INF:
        return dp[v]
    if v == 0:
        dp[v] = 0
        return 0
    
    # v-n を再帰
    res = INF
    for w in range(3):
        for x in range(int(math.log(N+1,6))+1):
            n = W[w]**x
            if v<n:
                continue
            res = min(res,rec(v-n) + 1)
            # メモして返す
            dp[v] = res
    return res
rec(N)
print(dp[N])

Submission status: Accepted

Solution code:
# C - Strange Bank
import math
N = int(input())

INF = 10**10

dp = [0]*(N+1)

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

dp[0] = 0
W = [1,6,9]

# dp{N} に最小値を記録する
# 今の金額
for v in range(1,N+1):
    for w in range(3):
        for x in range(int(math.log(N+1,6))+1):
            # 選ぶ数
            n = W[w]**x
            if v-n < 0:
                continue
            dp[v] = min(dp[v],dp[v-n] + 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%9
        t//=9
    j=N-i
    while j>0:
        cnt+=j%6
        j//=6
    ans = min(ans,cnt)
print(ans)

Submission status: Accepted

Solution code:
def fn(n, a):
    res = 0
    while n > 0:
        res += n % a
        n //= a

    return res


def solve(N):

    ans = 10 ** 5
    for i in range(N+1):
        tmp = fn(i, 6) + fn(N-i, 9)
        ans = min(ans, tmp)

    return ans


if __name__ == "__main__":
    N = int(input())
    print(solve(N))

Submission status: Accepted

Solution code:
#解説見ながら

n = int(input())

ans = n

for i in range(n+1) :
    c = 0
    a = n-i
    while a>0 :
        c += a%6
        a = a//6
    a = i
    while a>0 :
        c += a%9
        a = a//9
    if c<ans :
        ans = c

print(ans)

Submission status: Accepted

Solution code:
#####################################################################################################
##### コイン問題
#####################################################################################################
"""

ベンチマーク
コイン問題 (※ larger = False): http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4696859#1
E - Crested Ibis vs Monster (※ larger = True): https://atcoder.jp/contests/abc153/submissions/15396586

"""


def coin(larger=False, single=False):
    """
    ナップサックに入れる重さが W 丁度になる時の価値の最小値
    :param larger: False = (重さ = W)の時の最小価値
                   True  = (重さ =< W)の時の最小価値
    :param single: False = 重複あり

    dp[weight <= W+1] = 重さを固定した時の最小価値
    dp[W+1] = 重さがWより大きい時の最小価値
    """
    W2 = W + 1              # dp[W+1] に W より大きい時の全ての場合の情報を持たせる
    dp_max = float("inf")   # 総和価値の最大値
    dp = [dp_max] * (W2 + 1)
    dp[0] = 0               # 重さ 0 の時は価値 0

    for item in range(N):
        if single:
            S = range(W2, weight_list[item] - 1, -1)
        else:
            S = range(W2)
        for weight in S:
            dp[min2(weight + weight_list[item], W2)] = min2(dp[min2(weight + weight_list[item], W2)], dp[weight] + cost_list[item])
    if larger:
        return min(dp[w] for w in range(W, W2+1))
    else:
        return dp[W]

#######################################################################################################
import sys
input = sys.stdin.readline


def max2(x, y):
    return x if x > y else y

def min2(x, y):
    return x if x < y else y

W = int(input())
cost_list = [1]
weight_list = [1]
p = 6
while p<=W:
    cost_list.append(1)
    weight_list.append(p)
    p *= 6
p = 9
while p<=W:
    cost_list.append(1)
    weight_list.append(p)
    p *= 9
N = len(weight_list)

print(coin(larger=False, single=False))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000000)
n=int(input())
memo=[-1]*(10**7)
memo[0]=0
def rec(a:int):
    if a==0:
        return 0
    if memo[a]!=-1:
        return memo[a]
    res=100000
    for i in range(1,9):
        if 0<=a-6**i:
            res=min(res,rec(a-6**i)+1)
    for j in range(1,9):
        if 0<=a-9**j:
            res=min(res,rec(a-9**j)+1)
    res=min(res,rec(a-1)+1)

    memo[a] = res

    return res
print(rec(n))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
dp=[10**3]*(n+1)
dp[0]=0

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

Submission status: Accepted

Solution code:
N = int(input())
dp = [0] * 100500

import math
dp[1] = 1
for i in range(2, N+1):
    dp[i] = dp[i-1] + 1
    for j in range(math.floor(math.log(i, 6)) + 1):
        dp[i] = min(dp[i], dp[i - 6 ** j] + 1)
    for k in range(math.floor(math.log(i, 9) + 0.00000001) + 1):
        dp[i] = min(dp[i], dp[i - 9 ** k] + 1)


print(dp[N])

Submission status: Accepted

Solution code:
def cal(n,x):
    res=0
    while n>0:
        res+=n%x
        n//=x
    return res

N=int(input())

ans=N
for i in range(N+1):
    ans=min(ans,cal(i,6)+cal(N-i,9))
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
def f(x):
    ans=0
    while x>0:
        ans+=x%6
        x=x//6
    return ans
def g(x):
    ans=0
    while x>0:
        ans+=x%9
        x=x//9
    return ans
ans=n
for i in range(n+1): 
  ans=min(ans,f(i)+g(n-i))
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
def f(n):
    if dp[n] != -1:
        return dp[n]
    res = N
    for i in range(N):
        if n < 6**i:
            break
        res = min(res, f(n-6**i)+1)
    for i in range(N):
        if n < 9**i:
            break
        res = min(res, f(n-9**i)+1)
    dp[n] = res
    return res

N = int(input())
dp = [-1]*(N+1)
dp[0] = 0
f(N)
print(dp[N])