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 to_n(X, n):
    out = 0
    while X>0:
        out += (X%n)
        X = int(X/n)
    return out
  
n = int(input())
ans = 10 ** 6
for i in range(n+1):
  tmp = 0
  res = n
  if not i % 9:
    tmp += to_n(i,9)
    res -= i
  tmp += to_n(res,6)
  ans = min(ans,tmp)
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=[0]*(n+1)
six=0
nine=0
for i in range(1,n+1):
  if i>=6**(six+1):
    six+=1
  if i>=9**(nine+1):
    nine+=1
  a[i]=min(a[i-1],a[i-6**six],a[i-9**nine])+1
print(a[n])

Submission status: Accepted

Solution code:
def count(n, b):
  res = 0
  while n:
    res += n % b
    n //= b
  return res

def main():
  res = float('inf')
  for i in range(n + 1):
    res = min(res, count(i, 6) + count(n - i, 9))
  print(res)
 
if __name__ ==  '__main__':
  n = int(input())
  main()

Submission status: Accepted

Solution code:
def resolve():
    wd6 = [46656, 7776, 1296, 216, 36, 6, 1]
    wd9 = [59049, 6561, 729, 81, 9, 1]
    def div6(n):
        ans = 0
        for i in wd6:
            if i <= n:
                ans += n//i
                n %= i
        return ans

    def div9(n):
        ans = 0
        for j in wd9:
            if j <= n:
                ans += n // j
                n %= j
        return ans
    n = int(input())

    wd = []
    for k in range(n+1):
        wd.append(div6(k) + div9(n-k))
    print(min(wd))
resolve()

Submission status: Accepted

Solution code:
N=int(input())

A=[1]

i = 1
while True:
    if 6**i <= 100000:
        A.append(6**i)
    else:
        break
    i += 1

i = 1
while True:
    if 9**i <= 100000:
        A.append(9**i)
    else:
        break
    i += 1

A.sort()

dp = [N]*(N+1)
dp[0] = 0
for i in range(1, N+1):
    for j in range(len(A)):
        if i - A[j] >= 0:
            dp[i] = min(1+dp[i-A[j]], dp[i])

print(dp[-1])

Submission status: Accepted

Solution code:
import math, sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from copy import deepcopy
from functools import lru_cache
from heapq import heapify, heappop, heappush
from itertools import accumulate, combinations, permutations
input = sys.stdin.readline
mod = 10**9 + 7
ns = lambda: input().strip()
ni = lambda: int(input().strip())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

n = ni()

res = n
for i in range(n+1):
    cash = 0
    t = i
    while t > 0: # 0 ~ iを6で表す
        cash += t % 6
        t //= 6
    t = n - i
    while t > 0: # n-i ~ nを9で表す
        cash += t % 9
        t //= 9
    if res > cash: # cash最小値
        res = cash

print(res)

Submission status: Accepted

Solution code:
import math, sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from copy import deepcopy
from functools import lru_cache
from heapq import heapify, heappop, heappush
from itertools import accumulate, combinations, permutations
input = sys.stdin.readline
mod = 10**9 + 7
ns = lambda: input().strip()
ni = lambda: int(input().strip())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

n = ni()

res = 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
    if res > cc:
        res = cc

print(res)

Submission status: Accepted

Solution code:
n = int(input())
cand = [1]
for i in range(1,7):
    cand.append(6**i)
for j in range(1,6):
  cand.append(9**j)
cand.sort()
dp = []
for c in cand:
  hoge = []
  for i in range(n+1):
    if i % c == 0:
      hoge.append(i//c)
    else:
      hoge.append(i)
  dp.append(hoge)
for a in range(1,12):
  for b in range(1,n+1):
    if b >= cand[a]:
    	dp[a][b] = min(dp[a-1][b],dp[a][b - cand[a]] + 1)
    else:
      dp[a][b]  = dp[a-1][b]
      
print(dp[-1][n])

Submission status: Accepted

Solution code:
N = int(input())
B = [pow(6,i) for i in range(1,10) if pow(6,i)<=N]
C = [pow(9,i) for i in range(1,10) if pow(9,i)<=N]
A = sorted(B+C+[1])
L = len(A)
DP = [[N]*(N+1) for i in range(L)]
DP[0] = [i for i in range(N+1)]
for l in range(1,L):
    k = A[l]
    for n in range(0,k):
        DP[l][n] = DP[l-1][n]
    for n in range(k,N+1):
        DP[l][n] = min(DP[l-1][n-k]+1,DP[l][n-k]+1,DP[l-1][n])
print(DP[L-1][N])

Submission status: Accepted

Solution code:
inf = 10**9+7

n = int(input())
dp = [inf for i in range(n+1)]
dp[0] = 0
tmp = 1
use = [1]
while tmp*6 <= n:
    tmp *= 6
    use.append(tmp)
tmp = 1
while tmp*9 <= n:
    tmp *= 9
    use.append(tmp)
use.sort()

for i in range(n):
    for num in use:
        if i+1-num >= 0:
            dp[i+1] = min(dp[i+1], dp[i+1-num]+1)
        else:
            break
print(dp[n])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
m = [1, 6, 9, 36, 81, 216, 729, 1296, 6561, 7776, 46656, 59049]
dp = [10**6 for i in range(100001)]
for mi in m:
    dp[mi] = 1
for i in range(1,100001):
    for mi in m:
        if i+mi <= 100000:
            dp[i+mi] = min(dp[i+mi],dp[i]+1)
        else:
            break
print(dp[n])

Submission status: Accepted

Solution code:
import math
n = int(input())

target_ls = [1]
target_6 = 6
while target_6 <= n:
    target_ls.append(target_6)
    target_6 *= 6
target_9 = 9
while target_9 <= n:
    target_ls.append(target_9)
    target_9 *= 9

dp = [float('inf')] * (n+1)
dp[0] = 0
for i in range(n):
    for j in target_ls:
        if i+j <= n:
            dp[i+j] = min(dp[i+j],dp[i] + 1)
print(dp[n])

Submission status: Accepted

Solution code:
import sys

def count(n, b):
    res = 0
    while n:
        res += n % b
        n //= b
    return res

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

def main():
    res = float('inf')
    for i in range(n + 1):
        res = min(res, count(i, 6) + count(n - i, 9))
    print(res)

if __name__ ==  '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

def count(n, b):
    res = 0
    while n:
        n, r = divmod(n, b)
        res += r
    return res

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

def main():
    res = float('inf')
    for i in range(n + 1):
        res = min(res, count(i, 6) + count(n - i, 9))
    print(res)

if __name__ ==  '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())

L6 = []
for i in range(1, 100):
  if 6**i <= n:
    L6.append(6**i)
  else:
    break

L9 = []
for i in range(1, 100):
  if 9**i <= n:
    L9.append(9**i)
  else:
    break

dp = [0] * (n+1)
    
for i in range(1, n+1):
  dp[i] = dp[i-1] + 1
  for l6 in L6:
    if i - l6 >= 0:
      dp[i] = min(dp[i], dp[i - l6] + 1)
  for l9 in L9:
    if i - l9 >= 0:
      dp[i] = min(dp[i], dp[i - l9] + 1)
print(dp[n])

Submission status: Accepted

Solution code:
#import collections
#aa = collections.Counter(a) # list to list
#from itertools import combinations # (string,3) 3回

mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    n = int(input())
    def count_(num,x):
        i = 0
        while num > 0:
            i += num % x
            num //= x
        return i
    ans = n

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




if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
n = int(input())
dp = [10**5]*(10**5+1)
dp[0] = 0
for i in range(n+1):
  if i >= 1:
    dp[i] = min(dp[i-1]+1,dp[i])
  if i >= 6:
    dp[i] = min(dp[i-6]+1,dp[i])
  if i >= 9:
    dp[i] = min(dp[i-9]+1,dp[i])
  if i >= 36:
    dp[i] = min(dp[i-36]+1,dp[i])
  if i >= 81:
    dp[i] = min(dp[i-81]+1,dp[i])
  if i >= 216:
    dp[i] = min(dp[i-216]+1,dp[i])
  if i >= 729:
    dp[i] = min(dp[i-729]+1,dp[i])
  if i >= 1296:
    dp[i] = min(dp[i-1296]+1,dp[i]) 
  if i >= 6561:
    dp[i] = min(dp[i-6561]+1,dp[i])
  if i >= 7776:
    dp[i] = min(dp[i-7776]+1,dp[i])
  if i >= 46656:
    dp[i] = min(dp[i-46656]+1,dp[i])
  if i >= 59049:
    dp[i] = min(dp[i-59049]+1,dp[i])
print(dp[n])

Submission status: Accepted

Solution code:
def cnt(n,p):
    tmp=0
    m=n
    while(m>0):
        tmp+=m%p
        m//=p
    return tmp
ans=10**15
N=int(input())
for i in range(N+1):
    ans=min(ans,cnt(i,6)+cnt(N-i,9))
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
dp = [float("inf")] * (N + 1)
dp[0] = 0
for i in range(N):
  dp[i + 1] = min(dp[i + 1], dp[i] + 1)
  for j in range(1, 8):
    if i + pow(6, j) <= N: dp[i + pow(6, j)] = min(dp[i + pow(6, j)], dp[i] + 1)
    if i + pow(9, j) <= N: dp[i + pow(9, j)] = min(dp[i + pow(9, j)], dp[i] + 1)
print(dp[-1])

Submission status: Accepted

Solution code:
n = int(input())
INF = float('inf')
dp = [INF]*(n+1)
dp[0] = 0
# 配ればいい
for i in range(n):
    for j in range(7):
        if i+6**j < n+1:
            dp[i+6**j] = min(dp[i+6**j], dp[i]+1)
        if i+9**j < n+1:
            dp[i+9**j] = min(dp[i+9**j], dp[i]+1)
print(dp[-1])

Submission status: Accepted

Solution code:
n = int(input())
INF = float('inf')
dp = [INF]*(n+1)
dp[0] = 0
# 配ればいい
for i in range(n):
    for j in range(7):
        if i+6**j < n+1:
            dp[i+6**j] = min(dp[i+6**j], dp[i]+1)
        if i+9**j < n+1:
            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

six = 0
while True:
    if 6**(six+1) > n:
        break
    six += 1

nine = 0
while True:
    if 9**(nine+1) > n:
        break
    nine += 1

for a, b in zip([1, 6, 9], [1, six, nine]):
    for i in range(1, b+1):
        k = a**i
        for j in range(n):
            if j+k > n:
                break
            dp[j+k] = min(dp[j+k], dp[j]+1)
print(dp[n])

Submission status: Accepted

Solution code:
import math
import string
import collections
from collections import Counter
from collections import deque
import sys
sys.setrecursionlimit(2*10**5)
INF = 2**60


def readints():
    return list(map(int, input().split()))


def nCr(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor


# coordinates
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]

N = int(input())
dp = [INF]*(N+1)
dp[0] = 0

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

Submission status: Accepted

Solution code:
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from decimal import *
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
INF = float('inf') #無限大
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(sys.stdin.readline()) #整数読み込み
def ifn(): return float(sys.stdin.readline()) #浮動小数点読み込み
def isn(): return sys.stdin.readline().split() #文字列読み込み
def imn(): return map(int, sys.stdin.readline().split()) #整数map取得
def imnn(): return map(lambda x:int(x)-1, sys.stdin.readline().split()) #整数-1map取得
def fmn(): return map(float, sys.stdin.readline().split()) #浮動小数点map取得
def iln(): return list(map(int, sys.stdin.readline().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, sys.stdin.readline().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD
def print_list(l): print(*l, sep='\n')
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def No(): print('No')

def sieves_of_e(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n+1, i): is_prime[j] = False
    return is_prime

N = iin()

money = []
pow6 = 1
while pow6 <= N:
    money.append(pow6)
    pow6 *= 6
pow9 = 9
while pow9 <= N:
    money.append(pow9)
    pow9 *= 9
lm = len(money)
dp = [INF for _ in range(N+1)]
dp[0] = 0
for i in range(lm):
    for j in range(N+1):
        if j - money[i] >= 0:
            dp[j] = min(dp[j], dp[j-money[i]]+1)
print(dp[N])

Submission status: Accepted

Solution code:
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from decimal import *
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
INF = float('inf') #無限大
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(sys.stdin.readline()) #整数読み込み
def ifn(): return float(sys.stdin.readline()) #浮動小数点読み込み
def isn(): return sys.stdin.readline().split() #文字列読み込み
def imn(): return map(int, sys.stdin.readline().split()) #整数map取得
def imnn(): return map(lambda x:int(x)-1, sys.stdin.readline().split()) #整数-1map取得
def fmn(): return map(float, sys.stdin.readline().split()) #浮動小数点map取得
def iln(): return list(map(int, sys.stdin.readline().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, sys.stdin.readline().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD
def print_list(l): print(*l, sep='\n')
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def No(): print('No')

def sieves_of_e(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n+1, i): is_prime[j] = False
    return is_prime

N = iin()


money = []
pow6 = 1
while pow6 <= N:
    money.append(pow6)
    pow6 *= 6
pow9 = 9
while pow9 <= N:
    money.append(pow9)
    pow9 *= 9
lm = len(money)
dp = [[INF for _ in range(N+1)] for _ in range(lm+1)]
dp[0][0] = 0
for i in range(lm):
    for j in range(N+1):
        dp[i+1][j] = dp[i][j]
        if j - money[i] >= 0:
            dp[i+1][j] = min(dp[i+1][j], dp[i+1][j-money[i]]+1)
print(dp[lm][N])

Submission status: Accepted

Solution code:
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from decimal import *
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
INF = float('inf') #無限大
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(sys.stdin.readline()) #整数読み込み
def ifn(): return float(sys.stdin.readline()) #浮動小数点読み込み
def isn(): return sys.stdin.readline().split() #文字列読み込み
def imn(): return map(int, sys.stdin.readline().split()) #整数map取得
def imnn(): return map(lambda x:int(x)-1, sys.stdin.readline().split()) #整数-1map取得
def fmn(): return map(float, sys.stdin.readline().split()) #浮動小数点map取得
def iln(): return list(map(int, sys.stdin.readline().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, sys.stdin.readline().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD
def print_list(l): print(*l, sep='\n')
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def No(): print('No')

def sieves_of_e(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n+1, i): is_prime[j] = False
    return is_prime

N = iin()

dp = [-1 for _ in range(N+1)]
dp[0] = 0
queue = deque([0])

while len(queue) > 0:
    current = queue.popleft()
    
    pow6 = 1
    while current+pow6 <= N:
        if dp[current+pow6] == -1:
            queue.append(current+pow6)
            dp[current+pow6] = dp[current]+1
        pow6 *= 6

    pow9 = 1
    while current+pow9 <= N:
        if dp[current+pow9] == -1:
            queue.append(current+pow9)
            dp[current+pow9] = dp[current]+1
        pow9 *= 9
print(dp[N])

Submission status: Accepted

Solution code:
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from decimal import *
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
INF = float('inf') #無限大
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(sys.stdin.readline()) #整数読み込み
def ifn(): return float(sys.stdin.readline()) #浮動小数点読み込み
def isn(): return sys.stdin.readline().split() #文字列読み込み
def imn(): return map(int, sys.stdin.readline().split()) #整数map取得
def imnn(): return map(lambda x:int(x)-1, sys.stdin.readline().split()) #整数-1map取得
def fmn(): return map(float, sys.stdin.readline().split()) #浮動小数点map取得
def iln(): return list(map(int, sys.stdin.readline().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, sys.stdin.readline().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD
def print_list(l): print(*l, sep='\n')
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def No(): print('No')

def sieves_of_e(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n+1, i): is_prime[j] = False
    return is_prime

N = iin()

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

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

Submission status: Accepted

Solution code:
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from decimal import *
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
INF = float('inf') #無限大
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(sys.stdin.readline()) #整数読み込み
def ifn(): return float(sys.stdin.readline()) #浮動小数点読み込み
def isn(): return sys.stdin.readline().split() #文字列読み込み
def imn(): return map(int, sys.stdin.readline().split()) #整数map取得
def imnn(): return map(lambda x:int(x)-1, sys.stdin.readline().split()) #整数-1map取得
def fmn(): return map(float, sys.stdin.readline().split()) #浮動小数点map取得
def iln(): return list(map(int, sys.stdin.readline().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, sys.stdin.readline().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD
def print_list(l): print(*l, sep='\n')
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def No(): print('No')

def sieves_of_e(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n+1, i): is_prime[j] = False
    return is_prime

N = iin()

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

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

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

print(dp[N])

Submission status: Accepted

Solution code:
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from decimal import *
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
INF = float('inf') #無限大
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(sys.stdin.readline()) #整数読み込み
def ifn(): return float(sys.stdin.readline()) #浮動小数点読み込み
def isn(): return sys.stdin.readline().split() #文字列読み込み
def imn(): return map(int, sys.stdin.readline().split()) #整数map取得
def imnn(): return map(lambda x:int(x)-1, sys.stdin.readline().split()) #整数-1map取得
def fmn(): return map(float, sys.stdin.readline().split()) #浮動小数点map取得
def iln(): return list(map(int, sys.stdin.readline().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, sys.stdin.readline().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD
def print_list(l): print(*l, sep='\n')
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def No(): print('No')

def sieves_of_e(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n+1, i): is_prime[j] = False
    return is_prime

N = iin()

memo = [-1 for _ in range(N+1)]

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

Submission status: Accepted

Solution code:
n = int(input())
dp = [0]*(n+1)
dp[0] = 0
dp[1] = 1
for i in range(2,n+1):
    c = float("inf")
    j = 1
    while j <= i:
        c = min(c,dp[i-j]+1)
        j *= 6
    k = 1
    while k <= i:
        c = min(c,dp[i-k]+1)
        k *= 9
    dp[i] = c

print(dp[n])

Submission status: Accepted

Solution code:
import math
n=int(input())
l1=math.floor(math.log(n,6))
l2=math.floor(math.log(n,9))
dp=[i for i in range(n+1)]
for i in range(1,l1+1):
    for j in range(n):
        if j+6**i<n+1:
            dp[j+6**i]=min(dp[j]+1,dp[j+6**i])
for i in range(1,l1+1):
    for j in range(n):
        if j+9**i<n+1:
            dp[j+9**i]=min(dp[j]+1,dp[j+9**i])
print(dp[-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
n=int(input())
l1=math.ceil(math.log(n,6))
l2=math.ceil(math.log(n,9))
dp=[i for i in range(n+1)]
for i in range(1,l1+1):
    for j in range(n):
        if j+6**i<n+1:
            dp[j+6**i]=min(dp[j]+1,dp[j+6**i])
for i in range(1,l1+1):
    for j in range(n):
        if j+9**i<n+1:
            dp[j+9**i]=min(dp[j]+1,dp[j+9**i])
print(dp[-1])

Submission status: Accepted

Solution code:
import numpy as np
N=int(input())
six=[1]
nine=[]
for i in range(1,N):
  six.append(6**i)
  nine.append(9**i)
  if 6**i>N:
    break
six=np.array(six)
nine=np.array(nine)
L=np.concatenate([six,nine])    
now=N
count=0
dp=np.ones(N+L.max()+1)*10**9
dp[1]=1
dp[0]=0
#dp[i+1]　iをちょうど引き出すのに必要な最小回数
for i in range(1,N):
  dp[i+1]=(dp[i-L+1]+1).min()

  
print(int(dp[N]))
#print(len(L))

Submission status: Accepted

Solution code:
import numpy as np
N=int(input())
six=[1]
nine=[]
for i in range(1,N):
  six.append(6**i)
  nine.append(9**i)
  if 6**i>N:
    break
six=np.array(six)
nine=np.array(nine)
L=np.concatenate([six,nine])    
now=N
count=0
dp=np.ones(N+L.max()+1)*np.inf
dp[1]=1
dp[0]=0
#dp[i+1]　iをちょうど引き出すのに必要な最小回数
for i in range(1,N):
  dp[i+1]=(dp[i-L+1]+1).min()

  
print(int(dp[N]))
#print(len(L))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000)
def resolve():
    N = int(input())
    candidates = []
    x6 = 6
    x9 = 9
    while True:
        if x6 > N and x9 > N:
            break
        if x6 <= N:
            candidates.append(x6)
        if x9 <= N:
            candidates.append(x9)
        x6 = x6 * 6
        x9 = x9 * 9
    candidates.sort()
    # print(candidates)
    dic = {}
    res = rec(candidates, N, dic)
    print(res)

def rec(ary, target, dic):
    # print(dic)
    if target in dic:
        return dic[target]
    if len(ary) < 1:
        return target
    if ary[0] > target:
        dic[target] = target
        return target
    counts = []
    for i in ary:
        if target - i < 0:
            continue
        counts.append(rec(ary, target - i, dic)+1)
    dic[target] = min(counts)
    return dic[target]
        

if '__main__' == __name__:
    resolve()

Submission status: Accepted

Solution code:
N=int(input())

xlist=[1]
for d in range(1,10**9):
  if 6**d>100000:
    break
  xlist.append(6**d)
for d in range(1,10**9):
  if 9**d>100000:
    break
  xlist.append(9**d)
xlist.sort()
#print(xlist)

dp=[0]*(N+1)
for i in range(1,N+1):
  min_dp=10**9
  for x in xlist:
    if i-x<0:
      break
    min_dp=min(min_dp,dp[i-x])
  dp[i]=min_dp+1
  
#print(dp)
print(dp[-1])

Submission status: Accepted

Solution code:
N=int(input())

xlist=[1]
for d in range(1,10**9):
  if 6**d>100000:
    break
  xlist.append(6**d)
for d in range(1,10**9):
  if 9**d>100000:
    break
  xlist.append(9**d)
xlist.sort()
#print(xlist)

dp=[0,1]+[0]*(N-1)
for i in range(2,N+1):
  min_dp=10**9
  for x in xlist:
    if i-x>=0:
      min_dp=min(min_dp,dp[i-x])
  dp[i]=min_dp+1
  
#print(dp)
print(dp[-1])

Submission status: Accepted

Solution code:
n = int(input())
L = [1]
for i in range(1, 6):
    L.append(pow(9, i))
for i in range(1, 7):
    L.append(pow(6, i))
L = sorted(L)
dp = [float("inf") for _ in range(n + 1)]
dp[0] = 0
for i in range(1, n + 1):
    for l in L:
        if i - l >= 0:
            dp[i] = min(dp[i], dp[i - l] + 1)
print(dp[n])

Submission status: Accepted

Solution code:
n = int(input())
lis = [1]
i = 1
while 6 ** i <= n:
    lis.append(6 ** i)
    i += 1
i = 1
while 9 ** i <= n:
    lis.append(9 ** i)
    i += 1

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

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math
from fractions import gcd

NN = 202020
MOD = 10**9+7
INF = float("inf")

n = int(input())
min_time = n

for i in range(n+1):
    v6, v9 = i, n-i
    count = 0
    while v6 > 0:
        count += v6 % 6
        v6 //= 6
    while v9 > 0:
        count += v9 % 9
        v9 //= 9
    min_time = min(min_time, count)

print(min_time)

Submission status: Accepted

Solution code:
# 1次元DP
# 番兵を手前に100000用意してしまおうｗ
n = int(input())

dp = [9999] * (200000 + 10)
offset = 100000
dp[0 + offset] = 0

coin = []
coin.append(1)
temp = 6
while temp <= 100000:
    coin.append(temp)
    temp *= 6
temp = 9
while temp <= 100000:
    coin.append(temp)
    temp *= 9

# print(coin)

for i in range(1, len(dp) - offset):
    temp_min = 9999
    for c in coin:
        temp_min = min(temp_min, dp[i + offset - c])
    dp[i + offset] = temp_min + 1

print(dp[n + offset])