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:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n = INT()
a = [inf]*100001

a[0] = 0
for i in range(1,100001):
    a[i] = min(a[i], a[i-1]+1)
    j = 1
    while i - 6**j >= 0:
        a[i] = min(a[i], a[i-6**j]+1)
        j += 1
    j = 1
    while i - 9**j >= 0:
        a[i] = min(a[i], a[i-9**j]+1)
        j += 1

print(a[n])

Submission status: Accepted

Solution code:
n = int(raw_input())
dp = [j for j in range(n+1)] 
for i in range(1, n+1):
	for u in [6,9]:
		p = 1
		q = u ** p
		while((i  - q) >= 0):
			dp[i] = min(dp[i], 1 + dp[i - q])
			p += 1
			q = u ** p
print dp[n]

Submission status: Accepted

Solution code:
n = int(raw_input())
dp = [+float('inf')] * (n+1)
dp[0] = 0
for i in range(1, n+1):
	q = 1
	if i - q >= 0:
		dp[i] = min(dp[i], 1 + dp[i - q])
	for u in [6,9]:
		p = 1
		q = u ** p
		while((i  - q) >= 0):
			dp[i] = min(dp[i], 1 + dp[i - q])
			p += 1
			q = u ** p
print dp[n]

Submission status: Accepted

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

for n in range(N+1):
  c = 0
  t = n
  while t>0:
    c+=t%6
    t//=6
  t = N-n
  while t>0:
    c+=t%9
    t//=9
  a = min(a,c)
  
print(a)

Submission status: Accepted

Solution code:
n = int(input())
dp = [None] * (n+1)
dp[1] = 1
dp[0] = 0
sixs = [6]
nines = [9]
i = 1
while sixs[i-1] * 6 <= n:
    sixs.append(sixs[i-1]*6)
    i += 1

i = 1
while nines[i-1] * 6 <= n:
    nines.append(nines[i-1]*9)
    i += 1
for current in range(2, n+1):
    smin = n
    for six in sixs:
        if current - six >= 0 and dp[current-six] != None:
            smin = min(smin, dp[current-six] + 1)
    nmin = n
    #print (smin, nmin)
    for nine in nines:
        if current - nine >= 0 and dp[current-nine] != None:
            nmin = min(nmin, dp[current-nine] + 1)
    #print (dp)
    dp[current] = min(dp[current-1] + 1, nmin, smin)
print (dp[n])
#print (dp)

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
N = int(input())

coins = [(9 ** i) for i in range(1, 7)] + [(6 ** i) for i in range(1, 8)] + [1]
dp = [INF] * (N + 1)
dp[0] = 0
for i in range(len(coins)):
    for j in range(N + 1):
        if j + coins[i] > N:
            continue
        dp[j + coins[i]] = min(dp[j + coins[i]], dp[j] + 1)
print(dp[N])

Submission status: Accepted

Solution code:
from functools import lru_cache

n = int(input())
@lru_cache(maxsize=None)
def func(n):
  if n < 6:
    return n
  a = []
  b = 6
  while(b<=n):
    a.append(b)
    b*=6
  b = 9
  while(b<=n):
    a.append(b)
    b*=9
  ret = n
  a.sort(reverse=True)
  for i in a:
    ret = min(ret,1+func(n-i))
  return ret
print(func(n))

Submission status: Accepted

Solution code:
N = int(input())

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

dp = [10**6+10] * (N+1)
dp[0] = 0
for i in range(1, N+1):
    for j in cash:
        if i-j >= 0:
            dp[i] = min(dp[i], dp[i-j]+1)
print(dp[-1])

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
ans = float("inf")
def sub(x, base):
    if x==0:
        return 0
    i = 0
    while pow(base, i+1)<=x:
        i += 1
    return sub(x-pow(base,i), base) + 1
for i in range(n+1):
    ans = min(ans, sub(i,6)+sub(n-i,9))
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:
    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:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    N = int(input())

    X = [1]
    for i in range(1, 101):
        if 6**i > N:
            break
        X.append(6**i)
    for i in range(1, 101):
        if 9**i > N:
            break
        X.append(9**i)
    dp = [N+1] * (N+1)
    dp[0] = 0
    for i in range(N):
        for x in X:
            if i+x <= N:
                dp[i+x] = min(dp[i+x], dp[i] + 1)
    print(dp[N])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N=int(input())
from itertools import product
a=10**5
for p in product(range(9),repeat=5):
    n=N-sum([9**(i+1)*p[i] for i in range(5)])
    if n<0:continue
    b=sum(p)
    x=6**6
    while x>0:
        b+=n//x
        n%=x
        x//=6
    a=min(a,b)
print(a)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N=int(input())
inf=float("inf")

X=[inf]*(N+1)
X[0]=0

for x in range(1,N+1):
    X[x]=X[x-1]+1

    b=6
    while x>=b:
        X[x]=min(X[x],X[x-b]+1)
        b*=6

    c=9
    while x>=c:
        X[x]=min(X[x],X[x-c]+1)
        c*=9

print(X[-1])

Submission status: Accepted

Solution code:
n = int(input())
A = [1]+[pow(6,i) for i in range(1,7)]+[pow(9,i) for i in range(1,6)]
D = [0]+[-1]*n
for i in range(1,n+1):
    D[i] = D[i-1]+1
    for j in range(1,7):
        if pow(6,j)>i: break
        D[i] = min(D[i], D[i-pow(6,j)]+1)
    for j in range(1,6):
        if pow(9,j)>i: break
        D[i] = min(D[i], D[i-pow(9,j)]+1)
print(D[-1])

Submission status: Accepted

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

i = 6
while i <= N:
    divider.append(i)
    i *= 6

i = 9
while i <= N:
    divider.append(i)
    i *= 9


for x in divider:
    dp[x] = 1

for i in range(1, N + 1):
    if dp[i] == 0:
        poss = []
        for x in divider:
            if i - x >= 0:
                poss.append(dp[i - x] + 1)
        dp[i] = min(poss)

print(dp[N])

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
def main():
    n = int(input())
    nums = []
    n6 = 6
    while n6 <= n:
        nums.append(n6)
        n6 = n6 * 6
    n9 = 9
    while n9 <= n:
        nums.append(n9)
        n9 = n9 * 9
    nums.sort(reverse=True)
    dp = [i for i in range(2 * n + 1)]
    for num in nums:
        for j1 in range(n + 1):
            dp[j1+num] = min(dp[j1+num], dp[j1] + 1)
    print(dp[n])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())

ans = 100000
for i in range(0,N+1,1):#i円6で払うj円9で払う
    j = N - i

    icount = 0
    while i!=0:
        icount += (i%6)
        i=i//6

    jcount = 0
    while j!=0:
        jcount += (j%9)
        j=j//9

    ans = min(icount+jcount,ans)

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

n = int(input())

dp = [0]*(n+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-1]+1, dp[i-b]+1)
  else:
    dp[i] = min(dp[i-1]+1, dp[i-b]+1, dp[i-c]+1)
print(dp[-1])

Submission status: Accepted

Solution code:
N = int(input())

a = []

# 1
a.append(1)

# 6**n
b = 6
while b <= N:
    a.append(b)
    b *= 6

# 9**n
b = 9
while b <= N:
    a.append(b)
    b *= 9

a.sort()

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

Submission status: Accepted

Solution code:
import sys


def resolve():
    readline = sys.stdin.readline

    def func(n: int, a: int):
        res = 0
        while n > 0:
            res += n % a
            n = int(n / a)
        return res

    N = int(readline())

    res = N
    for i in range(N + 1):
        tmp = func(i, 6) + func(N - i, 9)
        res = min(res, tmp)
    print(res)

resolve()

Submission status: Accepted

Solution code:
n=int(input())
dp=list(range(n+1))
dp[0]=0
a=[]
b=[]
i=1
while True:
  if 6**i>n:break
  a.append(6**i)
  i+=1
i=1
while True:
  if 9**i>n:break
  b.append(9**i)
  i+=1
for i in a:
  for j in range(i,n+1):
    dp[j]=min(dp[j],dp[j-i]+1)
for i in b:
  for j in range(i,n+1):
    dp[j]=min(dp[j],dp[j-i]+1)
print(dp[n])

Submission status: Accepted

Solution code:
def main():
    from collections import deque
    N = int(input())

    amounts = [1]
    mul6 = 6
    while mul6 <= N:
        amounts.append(mul6)
        mul6 *= 6
    mul9 = 9
    while mul9 <= N:
        amounts.append(mul9)
        mul9 *= 9

    distances = [-1]*(N+1)
    distances[0] = 0

    targets = deque([0])
    while targets:
        t = targets.popleft()
        d = distances[t]
        for a in amounts:
            if t + a <= N and distances[t+a] == -1:
                distances[t+a] = d+1
                targets.append(t+a)
    print(distances[N])




main()

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    amounts = [1]
    lim = 10**6
    mul6 = 6
    while mul6 < lim:
        amounts.append(mul6)
        mul6 *= 6
    mul9 = 9
    while mul9 < lim:
        amounts.append(mul9)
        mul9 *= 9
    
    dp = [lim] * (N+1)
    dp[0] = 0
    for i in range(N):
        for a in amounts:
            if i+a <= N:
                dp[i+a] = min(dp[i+a],dp[i]+1)
    print(dp[N])

    



main()

Submission status: Accepted

Solution code:
from collections import deque
def main():
    N = int(input())
    divs = [59049, 46656, 7776, 6561, 1296, 729, 216, 81, 36, 9, 6, 1]
    dp = [0]*(10**6+1)
    def f(x):
        if x == 0:
            return 0
        if x < 0:
            return 10**6
        if dp[x]:
            return dp[x]
        else:
            res = 10**6
            for d in divs:
                res = min(res,f(x-d)+1)
            dp[x] = res
            return res
            

    print(f(N))
main()

Submission status: Accepted

Solution code:
N = int(input())

def calc_dp(n):
    initial = 10**7
    dp=[initial for _ in range(100100)]#dp用の配列はすこし大きめに作る
    dp[0] = 0

    for i in range(100001):
        count = 0
        while 6**count <= n:
            power_six = 6**count
            count += 1
            if i - power_six >= 0:
                dp[i] = min(dp[i],1 + dp[i-power_six])
                
        count = 1
        while 9**count <= n:
            power_nine = 9**count
            count += 1
            if i - power_nine >= 0:
                dp[i] = min(dp[i],1 + dp[i-power_nine])

    return dp[n]

print(calc_dp(N))

Submission status: Accepted

Solution code:
N = int(input())
ans = float('inf')
for i in range(N+1):
    j = i
    count = 0
    t=N-i
    while j > 0:
        count += j%6
        j=j//6
    while t > 0:
        count += t%9
        t=t//9
    ans = min(ans,count)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

dp = [10 ** 9] * 100001
dp[0] = 1

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

print(dp[N] - 1)

Submission status: Accepted

Solution code:
N=int(input())

coin=[1]

for _ in [6,9]:
    __=_
    while __ <= N:
        coin.append(__)
        __=__*_
coin.sort()

dp=[[0]*(N+1) for c in coin]

for n in range(N):
    n += 1
    for c_idx,c in enumerate(coin):
        
        if c_idx==0:#c=1のとき
            dp[c_idx][n] = dp[c_idx][n-c]+1
            
        elif n-c >= 0:
            dp[c_idx][n] = min(dp[c_idx-1][n],dp[c_idx][n-c]+1)
            
        else:
            dp[c_idx][n] = dp[c_idx-1][n]

ans=10**10
for c in range(len(coin)):
    if ans > dp[c][-1]:
        ans=dp[c][-1]
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
# n < 100000
res = n

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

print(res)

Submission status: Accepted

Solution code:
########10進法からn進法への変換関数部分##############
def Format(X, n):
    X_dumy = X
    out = ''
    while X_dumy>0:
        out = str(X_dumy%n)+out
        X_dumy = int(X_dumy/n)
    return out
############################

n=int(input())
# 6進表現と9進表現を全探索
ans=n
for i in range(n+1):
  j=n-i
  i,j=Format(i,6),Format(j,9)
  t=0
  for s in i:
    t+=int(s)
  for s in j:
    t+=int(s)
  ans=min(ans,t)
print(ans)

Submission status: Accepted

Solution code:
import bisect
N = int(input())

six = []
nine = []

now = 6
while now < 100001:
  six.append(now)
  now *= 6
  
now = 9
while now < 100001:
  nine.append(now)
  now *= 9  

#print(six, nine)  
#[6, 36, 216, 1296, 7776, 46656] [9, 81, 729, 6561, 59049]

def coin(n):
  if n < 6:
    return n
  else:
    index_six = bisect.bisect_right(six, n)
    index_nine = bisect.bisect_right(nine, n)
    #print(n, index_six, index_nine, count)
    #print(n, n - six[index_six - 1], n - nine[index_nine - 1])
    if n - six[index_six - 1] >= 0:
      alpha = coin(n - six[index_six - 1]) + 1
    else:
      alpha = 10 ** 7
    if n - nine[index_nine - 1] >= 0:
      beta = coin(n - nine[index_nine - 1]) + 1
    else:
      beta = 10 ** 7
    return min(alpha, beta)
  
print(coin(N))

Submission status: Accepted

Solution code:
def main():
  N=int(input())
  values=[]
  val=6
  while val<=N:
    values.append(val)
    val*=6
  
  val=9
  while val<=N:
    values.append(val)
    val*=9
  values.append(1)
  values.sort()
  dp=[N]*(N+1)
  dp[0]=0
  for i in range(N):
    for v in values:
      if i+v>N:break
      dp[i+v]=min(dp[i]+1,dp[i+v])
  print(dp[N])
  pass
if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
N = 10**6
n = int(input())

nine = [1, 9]
while True:
    t = nine[-1] * 9
    if t > N:
        break
    nine.append(t)

six = [1, 6]
while True:
    t = six[-1] * 6
    if t > N:
        break
    six.append(t)

dp = [N]*(n+1)
dp[0] = 0
for i in range(1, n+1):
    # dp[i] = min(dp[i], dp[i-1]+1)
    for j in nine:
        if i-j < 0:
            break
        dp[i] = min(dp[i], dp[i-j]+1)
    for j in six:
        if i-j < 0:
            break
        dp[i] = min(dp[i], dp[i-j]+1)

print(dp[n])

Submission status: Accepted

Solution code:
N = int(input())
INF = 10**18
dp = [INF] * (N+1)
dp[0] = 0

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

Submission status: Accepted

Solution code:
import sys 
sys.setrecursionlimit(2147483647)

INF = float("inf")

memo = [float("inf")]*100005

def rec(n):
    if n==0:
        return 0
    if memo[n]!=float("inf"):
        return memo[n]
    res = float("inf")
    val = 1
    while val<=n:
        res = min(res,rec(n-val)+1)
        val*=6
    
    val = 1
    while val<=n:
        res = min(res,rec(n-val)+1)
        val*=9
    memo[n]=res
    return memo[n]

dp = [INF]*100005

def morau_dp():
    #min(dp[n-x]+1....)
    N = int(input())
    dp[0]=0
    for i in range(1,N+1):
        val = 1
        while val<=N:
            dp[i]=min(dp[i],dp[i-val]+1)
            val*=6
        
        val = 1
        while val<=N:
            dp[i] = min(dp[i],dp[i-val]+1)
            val*=9

    print(dp[N])


def kubaru_dp():
    #dp[i]+1, dp[i]+6, dp[i]+9....
    N = int(input())
    dp[0]=0
    for i in range(0,N):#配るDPの場合，ループは初期値０から直前N-1まで（貰うDPと1スライドする）
        val = 1
        while (i+val)<=N:
            dp[i+val] = min(dp[i+val],dp[i]+1)
            val*=6

        val = 1
        while (i+val)<=N:
            dp[i+val] = min(dp[i+val],dp[i]+1)
            val*=9
    print(dp[N])


if __name__ == "__main__":
    # N = int(input())
    # print(rec(N))
    # morau_dp()
    kubaru_dp()

Submission status: Accepted

Solution code:
import sys 
sys.setrecursionlimit(2147483647)

INF = float("inf")

memo = [float("inf")]*100005

def rec(n):
    if n==0:
        return 0
    if memo[n]!=float("inf"):
        return memo[n]
    res = float("inf")
    val = 1
    while val<=n:
        res = min(res,rec(n-val)+1)
        val*=6
    
    val = 1
    while val<=n:
        res = min(res,rec(n-val)+1)
        val*=9
    memo[n]=res
    return memo[n]

dp = [INF]*100005

def morau_dp():
    #min(dp[n-x]+1....)
    N = int(input())
    dp[0]=0
    for i in range(1,N+1):
        val = 1
        while val<=N:
            dp[i]=min(dp[i],dp[i-val]+1)
            val*=6
        
        val = 1
        while val<=N:
            dp[i] = min(dp[i],dp[i-val]+1)
            val*=9

    print(dp[N])


if __name__ == "__main__":
    # N = int(input())
    # print(rec(N))
    morau_dp()

Submission status: Accepted

Solution code:
import sys 
sys.setrecursionlimit(2147483647)

memo = [float("inf")]*100005

def rec(n):
    if n==0:
        return 0
    if memo[n]!=float("inf"):
        return memo[n]
    res = float("inf")
    val = 1
    while val<=n:
        res = min(res,rec(n-val)+1)
        val*=6
    
    val = 1
    while val<=n:
        res = min(res,rec(n-val)+1)
        val*=9
    memo[n]=res
    return memo[n]

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

Submission status: Accepted

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


#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

def main():
	n=II()
	dp=list(range(10**5+1))
	x=[]
	a=6
	while a<10**5:
		x.append(a)
		a*=6
	a=9
	while a<10**5:
		x.append(a)
		a*=9
	x.sort()
	#print(x)

	#print(dp)

	for i in x:
		for j in range(i,10**5+1):
			dp[j]=min(dp[j],dp[j-i]+1)
	print(dp[n])



if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
n = int(input())
ans = pow(10, 10)

for i in range(n+1):
    cnt = 0
    j = n - i
    while i > 0:
        cnt += i % 6
        i //= 6

    while j > 0:
        cnt += j % 9
        j //= 9

    ans = min(ans, cnt)

print(ans)

Submission status: Accepted

Solution code:
def main():
  N=int(input())
  values=[]
  val=6
  while val<=N:
    values.append(val)
    val*=6
  
  val=9
  while val<=N:
    values.append(val)
    val*=9
  
  values.sort(reverse=True)
  dp=[N]*(N+1)
  dp[0]=0
  for value in values:
    for i in range(0,N-value+1):
      if dp[i] != N:
        dp[i+value]=min(dp[i]+1,dp[i+value])
        #print(i,value,dp[i+value])
  #print(dp)
  ans=10**10
  for index,item in enumerate(dp):
    ans=min(ans,item+N-index)
  print(ans)
  pass
if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

def main():
    N = int(input())
    money = [1]
    for i in range(10):
        money.append(money[-1]*6)
    money.append(9)
    for i in range(9):
        money.append(money[-1]*9)
    
    dp = [INF] * (1 + N)
    dp[0] = 0
    for m in money:
        for j in range(m,N + 1):
            dp[j] = min(dp[j],dp[j - m] + 1)
    ans = dp[-1]
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
lst=[1, 6, 9, 36, 81, 216, 729, 1296, 6561, 7776, 46656, 59049]

dp=[None]*(n+1) #リストの番号と同じお金を払うのに必要な最短手数
dp[0]=0
for i in lst:
    if i<=n:
        dp[i]=1

for i in range(2,n+1):
    kouho=[]
    for j in lst:
        if i-j>=0:
            kouho.append(dp[i-j]+1)
    dp[i]=min(kouho)

print(dp[-1])

Submission status: Accepted

Solution code:
import sys
INFTY=sys.maxsize

def readinput():
    n=int(input())
    return n

def main(n):
    dp=[INFTY]*(n+1)
    dp[0]=0
    dp[1]=1
    for i in range(2,n+1):
        dp[i]=min(dp[i],dp[i-1]+1)  # 1円
        k=1
        while(i-6**k>=0):
            dp[i]=min(dp[i],dp[i-6**k]+1)
            k+=1
        k=1
        while(i-9**k>=0):
            dp[i]=min(dp[i],dp[i-9**k]+1)
            k+=1
    return dp[n]

if __name__=='__main__':
    n=readinput()
    ans=main(n)
    print(ans)

Submission status: Accepted

Solution code:
N = int(input())

def to_n(X, n):
    if (int(X / n)):  return to_n(int(X / n), n) + str(X % n)
    return str(X % n)

ans = 10 ** 9 + 7
for i in range(N + 1):
    N6 = to_n(N - i, 6)
    N9 = to_n(i, 9)
    res = 0
    for j in N6:  res += int(j)
    for j in N9:  res += int(j)
    ans = min(res, ans)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
c = [1]
temp = 6
while(temp <= N):
    c.append(temp)
    temp *= 6
temp = 9
while(temp <= N):
    c.append(temp)
    temp *= 9
m = len(c)

dp = [10 ** 9 + 7 for _ in range(N + 1)]
dp[0] = 0
for i in range(m):
    for j in range(1, N + 1):
        if j - c[i] >= 0:
            dp[j] = min(dp[j], dp[j - c[i]] + 1)
print(dp[N])

Submission status: Accepted

Solution code:
N = int(input())
m = 10000000
def judge_1(t):
  c = 0
  while t>0:
    c += t%6
    t = t//6  
  return c
def judge_2(t):
  c = 0
  while t>0:
    c += t%9
    t = t//9  
  return c
for i in range(N+1):
  m = min(m, judge_1(i)+judge_2(N-i))
print(m)

Submission status: Accepted

Solution code:
N = int(input())
dp = [None]*(N+1)
a = 1
while a <= N:
    dp[a] = 1
    a *= 6
a = 1
while a <= N:
    dp[a] = 1
    a *= 9

def f(n):
    if dp[n]:
        return dp[n]
    a = 6
    while a <= n:
        a *= 6
    a //= 6
    b = 9
    while b <= n:
        b *= 9
    b //= 9
    ans = min([f(n-a), f(n-b)])+1
    dp[n] = ans
    return ans
print(f(N))

Submission status: Accepted

Solution code:
n=int(input())
l6=[6**i for i in range(7)]
l9=[9**i for i in range(1,6)]
m=l6+l9
m.sort()
inf=float("inf")
dp=[inf]*(10**5+1)
dp[0]=0
dp[1]=1
for i in range(1,n+1):
  for mi in m:
    if i-mi>=0:
      dp[i]=min(dp[i-mi]+1,dp[i])
print(dp[n])

Submission status: Accepted

Solution code:
import functools

import sys
import functools

sys.setrecursionlimit(100000)


def f(r, i):
    # return (r ** (i + 1) - r) / (r - 1)
    return r ** i


@functools.lru_cache(maxsize=None)
def solve(N, size):
    if size == -1:
        return N
    b = C[size]
    if N - b >= 0:
        return min(solve(N - b, size) + 1, solve(N, size - 1))
    else:
        return solve(N, size - 1)


if __name__ == "__main__":
    max_N = 10_0000
    N = int(input())

    A = [f(6, i) for i in range(1, 7) if f(6, i) <= N]
    B = [f(9, i) for i in range(1, 7) if f(9, i) <= N]
    C = A + B
    C.sort(reverse=True)
    print(solve(N, len(C) - 1))

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    ans = N
    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
        ans = min(ans, cc)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    dp = [-1]*(N + 1)
    dp[0] = 0
    multiples = [1]
    n = 9
    while n <= N:
        multiples.append(n)
        n *= 9
    n = 6
    while n <= N:
        multiples.append(n)
        n *= 6
    multiples.sort(reverse=True)
    # print(multiples)
    for ratio in reversed(multiples):
        for i in range(N + 1):
            c = dp[i]
            if c == - 1:
                continue
            if i + ratio > N:
                continue
            if dp[i + ratio] == -1 or dp[i + ratio] > c + 1:
                dp[i + ratio] = c + 1
    # print(dp)
    print(dp[N])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())

l = [1]
i = 1
while 6 ** i <= 100000:
    l.append(6 ** i)
    i += 1
i = 1
while 9 ** i <= 100000:
    l.append(9 ** i)
    i += 1
l.sort()

dp = [float('inf')] * (n+1)
dp[0] = 0
for i in range(1, n+1):
    for v in l:
        if v > i:
            break
        dp[i] = min(dp[i], dp[i-v] + 1)

print(dp[n])

Submission status: Accepted

Solution code:
N = int(input())

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

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

print(dp[N])

Submission status: Accepted

Solution code:
N = int(input())
dp = [float('inf')]*(N+1)
dp[0] = 0#i円を引き出す最小の操作回数
for i in range(1,N+1):
    dp[i] = 1 + dp[i-1]
    j,k = 1,1
    while pow(6,j)<=i:
        dp[i] = min(dp[i],1+dp[i-pow(6,j)])
        j += 1
    while pow(9,k)<=i:
        dp[i] = min(dp[i],1+dp[i-pow(9,k)])
        k += 1
print(dp[-1])

Submission status: Accepted

Solution code:
from bisect import bisect_right

n = int(input())

l = [1]
i = 1
while 6 ** i <= 100000:
    l.append(6 ** i)
    i += 1
i = 1
while 9 ** i <= 100000:
    l.append(9 ** i)
    i += 1
l.sort()

dp = [float('inf')] * (n+1)
dp[0] = 0
for i in range(1, n+1):
    for v in l:
        if v > i:
            break
        dp[i] = min(dp[i], dp[i-v] + 1)

print(dp[n])

Submission status: Accepted

Solution code:
n = int(input())

cnt = [float("inf")] * (n + 1)
cnt[0] = 0

sixes = [pow(6, num) for num in range(1, 10)]
nines = [pow(9, num) for num in range(1, 10)]

for six in sixes:
    for i in range(n + 1):
        if six + i <= n and cnt[i] != float("inf"):
            cnt[six + i] = min(cnt[six + i], cnt[i] + 1)

for nine in nines:
    for i in range(n + 1):
        if nine + i <= n and cnt[i] != float("inf"):
            cnt[nine + i] = min(cnt[nine + i], cnt[i] + 1)

for i in range(n):
    cnt[i + 1] = min(cnt[i + 1], cnt[i] + 1)

print(cnt[n])

Submission status: Accepted

Solution code:
n = int(input())
dp = [float("Inf")]*(n+1)
for i in range(min(6, n+1)):
    dp[i] = i
for i in range(n):
    for j in range(1,n//6+1):
        if i + 6**j > n:
            break
        dp[i+6**j] = min(dp[i+6**j], dp[i] + 1)
    for j in range(1,n//9+1):
        if i + 9**j > n:
            break
        dp[i+9**j] = min(dp[i+9**j], dp[i] + 1)
print(dp[-1])

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
from heapq import heappush, heappop
def input(): return sys.stdin.readline().strip()


def main():
    """
    ６のべき乗しか引き出せない部分問題を考える。
    このとき最適な支払方法は、当然大きい金額を序盤に一気に下ろすこと。
    なのでN円をi円と(N - i)円に分けて片方を6のべき、もう片方を９のべきで支払って
    その合計を見ればよい。

    それぞれの支払い方はすなわち６進数（９進数）展開することに他ならないので
    １円から支払う方法を考えた方が早い。
    """
    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)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def Base(X, n):
    if (int(X/n)):
        return Base(int(X/n), n)+str(X%n)
    return str(X%n)

def main():
    N = ii()
    m = 10**100
    for i in range(N+1):
        a = sum(map(int, Base(i, 6)))
        b = sum(map(int, Base(N-i, 9)))
        m = min(m, a+b)
    print(m)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
dp = [float("Inf")]*(n+1)
dp[0] = 0
for i in range(n):
    for j in range(1,6):
        if i + j > n:
            break
        dp[i+j] = min(dp[i+j], dp[i] + j)
    for j in range(1,n//6+1):
        if i + 6**j > n:
            break
        dp[i+6**j] = min(dp[i+6**j], dp[i] + 1)
    for j in range(1,n//9+1):
        if i + 9**j > n:
            break
        dp[i+9**j] = min(dp[i+9**j], dp[i] + 1)
print(dp[-1])

Submission status: Accepted

Solution code:
n = int(input())
dp = [float("Inf")]*(n+1)
dp[0] = 0
for i in range(n):
    if dp[i] == float("Inf"):
        pass
    else:
        for j in range(1,n//6+1):
            if i + 6**j > n:
                break
            dp[i+6**j] = min(dp[i+6**j], dp[i] + 1)
        for j in range(1,n//9+1):
            if i + 9**j > n:
                break
            dp[i+9**j] = min(dp[i+9**j], dp[i] + 1)
ans = n
for i in range(max(0, n-5), n+1):
    ans = min(ans, dp[i]+n-i)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
inf = float("inf")
dp = [inf for _ in range(N+1)]
l6 = 7
l9 = 6
dp[0] = 0

# DP
for i in range(1, N+1):
    # 1円を引き出す
    dp[i] = min(dp[i], dp[i-1] + 1)
    
    # 6の累乗円を引き出す
    for j in range(1, l6):
        if i - 6**j >= 0:
            dp[i] = min(dp[i], dp[i - 6**j] + 1)
        
    # 9の累乗円を引き出す
    for j in range(1, l9):
        if i - 9**j >= 0:
            dp[i] = min(dp[i], dp[i - 9**j] + 1)

print(dp[N])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int):
    from itertools import takewhile, count
    dp = list(range(N+1))
    for n in (6, 9):
        for m in takewhile(lambda x: x<=N, (n**e for e in count(1))):
            for i in range(m, N+1):
                dp[i] = min(dp[i], dp[i-m]+1)
    return dp[N]


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    print(solve(N))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()