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

r = n

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

print(r)

Submission status: Accepted

Solution code:
# f(cu) = cu円取り出すのに必要な最小回数
import numpy as np

N = int(input())

dp = dict()
dp[0] = 0
for n in range(1, N+1):
  ans = dp[n-1] + 1
  
  x = 6
  while x <= n:
    ans = min(ans, dp[n-x]+1)
    x *= 6
  
  x = 9
  while x <= n:
    ans = min(ans, dp[n-x]+1)
    x *= 9
    
  dp[n] = ans
  
print(dp[N])

Submission status: Accepted

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

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

print(dp[N])

Submission status: Accepted

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

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

print(dp[N])

Submission status: Accepted

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

for i in range(N+1):
    cc = 0
    t = i
    while t > 0:
        cc += int(t % 6)
        t //= 6
    t = N - i
    while t > 0:
        cc += int(t % 9)
        t //= 9
    res = min(res, cc)

print(int(res))

Submission status: Accepted

Solution code:
n=int(input())
dp=[10**5]*(n+1)
dp[0]=0
for i in range(n+1):
    pow=1
    while pow<=n:
        dp[i]=min(dp[i],dp[i-pow]+1)
        pow*=6
    pow=1
    while pow<=n:
        dp[i]=min(dp[i],dp[i-pow]+1)
        pow*=9
print(dp[n])

Submission status: Accepted

Solution code:
N=int(input())

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

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

Submission status: Accepted

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

k = 0
while(6**k <= N):
    enable.add(6**k)
    k += 1
k = 0
while(9**k <= N):
    enable.add(9**k)
    k += 1


enable = list(enable)
enable.sort()

ans = 10**9
l = len(enable)
for i in range(l):
    n = N
    tmp = 0
    while(n != 0):
        id = bisect.bisect_right(enable, n) - 1
        if id != 0 and n % enable[id] > 2 and n % enable[id] < 6:
            id -= 1
        n -= enable[id]
        tmp += 1
    enable.pop()

    ans = min(tmp, ans)

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
X = [0]
for n in range(1,N+1):
    x = X[-1]+1

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

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

    X.append(x)

print(X[N])

Submission status: Accepted

Solution code:
n=int(input())
num6=6
num9=9
l=[]
while num6<=n:
  l.append(num6)
  num6*=6
while num9<=n:
  l.append(num9)
  num9*=9
count=[0,1,2,3,4,5,1,2,3,1,2,3]
for i in range(12,n+1):
  min=100000
  for j in l:
    if i-j<0:
      pass
    else:
      if min>count[i-j]+1:
        min=count[i-j]+1
  count.append(min)
print(count[n])

Submission status: Accepted

Solution code:
n=int(input())
l6=[]
l9=[]
num6=6
num9=9
while num6<=n:
  l6.append(num6)
  num6*=6
while num9<=n:
  l9.append(num9)
  num9*=9
count=[0,1,2,3,4,5,1,2,3,1,2,3]
for i in range(12,n+1):
  min=100000
  for j in l6:
    if i-j<0:
      pass
    else:
      if min>count[i-j]+1:
        min=count[i-j]+1
  for j in l9:
    if i-j<0:
      pass
    else:
      if min>count[i-j]+1:
        min=count[i-j]+1
  count.append(min)
print(count[n])

Submission status: Accepted

Solution code:
N = int(input())

ans = 10 ** 5
for i in range(N+1):
    j = N-i
    count = 0
    while i > 0:
        count += i % 6
        i //= 6
    while j > 0:
        count += j % 9
        j //= 9
    ans = min(ans, count)

print(ans)

Submission status: Accepted

Solution code:
import sys

N = int(input())
if N < 6:
	print(N)
	sys.exit()
elif N < 9:
	print(1+(N-6))
	sys.exit()

def Base_10_to_n(X, n):
    X_dumy = X
    out = ''
    while X_dumy>0:
        out = str(X_dumy%n)+out
        X_dumy = int(X_dumy/n)
    return out

ans = float("inf")

for i in reversed(range((N//9)+1)):
	t = N - 9*i
	t_6, t_1 = divmod(t, 6)

	time_9 = Base_10_to_n(i, 9)
	time_6 = Base_10_to_n(t_6, 6)

	ans = min(ans, sum(list(map(int, time_9))) + sum(list(map(int, time_6))) + t_1)

print(ans)

Submission status: Accepted

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

dp = [10 ** 9 + 7] * (N + 1)
dp[0] = 0
for n in range(N+1):
    pow = 1
    while pow <= n:
        dp[n] = min(dp[n], dp[n-pow] + 1)
        pow *= 6
    pow = 1
    while pow <= n:
        dp[n] = min(dp[n], dp[n-pow] + 1)
        pow *= 9

print(dp[-1])

Submission status: Accepted

Solution code:
def main():
    n=int(input())
    ln=[1,6,9,36,81,216,729,1296,6561,7776,46656,59049]
    dp=[0 for i in range(n+1)]
    dp[1] = 1
    for i in range(2,n+1):
        lnt = [ln[j] for j in range(12) if i >= ln[j]]
        tdp=[]
        for slnt in lnt:
            tdp.append(dp[i-slnt])
        dp[i]=min(tdp)+1
    return dp[-1]

print(main())

Submission status: Accepted

Solution code:
n = int(input())
dp=[0]*(n+1)
dp[1]=1
j,k=1,1
for i in range(2,n+1):
    if i==6*j:
        j*=6
    if i==9*k:
        k*=9
    dp[i]=min(dp[i-k],dp[i-j],dp[i-1])+1
print(dp[n])

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
N = int(input())


candidates = []
for base in [6, 9]:
    n = base
    while n <= N:
        candidates.append(n)
        n *= base



# DP
counts = [i for i in range(N + 1)]
for c in candidates:
    for i in range(c, N+1):
        counts[i] = min(counts[i], counts[i-c] + 1)

print(counts[N])

Submission status: Accepted

Solution code:
n = int(input())
dp = [float("inf")] * (n+1)
dp[0] = 0

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

print(dp[n])

Submission status: Accepted

Solution code:
import bisect
n = int(input())
add_num = 1
draw_money = []
while add_num <= 10 ** 5:
    draw_money.append(add_num)
    add_num *= 6
    
add_num = 1
while add_num <= 10 ** 5:
    draw_money.append(add_num)
    add_num *= 9

#重複を削除
draw_money = list(set(draw_money))
ans = 0
draw_money.sort()
# dp[i] = i円引き出すのに必要な最小操作
dp = [10000000] * (n + 1)
dp[0] = 0
for i in range(1,n + 1):
    for j in draw_money:
        if  i - j >= 0:
            dp[i] = min(dp[i - 1] + 1, dp[i - j] + 1,dp[i])
        else:
            dp[i] = min(dp[i-1] + 1, dp[i])

print(dp[n])

Submission status: Accepted

Solution code:
from bisect import bisect

N=int(input())

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

Lis=list(set(Lis))
Lis.sort()

DP=[100001]*(N+1)

DP[0]=0

for i in range(1,N+1):
    temp=[]
    idx=bisect(Lis,i)
    for j in range(idx):
        tem=1+DP[i-Lis[j]]
        temp.append(tem)
    DP[i]=min(temp)
print(DP[N])

Submission status: Accepted

Solution code:
n = int(input())
a = 6
b = [1]
b.append(a)
while a <= 100000:
	a *= 6
	b.append(a)
c = 9
b.append(c)
while c <= 100000:
	c *= 9
	b.append(c)
b.sort()
INF = 10**7
dp = [INF]*100001
dp[0] = 0
for i in range(100001):
	for j in b:
		if i + j > 100000:
			continue
		dp[i+j] = min(dp[i]+1, dp[i+j])
print (dp[n])

Submission status: Accepted

Solution code:
INF = 110000

n = int(input())
dp = [ INF for _ in range(n+10)]
dp[0] = 0

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

Submission status: Accepted

Solution code:
n=int(input())
inf=10**10
dp=[inf]*(n+1)
dp[0]=0
dp[1]=1
m6=[]
m9=[]
j6=1
while j6<=n:
    m6.append(j6)
    dp[j6]=1
    j6*=6
j9=1
while j9<=n:
    m9.append(j9)
    dp[j9]=1
    j9*=9
for i in range(1,n+1):
    if dp[i]==1:
        continue
    for j in m6:
        if i-j>=0:
            dp[i]=min(dp[i],dp[i-j]+1)
    for k in m9:
        if i-k>=0:
            dp[i]=min(dp[i],dp[i-k]+1)
print(dp[n])

Submission status: Accepted

Solution code:
n=int(input())
INF=2<<60
dp=[INF]*(2*10**5)
money_list=[1]+[6**i for i in range(1, 7)]+[9**i for i in range(1, 6)]
money_list.sort()
for m in money_list:
    dp[m-1]=1
for i in range(n):
    for m in money_list:
        dp[i+m]=min(dp[i+m], dp[i]+1)
print(dp[n-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
list6 = [6**i for i in range(7)]
list9 = [9**i for i in range(6)]
m = {}
def ans(n):
    if n <= 5:
        return n
    elif n in m:
        return m[n]
    else:
        m6 = max(i for i in list6 if i <= n)
        m9 = max(i for i in list9 if i <= n)
        l6 = n - m6
        l9 = n - m9
        m[n] = min(ans(l6)+1,ans(l9)+1)
        return m[n]
print(ans(n))

Submission status: Accepted

Solution code:
import bisect
 
x = int(input())
six_list = [6 ** i for i in range(7)]
nine_list = [9 ** i for i in range(6)]
 
 
def six_nine(n):
    if n == 0:
        return 0
    else:
        six = six_list[bisect.bisect_right(six_list, n) - 1]
        nine = nine_list[bisect.bisect_right(nine_list, n) - 1]
        return min(n // six + six_nine(n % six), 1 + six_nine(n - nine))
 
 
print(six_nine(x))

Submission status: Accepted

Solution code:
def main():
    # 1回の操作で引き出す可能性のある金額リスト
    cash = [1]
    n = int(input())
    # nを超えない範囲で6,9の累乗を追加する
    for i in range(1, n):
        if 6 ** i > n:
            break
        cash.append(6 ** i)
    for i in range(1, n):
        if 9 ** i > n:
            break
        cash.append(9 ** i)
    cash.sort()
    # ans[i]: i円ちょうど引き出すのに必要な操作の最小回数
    ans = [float('inf')] * (n + 1)
    ans[0] = 0
    for i in range(1, n + 1):
        for j in cash:
            if i - j < 0:
                break
            else:
                ans[i] = min(ans[i], ans[i - j] + 1)
    print(ans[n])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# 1回の操作で引き出す可能性のある金額リスト
cash = [1]
n = int(input())
# nを超えない範囲で6,9の累乗を追加する
for i in range(1, n):
    if 6 ** i > n:
        break
    cash.append(6 ** i)
for i in range(1, n):
    if 9 ** i > n:
        break
    cash.append(9 ** i)
cash.sort()
# ans[i]: i円ちょうど引き出すのに必要な操作の最小回数
ans = [float('inf')] * (n + 1)
ans[0] = 0
for i in range(1, n + 1):
    for j in cash:
        if i - j < 0:
            break
        else:
            ans[i] = min(ans[i], ans[i - j] + 1)
print(ans[n])

Submission status: Accepted

Solution code:
cash = [1]
n = int(input())
ans = [float('inf')] * (n + 1)
for i in range(1, n):
    if 6 ** i > n:
        break
    cash.append(6 ** i)
for i in range(1, n):
    if 9 ** i > n:
        break
    cash.append(9 ** i)
cash.sort()
ans[0] = 0
for i in range(1, n + 1):
    for j in cash:
        if i - j < 0:
            break
        else:
            ans[i] = min(ans[i], ans[i - j] + 1)
print(ans[n])

Submission status: Accepted

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

ans = []
for i in range(n+1):
    cnt6 = i
    cnt9 = n - i
    ans6 = 0
    ans9 = 0
    
    while cnt6 > 0:
        sho = 6**math.floor(math.log(cnt6, 6))
        ans6 += cnt6//sho
        cnt6= cnt6%sho
        
    while cnt9 > 0:
        if cnt9 != 59049:
            sho2 = 9**math.floor(math.log(cnt9, 9))
        else:
            sho2=59049
        ans9 += cnt9//sho2
        cnt9 = cnt9%sho2
        
    ans.append(ans6+ans9)
    sho, sho2 = 0, 0
        
print(min(ans))

Submission status: Accepted

Solution code:
coins=[1]
n=int(input())
for i in range(20):
    coins.append(6**i)
for i in range(20):
    coins.append(9**i)
dp=[10**9]*(n+1)
dp[0]=0 
for c in coins:
    for j in range(n+1):
        if c<=j:
            dp[j]=min(dp[j],dp[j-c]+1)
print(dp[n])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)

n=int(input())
l=[]
for i in range(1,10):
    if 6**i>n:
        break
    l.append(6**i)
for i in range(1,10):
    if 9**i>n:
        break
    l.append(9**i)

l.sort()

if n in l:
    print(1)
    exit()

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

def dfs(n):
    if dp[n]!=inf:
        return dp[n]
    if n<6:
        return n
    m=inf
    for d in l:
        if n-d<0:
            break
        m=min(m,dfs(n-d)+1)
    dp[n]=m
    return m

print(dfs(n))

Submission status: Accepted

Solution code:
n=int(input())
b=[1,6,36,216,1296,7776,46656]
q=[9,81,729,6561,59049]
d=[100000]*(n+1)
d[0]=0
for i in range(n):
  for j in b:
    if i+j<=n:
      d[i+j]=min(d[i+j],d[i]+1)
  for k in q:
    if i+k<=n:
      d[i+k]=min(d[i+k],d[i]+1)
print(d[n])

Submission status: Accepted

Solution code:
N = int(input())

one = [1]
six_multi = [6, 6**2, 6**3, 6**4, 6**5, 6**6]
nine_multi = [9, 9**2, 9**3, 9**4, 9**5]
deposit = one + six_multi + nine_multi

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

for i in range(0, N):
    for d in range(len(deposit)):
        if i+deposit[d] <= N:
            dp[i+deposit[d]] = min(dp[i+deposit[d]], dp[i] + 1)

print(dp[N])

Submission status: Accepted

Solution code:
import math

import numpy as np


def get_choices(n, p):
    choices = set()
    for i in range(1, n):
        powered = int(math.pow(p, i))
        if powered <= n:
            choices.add(powered)
        else:
            break
    return choices


def main(n):
    choices = {1}
    choices |= get_choices(n, 6)
    choices |= get_choices(n, 9)

    dp = np.full(shape=n + 1, fill_value=n, dtype=int)
    dp[0] = 0
    dp[1] = 1

    for i in range(1, n + 1):
        if i in choices:
            dp[i] = 1
        else:
            for choice in choices:
                pre_index = i - choice
                if pre_index > 0:
                    if dp[i] > dp[pre_index] + 1:
                        dp[i] = dp[pre_index] + 1
                else:
                    break

    return dp[-1]


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

Submission status: Accepted

Solution code:
n = int(input())
dp = [10**6] * (n+1)
dp[0] = 0
for i in range(1,n+1):
  c = 1
  d = 1
  dp[i] = min(dp[i],dp[i-1]+1)
  while True:
    if i - 6**c >= 0:
      dp[i] = min(dp[i],dp[i-6**c]+1)
    else:
      break
    c += 1
  while True:
    if i - 9**d >= 0:
      dp[i] = min(dp[i],dp[i-9**d]+1)
    else:
      break
    d += 1
print(dp[n])

Submission status: Accepted

Solution code:
from bisect import bisect_right
N = int(input())
unit = [1]
for b in [6,9]:
    u = b
    while u <= N:
        unit.append(u)
        u *= b
unit.sort()
Nu = len(unit)

def dfs(n, i, pk, ans):
    if N - n >= (ans-i)*unit[pk]:
        return ans
    sk = bisect_right(unit, N-n, 0, pk+1) - 1
    for k in range(sk, -1, -1):
        c = n + unit[k]
        if c == N:
            if i + 1 < ans:
                return i + 1
        else:
            t = dfs(c, i+1, k, ans)
            if t < ans:
                ans = t
    return ans

print(dfs(0,0,Nu-1,N))

Submission status: Accepted

Solution code:
from bisect import bisect_right
N = int(input())
unit = [1]
for b in [6,9]:
    u = b
    while u <= N:
        unit.append(u)
        u *= b
unit.sort()
Nu = len(unit)

ans = N
state_pool = [(0, 0, 0, Nu-1)]
while state_pool:
    n, i, parent, pk = state_pool.pop()
    if N - n >= (ans-i)*unit[pk]:
        continue
    elif pk > 0 and i > 0:
        state_pool.append((parent+unit[pk-1], i, parent, pk-1))

    k = bisect_right(unit, N-n, 0, pk+1) - 1
    c = n + unit[k]
    if c == N:
        if i + 1 < ans:
            ans = i + 1
    else:
        state_pool.append((c, i+1, n, k))
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect
n=int(input())
lst=[0,1]
for i in range(1,8):
    lst.append(6**i)
for i in range(1,7):
    lst.append(9**i)
lst.sort()
inf=float("inf")
dp=[[inf]*(n+1) for i in range(15)]
for i in range(15):
    dp[i][0]=0
for i in range(1,15):
    a=lst[i]
    if a>n:
        print(dp[i-1][n])
        break
    for j in range(1,a):
        dp[i][j]=dp[i-1][j]
    for j in range(a,n+1):
        dp[i][j]=min(dp[i-1][j],dp[i-1][j-a]+1,dp[i][j-a]+1)
else:
    print(dp[14][n])

Submission status: Accepted

Solution code:
a=[1,6,36,216,1296,7776,46656,9,81,729,6561,59049]
n=int(input())
dp=[0]*(n+1)
dp[0]=0#0円は0通り
for i in range(1,n+1):
    s=[]
    for j in a:
        if i-j<0:
            continue
        s.append(dp[i-j])
    dp[i]=min(s)+1
print(dp[-1])

Submission status: Accepted

Solution code:
from bisect import bisect_right
N = int(input())
unit = [1]
for b in [6,9]:
    u = b
    while u <= N:
        unit.append(u)
        u *= b
unit.sort()
Nu = len(unit)

ans = N
state_pool = [(0, 0, Nu-1)]
while state_pool:
    n, i, pk = state_pool.pop()
    if N - n >= (ans-i)*unit[pk]:
        continue
    sk = bisect_right(unit, N-n, 0, pk+1)
    for k in range(sk):
        u = unit[k]
        c = n + u
        if c == N:
            if i + 1 < ans:
                ans = i + 1
        else:
            state_pool.append((c, i+1, k))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
memo = [N]*(N+1)
unit = [1]
for b in [6,9]:
    u = b
    while u <= N:
        unit.append(u)
        u *= b
unit.sort()
cur = set({0})
for i in range(1,N+1):
    prev = cur
    cur = set()
    for p in prev:
        for u in unit:
            c = p + u
            if c == N:
                print(i)
                exit()
            elif c > N:
                break
            elif memo[c] > i:
                cur.add(c)
                memo[c] = i

Submission status: Accepted

Solution code:
import sys

#+++++

def nn(val, count, aal):
	#pa((val,count,aal))
	if aal[val] >= 0:
		return aal[val]
	
	ll=[1]
	i=1
	while 6**i <= val:
		ll.append(6**i)
		i+=1
	
	i=1
	while 9 ** i <= val:
		ll.append(9**i)
		i+=1
	
	ll=ll[::-1]
	min_v = val
	for l in ll:
		temp = nn(val-l, count+1,aal)
		min_v = min(min_v,temp)
	
	aal[val]=min_v+1
	return min_v+1
	
	
		
def main():
	N = int(input())
	al=[-1]*(N+1)
	al[0:6]=[0,1,2,3,4,5]
	#print(al[0:10])
	ans=nn(N,0,al)

	print(ans)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
N=int(input())

def saiki(tgt,i,count,ans):
    #print(tgt,i,count,ans,temp[i])

    if i==0 or tgt==0:
        ans=min((tgt+count),ans)
        return ans
        
    num=tgt//temp[i]
    while num>=0:
        ans=saiki(tgt-num*temp[i],i-1,count+num,ans)
        if ans<(count+num):
            return ans
        num-=1
    return ans

temp=[1]
n=1
while N>=6**n:
    temp.append(6**n)
    n+=1
    
n=1
while N>=9**n:
    temp.append(9**n)
    n+=1

temp.sort()
#print(temp)

print(saiki(N,len(temp)-1,0,10**9))

Submission status: Accepted

Solution code:
import math
n = int(input())
six_ls = []
nine_ls = []
def nine_plus(base):
    "base : list of int"
    kuriagari = 1
    for num in range(len(base) - 1, -1, -1):
        if base[num] + kuriagari >= 9:
            base[num] = 0
            continue
        else:
            base[num] += kuriagari
            break
    return base

def six_plus(base):
    "base : list of int"
    kuriagari = 1
    for num in range(len(base) - 1, -1, -1):
        if base[num] + kuriagari >= 6:
            base[num] = 0
            continue
        else:
            base[num] += kuriagari
            break
    return base

six_sinsu = [0 for i in range(math.floor(math.log(n, 6)) + 2)]
nine_sinsu = [0 for i in range(math.floor(math.log(n, 9)) + 2)]

for i in range(n+1):
    six_ls.append(sum(six_sinsu))
    nine_ls.append(sum(nine_sinsu))
    six_sinsu = six_plus(six_sinsu)
    nine_sinsu = nine_plus(nine_sinsu)
hoge = [a + b for a, b in zip(six_ls, nine_ls[::-1])]
print(min(hoge))

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 = t//6

  s = n-i
  while s>0:
    c += s%9
    s = s//9
  ans = min(ans,c)
  
print(ans)

Submission status: Accepted

Solution code:
import math

N = int(input())
s = [6 ** i for i in range (0,7)]
q = [9 ** j for j in range (0,6)]
m = {}

def f(x):
  if x <= 5:
    return x
  elif x in m:
    return m[x]
  else:
    m_s = max(i for i in s if i <= x)
    m_q = max(j for j in q if j <= x)
    ms = x - m_s
    mq = x - m_q
    m[x] = min(f(ms)+1,f(mq)+1)
    return m[x]
print(f(N))

Submission status: Accepted

Solution code:
import sys


def slove():
    input = sys.stdin.readline
    n = int(input().rstrip('\n'))
    six_l = []
    for i in range(1, 7):
        six_l.append(pow(6, i))
    nine_l = []
    for i in range(1, 6):
        nine_l.append(pow(9, i))

    m_cnt = 10 ** 10
    for i in range(n // 6 + 1):
        t = n
        six = i
        t -= (6 * six)
        nine = t // 9
        t -= (nine * 9)
        cnt = t
        for j in range(len(six_l)):
            if six // six_l[-j-1] > 0:
                cnt += (six // six_l[-j-1])
                six %= six_l[-j-1]
        cnt += six
        for j in range(len(nine_l)):
            if nine // nine_l[-j-1] > 0:
                cnt += (nine // nine_l[-j-1])
                nine %= nine_l[-j-1]
        cnt += nine
        m_cnt = min(m_cnt, cnt)
    print(m_cnt)


if __name__ == '__main__':
    slove()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())

#6,9の累乗のリスト
sixs = []
t = 1
while t <= N:
    sixs.append(t)
    t *= 6

nines = []
t = 1
while t <= N:
    nines.append(t)
    t *= 9


ans = N

#aを６の指数乗、N-aを９の指数乗で支払う
for i in range(N+1):
    cnt = 0
    a = i
    b = N - i
    for num in list(reversed(sixs)):
        
        if a == 0:
            break
        elif a <= 5:
            cnt += a
            a = 0
        else:
            if a >= num:
                #if a == 36: print(a // num, num)
                tmp = a // num
                cnt += tmp
                a -=  num * tmp
                #if i == 36: print(a,cnt)
            else:
                continue
    #if i == 36: print(cnt)
    for num in list(reversed(nines)):
        
        if b == 0:
            break
        elif b <= 8:
            cnt += b
            b = 0
        else:
            if b >= num:
                tmp = b // num
                cnt += tmp
                b -=  num * tmp
            else:
                continue


    ans = min(ans, cnt)

print(ans)

Submission status: Accepted

Solution code:
N = int(input())

# dp = [0] * 100010
dp = []
for i in range(100010):
    dp.append(100000)

dp[0] = 0

for n in range(1, 100000 + 1):
    power = 1  # 1, 6, 36, 216
    while power <= n:
        dp[n] = min(dp[n], dp[n-power]+1)
        power *= 6

    power = 1  # 1, 9, 81, 729
    while power <= n:
        dp[n] = min(dp[n], dp[n-power]+1)
        power *= 9

print(dp[N])
# print(dp[:100])

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(2000000)

def re(r,k,l):
    if k==0:return r
    while(k<l[0]):
        l=l[1:]
    return re(r+1,k-l[0],l)





n=int(input())
i=1
l6=[]
ans=10**5
while(i<=n):
    l6.append(i)
    i*=6
i=1
l9=[]
while(i<=n):
    l9.append(i)
    i*=9
l6.sort(reverse=True)
l9.sort(reverse=True)
for i in range(n+1):
    ans=min(ans,re(0,n-i,l6)+re(0,i,l9))
print(ans)

Submission status: Accepted

Solution code:
inf = float('inf')

N = int(input())

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

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

Submission status: Accepted

Solution code:
n=int(input())
dp=[0]*(n+1)
i=1
while i <= n:
    dp[i]=float('inf')
    p=1
    while p<=i:
        dp[i]=min(dp[i],1+dp[i-p])
        p*=6
    p=1
    while p<=i:
        dp[i]=min(dp[i],1+dp[i-p])
        p*=9
    i+=1
print(dp[n])

Submission status: Accepted

Solution code:
N = int(input())
rec = [0] * (N+1)
for i in range(1,N+1):
    rec[i] = rec[i-1] + 1
    for b in [6,9]:
        u = b
        while u <= i:
            rec[i] = min(rec[i], rec[i-u]+1)
            u *= b
print(rec[N])

Submission status: Accepted

Solution code:
n = int(input())
dp = [float("Inf")]*(n+1)
for i in range(n+1):
    if i < 6:dp[i] = i
    power = 1
    while i >= 6 ** power:
        if dp[i] > dp[i-6**power]+1:dp[i] = dp[i-6**power] + 1
        power += 1
    power = 1
    while i >= 9 ** power:
        if dp[i] > dp[i-9**power]+1:dp[i] = dp[i-9**power] + 1
        power += 1
print(int(dp[n]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
dp=[10**10]*(n+1)
dp[0]=0
for i in range(1,n+1):
  dp[i]=dp[i-1]+1
  x=0
  while 9**(x+1)<=i:
    x+=1
  dp[i]=min(dp[i],dp[i-9**x]+1)
  x=0
  while 6**(x+1)<=i:
    x+=1
  dp[i]=min(dp[i],dp[i-6**x]+1)
print(dp[n])

Submission status: Accepted

Solution code:
'''dp[N] : N円の答え

dp[N] = min(dp[N-1] + 1,
dp[N-6] + 1, dp[N-6^2] + 1,
dp[N-9] + 1, dp[N-9^2] + 1)
'''

N = int(input())

dp = []
for j in range(100000 + 10):
    dp.append(j)

for i in range(100000 + 9):
    s = 6
    n = 9
    while i-s>=0:
        try:

        
            dp[i] = min(dp[i], dp[i-s] + 1)
            s *= 6
        except:
            print('s', i, i-s, s)
    while i-n>=0:
        dp[i] = min(dp[i], dp[i-n] + 1) 
        n *= 9

print(dp[N])

Submission status: Accepted

Solution code:
n = int(input())
six = [1]
nine = [1]
p =1 
while True:
    if 6**p<=n:
        six.append(6**p)
    else:
        break
    if 9**p <=n:
        nine.append(9**p)
    p +=1
six.sort(reverse=True)
nine.sort(reverse=True)
ans = float('inf')
for i in range(n+1):
    count =0
    r = i
    for a in six:
        quot = r//a
        r -= quot*a
        count += quot
        if r ==0:
            break
    r = n - i
    for a in nine:
        quot = r//a
        r -= quot*a
        count += quot
        if r ==0:
            break
    ans = min(ans,count)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

# dp[i]を合計i円引き出すための最小の引き出し回数とする
# 再帰関数で求めようとするとsys.setrecursionlimit(100000)でも再帰関数上限を突破する

square_6_list = []
x = 1
while 6**x <= 10**5:
    square_6_list.append(6**x)
    x += 1

square_9_list = []
x = 1
while 9**x <= 10**5:
    square_9_list.append(9**x)
    x += 1

min_withdrow = [float("inf")]*(N+1)
min_withdrow[0] = 0
min_withdrow[1] = 1

for i in range(2, len(min_withdrow)):
    tmp_list = []
    for x in [1, 2, 3, 4, 5]:
        if i-x >= 0:
            tmp_list.append(min_withdrow[i-x] + x)
        else:
            break
    for x in square_6_list:
        if i-x >= 0:
            tmp_list.append(min_withdrow[i-x] + 1)
        else:
            break
    for x in square_9_list:
        if i-x >= 0:
            tmp_list.append(min_withdrow[i-x] + 1)
        else:
            break
    min_withdrow[i] = min(tmp_list)

print(min_withdrow[-1])

Submission status: Accepted

Solution code:
def run():
  N = int(input())
  dp = [0] * (N+1)
  dp[1] = 1
  for n in range(1, N+1):
    if n == 1: continue
    dp[n] = dp[n-1]+1
    draw_money = 6
    while True:
      if n < draw_money: break
      dp[n] = min(dp[n], dp[n-draw_money]+1)
      draw_money *= 6
    draw_money = 9
    while True:
      if n < draw_money: break
      dp[n] = min(dp[n], dp[n-draw_money]+1)
      draw_money *= 9
  print(dp[N])
  
if __name__ == '__main__':
  run()

Submission status: Accepted

Solution code:
n=int(input())
dp=[float('inf')]*(n+1)
dp[1]=1
i=0
while 9**i<=n:
    dp[9**i]=1
    i+=1
j=0
while 6**j<=n:
    dp[6**j]=1
    j+=1
for i in range(2,n+1):
    for j in range(1,8):
        if i-6**j>=1 and i-9**j>=1:
            dp[i]=min(dp[i],min(dp[i-1],dp[i-6**j],dp[i-9**j])+1)
        elif i-6**j>=1:
            dp[i]=min(dp[i],min(dp[i-1],dp[i-6**j])+1)
        else:
            dp[i]=min(dp[i],dp[i-1]+1)
print(dp[n])

Submission status: Accepted

Solution code:
import sys
imput=sys.stdin.readline
n=int(input())
dp=[float('inf')]*(n+1)
dp[1]=1
i=0
while 9**i<=n:
    dp[9**i]=1
    i+=1
j=0
while 6**j<=n:
    dp[6**j]=1
    j+=1
#print(dp[1],dp[9],dp[36],dp[127])
for i in range(2,n+1):
    for j in range(1,8):
        if i-6**j>=1 and i-9**j>=1:
            dp[i]=min(dp[i],min(dp[i-1],dp[i-6**j],dp[i-9**j])+1)
        elif i-6**j>=1:
            dp[i]=min(dp[i],min(dp[i-1],dp[i-6**j])+1)
        else:
            dp[i]=min(dp[i],dp[i-1]+1)
#print(dp)
#int(dp[1],dp[9],dp[36],dp[127])
print(dp[n])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)

def main():
    n = int(input().strip())
    dp = [0] * (n+1)
    # coins = [0] + [6**i for i in range(8)] + [9 ** i for i in range(1, 7)]
    for i in range(1, n+1):
        dp[i] = 10**10

    for b in (6, 9):
        p = 0
        while b**p <= n:
            for i in range(n+1):
                if b**p <= i:
                    dp[i] = min(dp[i], dp[i-b**p]+1)
            p += 1
    print(dp[n])
if __name__ == '__main__':
    main()