Problem:


Score : 300 points

Problem Statement

To make it difficult to withdraw money, a certain bank allows its customers to withdraw only one of the following amounts in one operation:

1 yen (the currency of Japan)

6 yen, 6^2(=36) yen, 6^3(=216) yen, ...

9 yen, 9^2(=81) yen, 9^3(=729) yen, ...

At least how many operations are required to withdraw exactly N yen in total?

It is not allowed to re-deposit the money you withdrew.

Constraints

1 \leq N \leq 100000

N is an integer.

Input

Input is given from Standard Input in the following format:

N

Output

If at least x operations are required to withdraw exactly N yen in total, print x.

Sample Input 1

127

Sample Output 1

4

By withdrawing 1 yen, 9 yen, 36(=6^2) yen and 81(=9^2) yen, we can withdraw 127 yen in four operations.

Sample Input 2

3

Sample Output 2

3

By withdrawing 1 yen three times, we can withdraw 3 yen in three operations.

Sample Input 3

44852

Sample Output 3

16



Sample input:
127


Sample output:
4

Submission status: Accepted

Solution code:
n=int(input())
def search(k,m):
    count=0
    while 0<k:
        count+=k%m
        k=k//m
    return count
ans=10**6
for i in range(n+1):
    
    ans=min(ans,search(i,9)+search(n-i,6))
    #print(search(i,6),search(n-i,9))
    #print(ans)
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue
from decimal import *


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def divisor(n):
        res = []
        i = 1
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                res.append(i)
                if i != n // i:
                    res.append(n // i)
        return res

    @staticmethod
    def round_up(a, b):
        return -(-a // b)

    @staticmethod
    def is_prime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


def pop_count(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


MOD = int(1e09) + 7
INF = int(1e15)


def solve():
    N = Scanner.int()
    dp = [0 for _ in range(N + 1)]
    for i in range(1, N + 1):
        dp[i] = dp[i - 1] + 1
        n = 6
        while i - n >= 0:
            dp[i] = min(dp[i], dp[i - n] + 1)
            n *= 6
        n = 9
        while i - n >= 0:
            dp[i] = min(dp[i], dp[i - n] + 1)
            n *= 9
    print(dp[N])


def main():
    # sys.stdin = open("sample.txt")
    solve()


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())

moneylist = [1]

money = 6

while money < 100000:
    moneylist.append(money)
    money = money*6

money = 9    

while money < 100000:
    moneylist.append(money)
    money = money*9
moneylist.sort()

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

for i in range(1,N+1): #お金
    for j in moneylist: #使えるお金
        if j <= i:
            dp[i] = min(dp[i],dp[i-j] + 1)
        
print(dp[-1])

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    dp = [None]*(n+1)
    dp[0] = 0
    dp[1] = 1
    nl = list(sorted([6**i for i in range(10) if (6**i)<=n]+[9**i for i in range(1, 10) if (9**i)<=n]))
    for i in range(2, n+1):
        d = 10**15
        for j in nl:
            if j > i:
                break
            d = min(d, 1+dp[i-j])
        dp[i] = d
    print(dp[n])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()

def MIN(a, b):
    if a > b:
        return b
    else:
        return a

def main():
    N = int(input())
    yen6 = [6 ** i for i in range(1, 7) if 6 ** i <= N]
    yen9 = [9 ** i for i in range(1, 6) if 9 ** i <= N]

    if N < 6:
        print(N)
        exit()

    dp = [N] * (N + 1)
    for i in range(6):
        dp[i] = i
    for i in range(N + 1):
        for j in yen6:
            if i + j > N:
                break
            dp[i+j] = MIN(dp[i+j], dp[i] + 1)
        for j in yen9:
            if i + j > N:
                break
            dp[i+j] = MIN(dp[i+j], dp[i] + 1)
    print(dp[N])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()

def MIN(a, b):
    if a > b:
        return b
    else:
        return a

def main():
    N = int(input())
    yen6 = [6 ** i for i in range(1, 7) if 6 ** i <= N]
    yen9 = [9 ** i for i in range(1, 6) if 9 ** i <= N]

    if N < 6:
        print(N)
        exit()

    dp = [N] * (N + 1)
    for i in range(6):
        dp[i] = i
    for i in range(1, N + 1):
        for j in yen6:
            if i - j < 0:
                break
            dp[i] = MIN(dp[i], dp[i - j] + 1)
        for j in yen9:
            if i - j < 0:
                break
            dp[i] = MIN(dp[i], dp[i - j] + 1)
    print(dp[N])

if __name__ == '__main__':
    main()

Submission status: Accepted

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

for i in range(1,100010):
  dp[i]=float('inf')
  
for i in range(1,100010):
  power6=1
  while power6<=i:
    dp[i]=min(dp[i-power6]+1,dp[i])
    power6*=6
  power9=1
  while power9<=i:
    dp[i]=min(dp[i-power9]+1,dp[i])
    power9*=9

print(dp[n])

Submission status: Accepted

Solution code:
N = int(input())

cands = [1]
for i in range(1, 7):
  if 6**i <= N:
    cands.append(6**i)
  if 9**i <= N:
    cands.append(9**i)

dp = [10**6] * (N+1)
dp[0] = 0
for i in range(1, N+1):
  for c in cands:
    if c <= i:
      dp[i] = min(dp[i], dp[i-c]+1)

print(dp[-1])

Submission status: Accepted

Solution code:
n = int(input())
dp = [0]

for i in range(1, n+1):
    q = []
    q.append(1+dp[i-1])

    a = 1
    while True:
        a *= 6
        if a > i:
            break
        q.append(1+dp[i-a])

    b = 1
    while True:
        b *= 9
        if b > i:
            break
        q.append(1+dp[i-b])

    dp.append(min(q))

print(dp[n])

Submission status: Accepted

Solution code:
n = int(input())
ans = n

for i in range(n+1):
    j = n-i

    a = j
    p = 0
    while a>0:
        p += a%6
        a = a//6

    b = i
    q = 0
    while b>0:
        q += b%9
        b = b//9

    ans = min(ans, p+q)

print(ans)

Submission status: Accepted

Solution code:
def calc(n,num):
  ret=0
  while n>0:
    ret+=n%num
    n//=num
  return ret

N=int(input())
ans=N

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

Submission status: Accepted

Solution code:

n = int(input())
ans = n

def calc(n, num):
    ret = 0
    while n > 0:
        ret += n % num
        n //= num
    return ret

for i in range(n + 1):
    cc = 0
    cc += calc(i, 6)
    cc += calc(n - i, 9)
    ans = min(ans, cc)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
import collections
from operator import mul
from functools import reduce
import bisect

#n,m=map(int,input().split())

n=int(input())
a=[1]
s=6
while s<=n:
    a.append(s)
    s*=6
s=9
while s<=n:
    a.append(s)
    s*=9
a=sorted(list(set(a)))


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

for i in range(n):
    for ai in a:
        if i+ai<=n:
            dp[i+ai]=min(dp[i+ai],dp[i]+1)
       
print(dp[n])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#import sys
#sys.setrecursionlimit(10 ** 7)
'''
#import numpy as np
import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
from itertools import permutations, combinations, product, accumulate, groupby
from bisect import bisect_left, bisect_right, insort_left, insort_right
from operator import itemgetter as ig
#sys.setrecursionlimit(10 ** 7)
'''
#inf = 10 ** 20
'''
INF = float("INF")
mod = 10 ** 9 + 7
"""dd = [(-1, 0), (0, 1), (1, 0), (0, -1)];
ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)];
ddn9 = ddn + [(0, 0)]
for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""

def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]  # WideIntPoint
def ws(): return sys.stdin.readline().split()
def si(): return int(sys.stdin.readline())  # SingleInt
def ss(): return input()
def hi(n): return [si() for _ in range(n)]
def hs(n): return [ss() for _ in range(n)]  # HeightString
def s_list(): return list(input())
def mi(n): return [wi() for _ in range(n)]  # MatrixInt
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]
def num_grid(n): return [[int(i) for i in sys.stdin.readline().split()[0]] for _ in range(n)]  # NumberGrid
def grid(n): return [s_list() for _ in range(n)]

'''
def main():
    N = int(input())
    dp = [99999999] * (N + 1)
    dp[0] = 0
    for i in range(1, N + 1):
        dp[i] = dp[i - 1] + 1
        k = 6
        while i - k >= 0:
            dp[i] = min(dp[i], dp[i - k] + 1)
            k *= 6
        k = 9
        while i - k >= 0:
            dp[i] = min(dp[i], dp[i - k] + 1)
            k *= 9

    print(dp[N])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

import bisect

# from collections import Counter, deque, defaultdict
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd

import itertools

# from operator import attrgetter, itemgetter
import math

# import numpy as np

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n = int(input())

    ones = [1]
    sixs = [6, 36, 216, 1296, 7776, 46656]
    nines = [9, 81, 729, 6561, 59049]
    withdraws = ones + sixs + nines

    money = {0}
    cnt = 0

    while True:
        cnt += 1
        next_money = set()
        for i in money:
            for j in withdraws:
                nxt = i + j
                if nxt <= n:
                    next_money.add(nxt)
        if n in next_money:
            print(cnt)
            sys.exit()
        else:
            money = next_money


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from functools import lru_cache
import sys
sys.setrecursionlimit(10**6)
n=int(input())
@lru_cache(None)
def solve(n):
    
    if n==0:
        return 0
    if n==1:
        return 1
    ans=n
    cur=6
    while cur<=n:
        ans=min(ans,1+solve(n-cur))
        cur*=6
    cur=9
    while cur<=n:
        ans=min(ans,1+solve(n-cur))
        cur*=9
    return ans
print(solve(n))

Submission status: Accepted

Solution code:
#99c
import math

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

#引き算を足し算で下から求める

#直で引き出せる一覧のsetを作る。
single_withdraw_set = set()
single_withdraw_set.add(1)
single_withdraw_set |= {6**i for i in range(1,2 + int(math.log(N,6)))}
single_withdraw_set |= {9**i for i in range(1,2 + int(math.log(N,9)))}
#print(single_withdraw_set)

#何回で引き出せるかのdict。この後の計算でマイナス値を参照するので、あらかじめ作っておく。
withdraw_dict = {int(-i):10**9+7 for i in range(1,1 + max(single_withdraw_set)) }
withdraw_dict[0] = 0

#最低の引き出し回数を1円から計算していく
for i in range(1,N+1):
    if i in single_withdraw_set:
        #1回で引き出せるsetにあるなら当然1回
        withdraw_dict[i] = 1
    else:
        #なければ (現状の値 - 1回で引き出し可能な値)の中で1番少ない値 + 1 
        withdraw_dict[i] = 1 + min([withdraw_dict[i-j] for j in single_withdraw_set])
    
    #print(i,":",withdraw_dict[i])
    
#print(withdraw_dict)
print(withdraw_dict[N])

Submission status: Accepted

Solution code:
N = int(input())
dp = [1000000] * (N + 1)
dp[0] = 0
for i in range(1, N + 1):
    dp[i] = dp[i - 1] + 1
    x = 6
    while i - x >= 0:
        dp[i] = min(dp[i], dp[i - x] + 1)
        x *= 6
    x = 9
    while i - x >= 0:
        dp[i] = min(dp[i], dp[i - x] + 1)
        x *= 9

print(dp[N])

Submission status: Accepted

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

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

print(dp[N])

Submission status: Accepted

Solution code:
import sys
import heapq
from math import ceil, floor
from collections import deque, Counter, defaultdict
from fractions import gcd
input = lambda: sys.stdin.readline().rstrip()

def eprint(s):
    sys.stderr.write('DEBUG: {}'.format(s))
    return

def shortest_path(s, n, w, es):
    d = [float("inf")]*n
    d[s] = 0
    while True:
        update = False
        for p,q,r in es:
            if d[p] != float("inf") and d[q] > d[p] + r:
                d[q] = d[p] + r
                update = True
        if not update:
            break
    return d

def main():
    n = int(input())
    es = list()
    cnt = 0
    ps = [1, 6, 9, 36, 81, 216, 729, 1296, 6561, 7776, 46656, 59049]
    ps.sort()
    for i in range(n+1):
        for j in ps:
            if i + j <= n:
                es.append([i, i+j, 1])
                cnt += 1
            else:
                break

    reslut = shortest_path(0,n+1, cnt, es)
    print(reslut[n])
    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
ary = [1]
x = 1
for i in range(6):
	x *= 6
	ary.append(x)
x = 1
for i in range(5):
	x *= 9
	ary.append(x)
ary.sort()

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

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

Submission status: Accepted

Solution code:
n = int(input())
ary = [1]
x = 1
for i in range(6):
	x *= 6
	ary.append(x)
x = 1
for i in range(5):
	x *= 9
	ary.append(x)
ary.sort()

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

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

Submission status: Accepted

Solution code:
# import bisect
# from collections import Counter, deque
# import copy
# from fractions import gcd
# from functools import reduce
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np
import sys

sys.setrecursionlimit(10 ** 5 + 10)


# input = sys.stdin.readline

def resolve():
    N = int(input())
    M = N//9  # Nを変更したくなければ

    # 10進数表記のxをn進数表記にして返す
    def nary_notation(x, n):
        bi = ''
        while x != 0:
            # abs(n)で割った余りをbiに格納
            # nが負の時は不明
            bi += str(x % abs(n))
            if n < 0:
                x = -(-x // n)
            else:
                x = x // n
        # 位取りが逆順になっているため
        cnt = 0
        for j in bi:
            cnt += int(j)
        return cnt

    ans = 10 ** 9
    for i in range(M + 1):
        ans = min(nary_notation(9*i, 9) + nary_notation(N - (9 *i), 6), ans)
    print(ans)


resolve()

Submission status: Accepted

Solution code:
n=int(input())
A=[100]*(10**5+4)
A[0]=0
B=[1,6,6**2,6**3,6**4,6**5,6**6,9,9**2,9**3,9**4,9**5]
for i in range(1,n+2):
  A[i]=min(A[i-B[j]] for j in range(12))+1
print(A[n])

Submission status: Accepted

Solution code:
N = int(input())
dp = [i for i in range(100000+1)]
arr_6 = [6**i for i in range(11)]
arr_9 = [9**i for i in range(11)]
for index in range(100000+1):
  tmp = [v for v in arr_6 if index >= v]
  if len(tmp) != 0:
    tmp = tmp[-1]
    dp[index] = min(dp[index], dp[index - tmp] + 1)

  tmp = [v for v in arr_9 if index >= v]
  if len(tmp) != 0:
    tmp = tmp[-1]
    dp[index] = min(dp[index], dp[index - tmp] + 1)

print(dp[N])

Submission status: Accepted

Solution code:
dp=[100000 for i in range(100001)]
dp[0]=0
l=[1]
i=6
while i<=100000:
    l.append(i)
    i*=6
i=9
while i<=100000:
    l.append(i)
    i*=9
for i in range(1,100001):
    for j in l:
        if j<=i and dp[i-j]+1<dp[i]:
            dp[i]=dp[i-j]+1
print(dp[int(input())])

Submission status: Accepted

Solution code:
n = int(input())
base = []
i = 1
j = 1
i_6 = 6
i_9 = 9
dp = [float("inf")]*(n+1)
dp[0] = 0

base.append(1)

while i_6<=n:
  i_6 = 6**i
  base.append(i_6)
  i = i+1
  
while i_9<=n:
  i_9 = 9**j
  base.append(i_9)
  j = j+1
  
base.sort()
base_n = len(base)

for i  in range(1,n+1):
  for j in range(base_n):
    if 0 > i-base[j]:
      break
     
    temp = dp[i-base[j]]
    if temp < dp[i]:
      dp[i] = temp + 1
      
    
print(dp[n])

Submission status: Accepted

Solution code:
N=int(input())
DP=[0]*(N+1)
DP[1]=1
six=[]
nine=[]
numbersix=6
while numbersix<=N:
    six.append(numbersix)
    numbersix*=6
numbernine=9
while numbernine<=N:
    nine.append(numbernine)
    numbernine*=9
answers=six+nine

if N<=5:
    print(N)
elif N==6:
    print(1)
else:
    for a in range(2,N+1):
        kotae=[b for b in answers if b<=a]
        kouho=[DP[a-1]+1]
        for z in kotae:
            y=DP[a-z]+1
            kouho.append(y)
        DP[a]=min(kouho)
    print(DP[-1])

Submission status: Accepted

Solution code:
# abc099 c

import itertools
from math import factorial
import sys
import heapq
from collections import Counter
from collections import deque
from fractions import gcd
from functools import reduce

sys.setrecursionlimit(4100000)
INF = 1 << 60
MOD = 10 ** 9 + 7

# ここから書き始める
n = int(input())
dp = [INF] * (n + 1)
for i in range(n + 1):
    dp[i] = i
for i in range(n + 1):
    # for l in range(1, i + 1):
    #     dp[i] = min(dp[i], dp[i - l] + l)
    j = 1
    while i - pow(6, j) >= 0:
        dp[i] = min(dp[i], dp[i - pow(6, j)] + 1)
        j += 1
    k = 1
    while i - pow(9, k) >= 0:
        dp[i] = min(dp[i], dp[i - pow(9, k)] + 1)
        k += 1
# print(dp)
print(dp[-1])

Submission status: Accepted

Solution code:
n = int(input())
res = n
for i in range(n+1):
    cnt = 0
    tmp = i
    while tmp > 0:
        t = 0
        while 6**t <= tmp:
            t += 1
        tmp -= 6**(t-1)
        cnt += 1
    tmp = n-i
    while tmp > 0:
        t = 0
        while 9**t <= tmp:
            t += 1
        tmp -= 9**(t-1)
        cnt += 1
    res = min(res, cnt)
print(res)

Submission status: Accepted

Solution code:
N = int(input())

dp = [float("inf") for _ in range(100010)]
dp[0] = 0

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

Submission status: Accepted

Solution code:
# Problem C - Strange Bank

# input
N = int(input())

# initialization
INF = 10**15
dp = [INF] * (N+1)

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

    # 9 yen
    if i>=9:
        nine_count = 0
        tmp = 1
        while tmp*9<=i:
            nine_count += 1
            tmp *= 9
        dp[i] = min(dp[i], dp[i-9**nine_count]+1)

    # 6 yen
    if i>=6:
        six_count = 0
        tmp = 1
        while tmp*6<=i:
            six_count += 1
            tmp *= 6
        dp[i] = min(dp[i], dp[i-6**six_count]+1)

    # 1 yen
    if i>=1:
        dp[i] = min(dp[i], dp[i-1]+1)

# output
print(dp[N])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    from functools import lru_cache
    from sys import setrecursionlimit
    setrecursionlimit(10**6)
    N = int(input())
    withdraws = []
    for i in range(N):
        if N < 9**i:
            break
        withdraws.append(9**i)
    for i in range(1, N):
        if N < 6**i:
            break
        withdraws.append(6**i)
    withdraws.sort(reverse=True)

    @lru_cache(maxsize=100000)
    def rec(cur):
        if cur == 0:
            return 0
        ret = cur
        for draw in withdraws:
            if cur < draw:
                continue
            ret = min(ret, rec(cur - draw) + 1)
        return ret

    print(rec(N))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n = int(input())

coin = [1]
for i in range(1, 6):
    coin.append(pow(9, i))
for i in range(1, 7):
    coin.append(pow(6, i))

inf = pow(10, 10)
dp = [inf for _ in range(n + 1)]
dp[0] = 0
for i in range(1, n + 1):
    for j in range(len(coin)):
        if i - coin[j] >= 0:
            dp[i] = min(dp[i], dp[i - coin[j]] + 1)
print(dp[n])

Submission status: Accepted

Solution code:
def main():
    N = int(input())

    withdraws = []
    for i in range(N):
        if N < 9**i:
            break
        withdraws.append(9**i)
    for i in range(1, N):
        if N < 6**i:
            break
        withdraws.append(6**i)
    withdraws.sort(reverse=True)
    W = len(withdraws)

    dp = [[10**9 for i in range(N + 1)] for j in range(W + 1)]
    dp[0][0] = 0
    for i in range(1, W+1):
        for n in range(N + 1):
            if n - withdraws[i-1] >= 0:
                dp[i][n] = min(dp[i-1][n], dp[i][n - withdraws[i-1]] + 1)
            else:
                dp[i][n] = dp[i-1][n]
    print(dp[W][N])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    N = int(input())

    withdraws = []
    for i in range(N):
        if N < 9**i:
            break
        withdraws.append(9**i)
    for i in range(1, N):
        if N < 6**i:
            break
        withdraws.append(6**i)
    withdraws.sort(reverse=True)
    W = len(withdraws)

    dp = [[10**9 for i in range(N + 1)] for j in range(W + 1)]
    dp[0][0] = 0
    for i in range(1, W+1):
        for n in range(N + 1):
            if n - withdraws[i-1] >= 0:
                dp[i][n] = min(dp[i-1][n], dp[i][n],
                               dp[i][n - withdraws[i-1]] + 1)
            else:
                dp[i][n] = min(dp[i-1][n], dp[i][n])
    print(dp[W][N])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def rec(n, x):
        d, m = divmod(n, x)
        if d: return m + rec(d, x)
        else: return m

ans = n = int(input())
for i in range(n+1):
        ans = min(ans, rec(i, 6)+rec(n-i, 9))
print(ans)

Submission status: Accepted

Solution code:
import sys


def solve():
    input = sys.stdin.readline
    N = int(input())
    DP = [int(i) for i in range(N + 1)]
    ni = 9
    for i in range(N):
        if ni > N: break
        for j in range(N - ni + 1):
            DP[j + ni] = min(DP[j + ni], DP[j] + 1)
        ni *= 9
    six = 6
    for i in range(N):
        if six > N: break
        for j in range(N - six + 1):
            DP[j + six] = min(DP[j + six], DP[j] + 1)
        six *= 6
    print(DP[N])
    
    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
N = int(input())

a = [1]
n6 = 6
while n6 <= 100000:
    a.append(n6)
    n6 *= 6
n9 = 9
while n9 <= 100000:
    a.append(n9)
    n9 *= 9

#dp[i]=ちょうどi円払う場合に最小の操作回数
dp = [10**9] * (N+100010)
dp[0] = 0

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

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

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

for i in range(1,n+1):
    c = dp[i-1]
    for j in range(6):
        a = i-9**j if i-9**j >= 0 else i-1
        c = min(c, dp[a])
    for j in range(7):
        a = i-6**j if i-6**j >= 0 else i-1
        c = min(c, dp[a])
    dp[i] = c+1

print(dp[n])

Submission status: Accepted

Solution code:
n=int(input())

l=[1]
l_9=[pow(9,i) for i in range(1,7)]
l_6=[pow(6,i) for i in range(1,8)]
l+=l_9
l+=l_6
l.sort(reverse=True)
dp=[10**9 for i in range(n+1)]

dp[0]=0

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

Submission status: Accepted

Solution code:

#D

def sixnine(m):
    ret=[]
    for n in [6,9]:
        tmp=1
        while True:
            tmp*=n
            if tmp<=m:
                ret.append(tmp)
            else:
                break
    ret.sort()
    return ret


N=int(input())
dp=[0 for i in range(N+1)]
for i in range(1,N+1):
    if i<=5:
        dp[i]=i
        continue
    sn=sixnine(i)
    if i in sn:
        dp[i]=1
        continue
    ans=10**19
    for k in sn:
        ans=min(ans,dp[k]+dp[i-k])
    dp[i]=ans
# print(dp)
print(dp[-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
N = int(input())
bl = [False]*(N+1)
memo = [N]*(N+1)

def f(n):
    if bl[n]:
        return memo[n]
  
    m = N

    i = 0
    while n >= 6**i:
        if n == 6**i:
            bl[n] = True
            memo[n] = 1
            return 1
        m = min(m, f(n-6**i)+1)
        i += 1

    i = 1
    while n >= 9**i:
        if n == 9**i:
            bl[n] = True
            memo[n] = 1
            return 1
        m = min(m, f(n-9**i)+1)
        i += 1
    
    bl[n] = True
    memo[n] = m
    return m

print(f(N))

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

n = INT()
arr = [1]
arr.extend([pow(9, i) for i in range(1, 7)])
arr.extend([pow(6, i) for i in range(1, 8)])
arr.sort(reverse=True)
dp = [inf for _ in range(n + 1)]
dp[0] = 0
for i in range(1, n + 1):
    for j in arr:
        if i - j >= 0:
            dp[i] = min(dp[i], dp[i - j] + 1)
print(dp[n])

Submission status: Accepted

Solution code:
N = int(input())

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

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

ans = 10**18
for i, c in enumerate(dp):
    ans = min(ans, N - i + c)
print(ans)

Submission status: Accepted

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

info = [[1, 1]]
for i in range(1, 10):
    info.append([6**i, 1])
for i in range(1, 10):
    info.append([9**i, 1])
    
for i in range(n):
    for w, v in info:
        if i + w >= n + 1:
            continue
        dp[i + w] = min(dp[i] + 1, dp[i + w])
print(dp[-1])

Submission status: Accepted

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

for n in range(N+1):
  i = 0
  while n >= 6**i:
    if n == 6**i:
      dp[n] = 1
    else:
      dp[n] = min(dp[n], dp[n-6**i]+1)
    i += 1
                
  i = 1
  while n >= 9**i:
    if n == 9**i:
      dp[n] = 1
    else:
      dp[n] = min(dp[n], dp[n-9**i]+1)
    i += 1

print(dp[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:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-


def div(n, t):
    if n < t:
        return n
    else:
        return div(n // t, t) + n % t


def main():
    N = int(input())
    print(min(div(i, 6) + div(N - i, 9) for i in range(N + 1)))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())

DP = [100010]*(N+1)
DP[0] = 0

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

print(DP[-1])

Submission status: Accepted

Solution code:
n = int(input())

six = []
s = 6
while s <= n:
    six.append(s)
    s *= 6
s = 9
while s <= n:
    six.append(s)
    s *= 9
six.sort()
dp = [i for i in range(n+13)]
for s in six:
    for i in range(n-s+1):
        if dp[i] + 1 < dp[i+s]:
            dp[i+s] = dp[i] + 1

print(dp[n])

Submission status: Accepted

Solution code:
n = int(input())
dp = [0 for x in range(n+1)]
key = 1
while key <= n:
  key *= 6
while key > 1:
  for j in range(n+1):
    if j == 0 or dp[j]:
      if j+key <= n:
        if dp[j+key]:
          dp[j+key] = min([dp[j]+1, dp[j+key]])
        else:
          dp[j+key] = dp[j]+1
  key //= 6

key = 1
while key <= n:
  key *= 9
while key > 1:
  for j in range(n+1):
    if j == 0 or dp[j]:
      if j+key <= n:
        if dp[j+key]:
          dp[j+key] = min([dp[j]+1, dp[j+key]])
        else:
          dp[j+key] = dp[j]+1
  key //= 9

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

print(dp[n])

Submission status: Accepted

Solution code:
import sys

# N
n = int(input())

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())
a = [1]
b = 6
while True:
    a.append(b)
    b *= 6
    if b > 10 ** 5:
        break
b = 9
while True:
    a.append(b)
    b *= 9
    if b > 10 ** 5:
        break
a.sort()
a = [0] + a
dp = [[0 for _ in range(n + 1)] for _ in range(len(a))]
for i in range(n + 1):
    dp[0][i] = 10 ** 5
for i in range(1, len(a)):
    for j in range(1, n + 1):
        if a[i] > j:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = min(dp[i - 1][j], dp[i][j - a[i]] + 1)
print(dp[len(a) - 1][n])