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:
def powerset(n, lessequal):
    retval = []
    power = n
    while power <= lessequal:
        retval += [power]
        power *= n
    return retval


def main():
    N = int(input())
    dp = [0] * (N + 1)
    for i in range(1, N + 1):
        withdraw = [1] + powerset(6, i) + powerset(9, i)
        dp[i] = min([dp[i - x] for x in withdraw]) + 1
    print(dp[N])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
num = [1, 6, 6**2, 6**3, 6**4, 6**5, 6**6, 9, 9**2, 9**3, 9**4, 9**5]
answer = [0]*(n+1)
for i in range(1, n+1):
    answer[i] = min([answer[i-l]+1 for l in num if i-l>=0])
print(answer[n])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
table = [0]+[1]+[10**10 for i in range(10**6)]
six = [6 ** i for i in range(1,8)]
nine = [9 ** i for i in range(1,7)]
for i in range(10**5):
    table[i+1] = min(table[i+1],table[i]+1)
    for x in six:
        table[i + x] = min(table[i + x], table[i]+1 )
    for y in nine:
        table[i+y] = min(table[i+y], table[i]+1)
print(table[int(input())])

Submission status: Accepted

Solution code:
n = int(input())

dp = [10**10] * (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
        
for i in range(1,n+1):
    power = 1
    while power <= i:
        dp[i] = min(dp[i], dp[i-power] + 1)
        power *= 9
        
print(dp[-1])

Submission status: Accepted

Solution code:
nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

N = n()

min_count = 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

    if count < min_count:
        min_count = count
print(min_count)

Submission status: Accepted

Solution code:
N=int(input())
list1=[0]*(N+1)
for i in range(1,N+1):
	list2=[list1[i-1]]
	l=list2.append
	if i>=6:
		l(list1[i-6])
		if i>=9:
			l(list1[i-9])
			if i>=36:
				l(list1[i-36])
				if i>=81:
					l(list1[i-81])
					if i>=216:
						l(list1[i-216])
						if i>=729:
							l(list1[i-729])
							if i>=1296:
								l(list1[i-1296])
								if i>=6561:
									l(list1[i-6561])
									if i>=7776:
										l(list1[i-7776])
										if i>=46656:
											l(list1[i-46656])
											if i>=59049:
												l(list1[i-59049])
	list1[i]=min(list2)+1
print(list1[N])

Submission status: Accepted

Solution code:
N = int(input())
dp = [-1] * (N + 1)
dp[0] = 0
l = [1] + [6**i for i in range(1,7)] + [9**i for i in range(1,6)]

for n in range(1, N+1):
    tmp = float('inf')
    for j in l:
        if n-j >= 0:
            tmp = min(tmp, 1 + dp[n-j])
    dp[n] = tmp
print(dp[-1])

Submission status: Accepted

Solution code:

N = int(input())

lis = [0]

for i in range(N):

    i += 1

    now = lis[ i - 1 ] + 1

    cnt = 1
    while True:

        if i - ( 6 ** cnt )  >= 0:
            now = min(now, lis[i - ( 6 ** cnt )] + 1)
            cnt += 1

        else:
            break

    cnt = 1
    while True:

        if i - ( 9 ** cnt )  >= 0:
            now = min(now, lis[i - ( 9 ** cnt )] + 1)
            cnt += 1

        else:
            break

    #print (i,"は",now)
    lis.append(now)

print (lis[N])

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())

coin = [6**n for n in range(10) if 6**n <= N]
coin += [9**n for n in range(10) if 9**n <= N]

dp = np.zeros(N+1, dtype=np.int32)
dp += 10**9
dp[0] = 0

for c in coin:
  # それぞれの額は9回以下なので
  for _ in range(9):
    dp[c:] = np.minimum(dp[:-c] + 1, dp[c:])

answer = dp[-1]
print(answer)

Submission status: Accepted

Solution code:
N = int(input())
INF = 10**18

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

print(dp[N])

Submission status: Accepted

Solution code:
N = int(input())

A = []
for i in range(1, N+1):
    if 6**i > N:
        break
    else:
        A.append(6**i)
    if 9**i <= N:
        A.append(9**i)
A.sort(reverse=True)

money = [i for i in range(N+1)]
for i in A:
    for j in range(i,N+1):
        money[j] = min(money[j], money[j-i]+1)
print(money[N])

Submission status: Accepted

Solution code:
n=int(input())

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

Submission status: Accepted

Solution code:
def f(N,x):
    ret=0
    while N>=x:
        ret+=N%x
        N=N//x
    return(ret+N)

N=int(input())
ans=[]
for i in range(N+1):
    ans.append(f(i,6)+f(N-i,9))
print(min(ans))

Submission status: Accepted

Solution code:
#もらうDP
N = int(input())
dp=[float('inf')]*110000
dp[0] = 0
for n in range(1,N+1):
    pow6 = 1
    pow9 = 1
    while pow6 <= n:
        dp[n] = min(dp[n],dp[n-pow6]+1)
        pow6 *= 6
    while pow9 <= n:
        dp[n] = min(dp[n],dp[n-pow9]+1)
        pow9 *= 9
print(dp[N])

Submission status: Accepted

Solution code:
from itertools import*
from math import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)
"""
#memo化再帰
memo = [-1]*(110000)
def rec(n):
    if n==0:
        return 0
    if memo[n] != -1:
        return memo[n]
    res = n
    pow6,pow9 = 1,1
    while pow6 <=n:
        res = min(res,rec(n-pow6)+1)
        pow6 *= 6
    while pow9 <= n:
        res = min(res,rec(n-pow9)+1)
        pow9 *= 9
    memo[n] = res
    return memo[n]
N = int(input())
print(rec(N))
"""
"""
#もらうDP
N = int(input())
dp=[inf]*110000
dp[0] = 0
for n in range(1,N+1):
    pow6,pow9 = 1,1
    while pow6<=n:
        dp[n] = min(dp[n],dp[n-pow6]+1)
        pow6 *= 6
    while pow9 <= n:
        dp[n] = min(dp[n],dp[n-pow9]+1)
        pow9 *= 9
print(dp[N])
"""
#配るDP
N = int(input())
dp=[inf]*(110000)
for i in range(110000):
    dp[i] = N 
dp[0]=0
for n in range(N):
    pow6,pow9 = 1,1
    while n+pow6<=N:
        dp[n+pow6] = min(dp[n+pow6],dp[n]+1)
        pow6 *= 6
    while n+pow9 <=N:
        dp[n+pow9] = min(dp[n+pow9],dp[n]+1)
        pow9 *= 9
print(dp[N])

Submission status: Accepted

Solution code:
from itertools import*
from math import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

N = int(input())
dp=[inf]*110000
dp[0] = 0
for n in range(1,N+1):
    pow6,pow9 = 1,1
    while pow6<=n:
        dp[n] = min(dp[n],dp[n-pow6]+1)
        pow6 *= 6
    while pow9 <= n:
        dp[n] = min(dp[n],dp[n-pow9]+1)
        pow9 *= 9
print(dp[N])

Submission status: Accepted

Solution code:
from itertools import*
from math import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

memo = [-1]*(110000)
def rec(n):
    if n==0:
        return 0
    if memo[n] != -1:
        return memo[n]
    res = n
    pow6,pow9 = 1,1
    while pow6 <=n:
        res = min(res,rec(n-pow6)+1)
        pow6 *= 6
    while pow9 <= n:
        res = min(res,rec(n-pow9)+1)
        pow9 *= 9
    memo[n] = res
    return memo[n]

N = int(input())
print(rec(N))

Submission status: Accepted

Solution code:
#https://qiita.com/k-tokitoh/items/8fc1a2de8b110a043ea2
#模写、ｄｐ
N = int(input())
dp = [110000]*(N+1)
dp[0] = 0
for i in range(1, N + 1):
    dp[i] = dp[i-1]+1
    p6 = 1
    p9 = 1
    while i >= 6 ** p6:
        dp[i] = min(1 + dp[i - 6 ** p6],dp[i])
        p6 += 1
    while i >= 9 ** p9:
        dp[i] = min(1 + dp[i - 9 ** p9],dp[i])
        p9 += 1


print(dp[N])

Submission status: Accepted

Solution code:
#https://qiita.com/k-tokitoh/items/8fc1a2de8b110a043ea2
#模写、ｄｐ
N = int(input())
dp = [0]
for i in range(1, N + 1):
    Q = []
    Q.append(1 + dp[i - 1])
    
    p6 = 1
    p9 = 1
    while i >= 6 ** p6:
        Q.append(1 + dp[i - 6 ** p6])
        p6 += 1
    while i >= 9 ** p9:
        Q.append(1 + dp[i - 9 ** p9])
        p9 += 1
    dp.append(min(Q))


print(dp[N])

Submission status: Accepted

Solution code:
n = int(input())
c = [1]
for i in range(6):
    c.append(6**(i+1))
for i in range(5):
    c.append(9**(i+1))
INF = float("inf")
 
dp = [INF]*(n+1)
dp[0] = 0
 
for i in range(len(c)):
    for j in range(n+1):
        if j - c[i] < 0:
            continue
        else:
            dp[j] = min(dp[j], dp[j - c[i]] + 1)
 
print(dp[n])

Submission status: Accepted

Solution code:
n = int(input())
c = [1]
for i in range(6):
    c.append(6**(i+1))
for i in range(5):
    c.append(9**(i+1))
INF = float("inf")

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

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

print(dp[n])

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7

def LI(): return list(map(int,input().split()))
def I(): return int(input())
def LS(): return input().split()
def S(): return input()

def main():
  l=[inf]*100001
  l[0]=0

  l2=[1]
  for i in range(1,10):
    a=pow(6,i)
    b=pow(9,i)
    if a<=100000:
      l2.append(a)
    if b<=100000:
      l2.append(b)
  l2.sort()

  n=I()

  for i in range(1,n+1):
    for x in l2:
      if i-x>=0:
        l[i]=min(l[i],l[i-x]+1)

  return l[n]

print(main())

Submission status: Accepted

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

dp[0] = 0
dp[1] = 1

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

Submission status: Accepted

Solution code:
import sys

from collections import deque  # 双方向キュー
from collections import defaultdict  # 初期化済み辞書
from heapq import heapify, heappush, heappop, heappushpop  # プライオリティキュー
from bisect import bisect_left, bisect_right  # 二分探索

#import numpy as np  # 1.8.2
#import scipy  # 0.13.3

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N = i2n()
    total = 1e+6
    for i in range(N+1):
        a = i
        b = N - i
        c = 0
        while a > 0:
            d = a % 6
            c += d
            a = int(a / 6)
        while b > 0:
            d = b % 9
            c += d
            b = int(b / 9)
        if total > c:
            total = c
    print(total)

main()

Submission status: Accepted

Solution code:
n=int(input())
from copy import*
ans=[]
for i in range(n+1): #10000円を6円で払う分と9円で払う分に分ける
    count=0
    money6=i
    money9=n-i
    while money6:
        count+=money6%6
        money6//=6
    while money9:
        count+=money9%9
        money9//=9
    ans.append(count)
print(min(ans))

Submission status: Accepted

Solution code:
import sys

from collections import deque
# q = deque(); q.append(x); q.appendleft(x); q.pop() -> x; q.popleft() -> x
from collections import defaultdict
# d = defaultdict(lambda: []); d[key] -> []
import heapq
# hq = []; heapq.heappush(hq, x); heapq.heappop(hq) -> x; heapq.heappushpop(hq, x) -> x
import bisect
# i = bisect.bisect_left([1,2,3,4], 1.5); i = bisect.bisect_right([4,3,2,1], 1.5)

#import numpy as np
#from scipy.misc import comb

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

# 個数制限なしナップサック
def main():
    N = i2n()
    coins = [1]
    d = 6
    while d <= N:
        coins.append(d)
        d *= 6
    d = 9
    while d <= N:
        coins.append(d)
        d *= 9
    # アイテム = (重さ=金額, 価値=枚数) = (1, 1), (6, 1), ..., (9, 1), ...
    # DP[アイテムID][重さ] = 価値
    # DP[アイテムID][金額] = 枚数
    # 価値の最大化／枚数の最小化
    items = [(c, 1) for c in coins]
    itemlen = len(items)
    dp = [[int(1e+6)] * (N+1) for _ in range(itemlen+1)]
    for i in range(itemlen+1):
        dp[i][0] = 0
    # dp[i+1][w] = max(dp[i+1][w - item[0]] + item[1], dp[i][w])
    for item_id, (coin, coin_n) in enumerate(items):
        for n in range(1, N+1):
            if n - coin >= 0:
                dp[item_id+1][n] = min(dp[item_id][n], dp[item_id+1][n-coin] + coin_n)
            else:
                dp[item_id+1][n] = dp[item_id][n]
    #print(dp)
    print(dp[itemlen][N])


main()

Submission status: Accepted

Solution code:
n = int(input())
dp = [1e9 for i in range(100001)]
dp[0] = 0
ans = n
yen = set()
for i in range(7):
  yen.add(6**i)
  dp[6**i] = 1
for i in range(6):
  yen.add(9**i)
  dp[9**i] = 1
for i in range(1, n+1):
  for e in yen:
    if i+e<=100000:
      dp[i+e] = min(dp[i+e], dp[i]+1)
print(dp[n])

Submission status: Accepted

Solution code:
N = int(input())

dp = [200000] * 200000
dp[0] = 0

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

print(dp[N])

Submission status: Accepted

Solution code:
def ninebeki(n):
    cnt=0
    while n>=9**cnt:
        cnt+=1
    return cnt-1
def sixbeki(n):
    cnt=0
    while n>=6**cnt:
        cnt+=1
    return cnt-1

def resolve():
    n=int(input())
    cnt=0
    q=ninebeki(n)
    r=sixbeki(n)
    l=[9**i for i in range(1,q+1)]
    l+=[6**i for i in range(1,r+1)]
    l.append(1)
    l.sort()
    d=[n for i in range(n+1)]
    d[0]=0
    for c in l:
        for i in range(c,n+1):
            d[i]=min(d[i],d[i-c]+1)
    print(d[n])
resolve()

Submission status: Accepted

Solution code:
import sys

from collections import deque
# q = deque(); q.append(x); q.appendleft(x); q.pop() -> x; q.popleft() -> x
from collections import defaultdict
# d = defaultdict(lambda: []); d[key] -> []
import heapq
# hq = []; heapq.heappush(hq, x); heapq.heappop(hq) -> x; heapq.heappushpop(hq, x) -> x
import bisect
# i = bisect.bisect_left([1,2,3,4], 1.5); i = bisect.bisect_right([4,3,2,1], 1.5)

#import numpy as np
#from scipy.misc import comb

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

# BFS方法
def main():
    N = i2n()
    coins = [1]
    d = 6
    while d <= N:
        coins.append(d)
        d *= 6
    d = 9
    while d <= N:
        coins.append(d)
        d *= 9
    q = deque()
    q.append((0, 0))
    s = set((0,))
    while q:
        i, n = q.popleft()
        for j in coins:
            k = i + j
            if k == N:
                print(n+1)
                return
            if k > N:
                continue
            if k in s:
                continue
            q.append((k, n+1))
            s.add(k)
    print(-1)

main()

Submission status: Accepted

Solution code:
import sys

from collections import deque
# q = deque(); q.append(x); q.appendleft(x); q.pop() -> x; q.popleft() -> x
from collections import defaultdict
# d = defaultdict(lambda: []); d[key] -> []
import heapq
# hq = []; heapq.heappush(hq, x); heapq.heappop(hq) -> x; heapq.heappushpop(hq, x) -> x
import bisect
# i = bisect.bisect_left([1,2,3,4], 1.5); i = bisect.bisect_right([4,3,2,1], 1.5)

#import numpy as np
#from scipy.misc import comb

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

# BFS方法
def main():
    N = i2n()
    coins = [1]
    d = 6
    while d <= N:
        coins.append(d)
        d *= 6
    d = 9
    while d <= N:
        coins.append(d)
        d *= 9
    q = deque()
    q.append((0, 0))
    s = set((0,))
    while len(q) > 0:
        i, n = q.popleft()
        for j in coins:
            k = i + j
            if k == N:
                print(n+1)
                return
            if k > N:
                continue
            if k in s:
                continue
            q.append((k, n+1))
            s.add(k)
    print(-1)

main()

Submission status: Accepted

Solution code:
N=int(input())
def cou(n,x):
    i=0
    while(n>0):
        i+=n%x
        n//=x
    return i
ans=N

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

Submission status: Accepted

Solution code:
N = int(input())
dp = [float("inf")]*(N+10)
dp[0] = 0
for i in range(1,N+5):
    k = 0
    while i-6**k >= 0:
        dp[i] = min(dp[i-6**k]+1,dp[i])
        k += 1
    k = 1
    while i-9**k >= 0:
        dp[i] = min(dp[i-9**k]+1,dp[i])
        k += 1
print(dp[N])

Submission status: Accepted

Solution code:
MAXINT = 100010    # 十分に大きな数（回数）

# 引き出す金額を入力
N = int(input())

# 動的計画法のテーブル
dp = [MAXINT] * (N + 1)

# 初期値を設定
dp[0] = 0

# １円からN円に向かって探索　貰うDP
for i in range(1, N + 1):
    dp[i] = min(dp[i - 1] + 1, dp[i])
    
    j = 0
    while (i - 6 ** j) >= 0:
        dp[i] = min(dp[i - 6 ** j] + 1, dp[i])
        j += 1
        
    j = 0
    while (i - 9 ** j) >= 0:
        dp[i] = min(dp[i - 9 ** j] + 1, dp[i])
        j += 1

print(dp[N])

Submission status: Accepted

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

dp[0] = 0

for i in range(n + 1):

  dp[i] = min(dp[i], dp[i-1] + 1)

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

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


print(dp[n])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())

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

    res = min(res, cnt)

print(res)

Submission status: Accepted

Solution code:
import sys
import os
from sys import stdin
import math

# stdin = open(os.path.dirname(__file__) + '/input.txt')  # local test
input = stdin.readline
sys.setrecursionlimit(20000000)


N = int(input())
i_6 = math.ceil(math.log(N, 6))
i_9 = math.ceil(math.log(N, 9))

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

for i in range(N):
    for j in range(i_6 + 1):
        if (i + 6 ** j) > N:
            break
        if dp[i] < dp[i + 6 ** j]:
            dp[i + 6 ** j] = dp[i] + 1

    for k in range(i_9 + 1):
        if (i + 9 ** k) > N:
            break
        if dp[i] < dp[i + 9 ** k]:
            dp[i + 9 ** k] = dp[i] + 1

print(dp[N])

Submission status: Accepted

Solution code:
n = int(input())
coins = [1]

i = 1
while True:
  coin = 6**i
  if coin > 100000:
    break
  coins.append(coin)
  i += 1

i = 1
while True:
  coin = 9**i
  if coin > 100000:
    break
  coins.append(coin)
  i += 1

dp = [0] * (n+1)

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

print(dp[n])

Submission status: Accepted

Solution code:
n=int(input())
dp=list(range(n+1))
C=[]
i=1
while n>=6**i:
    C.append(6**i)
    C.append(9**i)
    i+=1
i=1
while n>=9**i:
    C.append(9**i)
    i+=1
C.sort()


for c in C:
    for i in range(n+1):
        if i-c<0:continue
        dp[i]=min(dp[i],dp[i-c]+1)
print(dp[-1])

Submission status: Accepted

Solution code:
n=int(input())
dp=list(range(n+1))
C=[]
i=1
while n>=6**i:
    C.append(6**i)
    i+=1
i=1
while n>=9**i:
    C.append(9**i)
    i+=1
C.sort()


for c in C:
    for i in range(n+1):
        if i-c<0:continue
        dp[i]=min(dp[i],dp[i-c]+1)
print(dp[-1])

Submission status: Accepted

Solution code:
input_num = int(input())

combinations = [(row1, row2, row3, row4, row5, row6)
               for row1 in range(0, 6)
               for row2 in range(0, 6)
               for row3 in range(0, 6)
               for row4 in range(0, 6)
               for row5 in range(0, 6)
               for row6 in range(0, 6)]


num_list = []

for i in combinations:
  row1, row2, row3, row4, row5, row6 = i
  draw = 6 ** 1 * row1 ++ 6 ** 2 * row2 + 6 ** 3 * row3 + 6 ** 4 * row4 + 6 ** 5 * row5 + 6 ** 6 * row6
  if draw > input_num:
    continue
  else:
    result = input_num - draw
    draw_list = sum(i)
    for n in reversed(range(1, 6)):
      draw_n = result // 9 ** n
      result -= 9 ** n * draw_n
      draw_list += draw_n
    draw_list += result
    num_list.append(draw_list)
    
print(str(min(num_list)))

Submission status: Accepted

Solution code:
N=int(input())
INF=10**9
dp=[INF]*(N+1)#dp[i] 足場i+1にいるときの最小コスト
dp[0]=0
list=[1]
i=1
while(6**i<=N):
    list.append(6**i)
    i+=1
i=1
while(9**i<=N):
    list.append(9**i)
    i+=1
for i in range(N+1):
    for k in list:
        if i+k<=N:
            dp[i+k]=min(dp[i+k],1+dp[i])
print(dp[N])

Submission status: Accepted

Solution code:
## 解説を見た
## まず9のべき乗の引き出しを行い、その後(最適に)6のべき乗の引き出しを行う
## 9のべき乗の引き出しは全通り行い、残金を全列挙する
## それぞれの残金を6進数で表し、各桁の総和が「6で引き出すコスト」となる

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

def Base_n_to_10(X,n):
    out = 0
    for i in range(1,len(str(X))+1):
        out += int(str(X)[-i])*(n**(i-1))
    return out


N = int(input())

after_draw_9 = []
for i in range(N // 9 + 1):
  cost_9 = sum(map(int, Base_10_to_n(9*i,9)))
  after_draw_9.append((N-9*i, cost_9))
#print(after_draw_9)

solver = []
for i in range(len(after_draw_9)):
  cost_6 = sum(map(int, Base_10_to_n(after_draw_9[i][0], 6)))
  solver.append(after_draw_9[i][1] + cost_6)
  
#print(solver)
print(min(solver))

Submission status: Accepted

Solution code:
N = int(input())

L =[1,6**1,6**2,6**3,6**4,6**5,6**6,9**1,9**2,9**3,9**4,9**5]
X = [0]*(N+1)
for i in range(1, N+1):
    X[i] = 100000

for i in range(N+1):
    for l in L:
        if i+l <= N:
            X[i+l] = min(X[i] + 1, X[i+l])
        
print(X[-1])

Submission status: Accepted

Solution code:
from collections import deque
INF = float('inf')
n = int(input())
g = {i: [] for i in range(n + 1)}
for i in range(n):
    g[i].append(i + 1)
    num = 6
    while num <= n:
        g[i].append(i + num)
        num *= 6
    num = 9
    while num <= n:
        g[i].append(i + num)
        num *= 9
queue = deque([0])
dist = [INF] * (n + 1)
dist[0] = 0
while queue:
    c = queue.pop()
    for node in g[c]:
        if node <= n and dist[node] == INF:
            queue.appendleft(node)
            dist[node] = dist[c] + 1
print(dist[n])

Submission status: Accepted

Solution code:
N = int(input())

ans = 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
    
    ans = min(ans, c)
print(ans)

Submission status: Accepted

Solution code:
import sys


sys.setrecursionlimit(1000000)


MAX_N = 100001

memo = [-1] * MAX_N


def f(n):
    # 残り金額が0なら引き出す必要がないので0(再帰の終端条件)
    if n == 0:
        return 0
    # すでに探索済みならメモを参照する
    if memo[n] != -1:
        return memo[n]

    res = sys.maxsize

    pow9 = 1
    while pow9 <= N:
        if n - pow9 < 0:
            break
        res = min(res, f(n-pow9)+1)
        pow9 *= 9


    pow6 = 1
    while pow6 <= N:
        if n - pow6 < 0:
            break
        res = min(res, f(n-pow6)+1)
        pow6 *= 6

    # メモ
    memo[n] = res

    return res


if __name__ == '__main__':
    N = int(input())

    print(f(N))

Submission status: Accepted

Solution code:
import sys


sys.setrecursionlimit(1000000)


MAX_N = 100001

memo = [-1] * MAX_N


def f(n):
    # 残り金額が0なら引き出す必要がないので0(再帰の終端条件)
    if n == 0:
        return 0
    # すでに探索済みならメモを参照する
    if memo[n] != -1:
        return memo[n]

    res = sys.maxsize

    pow9 = 1
    while pow9 <= N:
        if n - pow9 < 0:
            break
        # print(n)
        # print(pow9)
        res = min(res, f(n-pow9)+1)
        pow9 *= 9

    pow6 = 1
    while pow6 <= N:
        if n - pow6 < 0:
            break
        res = min(res, f(n-pow6)+1)
        pow6 *= 6

    # メモ
    memo[n] = res

    return res


if __name__ == '__main__':
    N = int(input())

    print(f(N))

Submission status: Accepted

Solution code:
n=int(input())

ans=n
for i in range(n+1):
    count=0
    pow6=6
    while pow6<=i:
        count+= (i%(pow6*6))//pow6
        pow6*=6
    pow9=9
    while pow9<=n-i:
        count+= ((n-i)%(pow9*9))//pow9
        pow9*=9
    count+= (i%6)+((n-i)%9)
    ans=min(ans,count)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python

def get_sum_digits(n, m):
    r = 0
    while n:
        r, n = r + n % m, n // m
    return r

N = int(input())
ans = 10*5
for i in range(N+1):
    ans = min(ans, get_sum_digits(i, 6) + get_sum_digits(N-i, 9))
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
l9 = []
l9.append(1)
tmp = 1
while tmp <= 10**5:
  tmp *= 9
  l9.append(tmp)
l6 = []
l6.append(1)
tmp = 1
while tmp <= 10**5:
  tmp *= 6
  l6.append(tmp)

  
import bisect 
n = int(input())
ans = 10**6

for i in range(0, n+1):

  a = i
  b = n - i
  p = 0
  while a > 0:
    idx = bisect.bisect_left(l6, a)
    if a == l6[idx]:
      a -= l6[idx]
    else:
      a -= l6[idx-1]
    p += 1
    
  q = 0
  while b > 0:
    idx = bisect.bisect_left(l9, b)
    if b == l9[idx]:
      b -= l9[idx]
    else:
      b -= l9[idx-1]
    q += 1
    
  ans = min(ans, p+q)

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
ans = 10**6
for i in range(0, n+1):
  cnt = 0
  
  a = i
  b = n - i
  p = 0
  # aは6のn乗何個で表すことができるか。a+b=n
  while a > 0:
    p += a % 6 # 6**Xをaから何個引くことができるか
    a = a // 6
    
  q = 0
  while b > 0:
    q += b % 9
    b = b // 9
    
  ans = min(ans, p+q)
  
  
print(ans)

Submission status: Accepted

Solution code:

N=int(input())
dp = [N]*100001
dp[0]=0
for i in range(1,N+1):
    temp = 1
    while temp <= i:
        dp[i]=min(dp[i], dp[i-temp] + 1)
        temp *= 6

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

print(dp[N])

Submission status: Accepted

Solution code:
n = int(input())

def ind6(x):
    j = 0
    while 6 ** (j + 1) <= x:
        j += 1
    return j
def ind9(x):
    j = 0
    while 9 ** (j + 1) <= x:
        j += 1
    return j
    
ans = [1000] * 100001

for i in range(6):
    ans[i] = i 

for i in range(100001):
    if ans[i] == 1000:
        ans[i] = min(ans[i-1]+1,ans[i-6**ind6(i)]+1,ans[i-9**ind9(i)]+1)
print(ans[n])

Submission status: Accepted

Solution code:
n=int(input())

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


for i in range(1,100010):
  n6=0
  n9=0
  li=[]
  while 6**(n6+1)<=i:
    n6+=1
  while 9**(n9+1)<=i:
    n9+=1
  for j in range(n6+1):
    li.append(dp[i-6**n6])
  for jj in range(n9+1):
    li.append(dp[i-9**n9])
  dp[i]=min(li)+1
print(dp[n])

Submission status: Accepted

Solution code:
# 14:50

N = int(input())
# 100000
MAX = 100000

dp = [0]*(N+1)

coins = [1]
for d in range(1,10):
    t = 6 ** d
    if t > MAX:
        break
    coins.append(t)

for d in range(1,10):
    t = 9 ** d
    if t > MAX:
        break
    coins.append(t)

coins.sort()

# coins | 0 | 1 | 6 | 7 | 8 | 9 |
# 1     | 0 | 1 | 6 | 7 |
# 6     | 0 | 1 | 1 | 2 |
# 9     |   |   |   |
def solve(N):
    for i in range(0,N+1):
        dp[i] = i

    for c in coins[1:]:
        for i in range(c, N+1):
            if dp[i-c] + 1 < dp[i]:
                dp[i] = dp[i-c]+1
    return dp[N]
print(solve(N))

Submission status: Accepted

Solution code:
n = int(input())
ans = n
l9 = [9**i for i in range(6,0,-1)]
l6 = [6**i for i in range(7,-1,-1)]
for i in range(n//9+1):
  x9 = i*9
  x61= n-x9
  csum = 0
  for x in l9:
    csum += x9//x
    x9 %= x
  for x in l6:
    csum += x61//x
    x61 %= x
  if ans > csum:
    ans = csum
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=n
for i in range(n+1):
    ni,si=i,n-i
    m=0
    while ni!=0:m+=ni%9;ni//=9
    while si!=0:m+=si%6;si//=6
    a=min(a,m)
print(a)

Submission status: Accepted

Solution code:
n=int(input())
a=n
for i in range(n+1):
  ni,si=i,n-i
  m=0
  while ni!=0:m+=ni%9;ni//=9
  while si!=0:m+=si%6;si//=6
  a=min(a,m)
print(a)

Submission status: Accepted

Solution code:
N = int(input())

l = [1] + [6 ** x for x in range(1, 7)] + [9 ** x for x in range(1, 6)]
l.sort()

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

for n in range(1, N + 1):
	dp[n] = min([dp[n - f] + 1 if 0 <= n - f else INF for f in l])
	#print(dp)
print(dp[-1])

Submission status: Accepted

Solution code:
N = int(input())

l = [1] + [6 ** x for x in range(1, 7)] + [9 ** x for x in range(1, 6)]
l.sort()

INF = 10 ** 3
dp = [0] + [INF] * N

for n in range(1, N + 1):
	#for f in [1, 6, 9, 6 ** 2, 9 ** 2, 6 ** 3, 9 ** 3]:
	for f in l:
		if 0 <= n - f:
			dp[n] = min([dp[n], dp[n - f] + 1])
			#print(dp)
print(dp[-1])