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 ds(a, b):
	return a if a<b else ds(a//b,b)+a%b
n = int(input())
print(min([ds(i,6)+ds(n-i,9) for i in range(n+1)]))

Submission status: Accepted

Solution code:
def ds(a, b):
	return a if a<b else ds(a//b,b)+a%b
ans = float('inf')
n = int(input())
for i in range(n+1):
	ans = min(ans,ds(i,6)+ds(n-i,9))
print(ans)

Submission status: Accepted

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

for i in range(0, 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 cc < res:
        res = cc

print(res)

Submission status: Accepted

Solution code:
dp_list = [0]

def dp(N, money_list):
    ans = 100000
    if N==0:
        return dp_list[0]
    else:
        for money in money_list:
            if N-money >= 0:
                ans = min(ans, dp_list[N-money]+1)
        dp_list.append(ans)
        
        return dp_list[N]
        
        
def main():
    money_list = [1]
    for i in range(1,7):
        money_list.append(6**i)
    for i in range(1,6):
        money_list.append(9**i)
    money_list.sort(reverse=True)
        
    N = int(input())
    
    for i in range(N+1):
        ans = dp(i, money_list)
        
    print(ans)
    
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from itertools import count, takewhile

def calc(N, d={}):
    if N < 6:
        return N
    if N in d:
        return d[N]

    max9 = max(takewhile(lambda x: x<=N, (9**i for i in count())))
    max6 = max(takewhile(lambda x: x<=N, (6**i for i in count())))

    d[N] = min(calc(N-max9), calc(N-max6))+1
    #print(N, ':', d[N])
    return d[N]

print(calc(int(input())))

Submission status: Accepted

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

    def trans(x, y):
        r = ""
        k = ""
        while not(x==y==0):
            r += str(x%6)
            x = x//6
            k += str(y%9)
            y = y//9
        return r,k

    cost = N
    for i in range(N+1):
        roku, kyu = trans(i, N-i)
        cost_i = 0
        for j in range(len(roku)):
            cost_i += int(roku[j]) + int(kyu[j])
        cost = min(cost, cost_i)

    return cost

if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
# ある数Nのみで割っていく関数
def div_by_N(inpt, N):
    if inpt < N:
        return inpt
    else:
        ans = 0
        while inpt>0:
            ans += inpt%N
            inpt = inpt // N
        return ans
        
def main():
    inpt = int(input())
    ans = 1000000
    for i in range(inpt+1):
        ans = min(ans, div_by_N(i,6)+div_by_N(inpt-i,9))
    print(ans)
    
    
if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
num = int(input())
res = num
for i in range(num+1):
    cc = 0
    t = i
    while(t > 0):
        cc += t%6
        t //=6
    t = num-i
    while(t > 0):
        cc += t%9
        t //=9
    if res > cc:
        res = cc

print(res)

Submission status: Accepted

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

for i in range(N+1):
    count = 0
    t = i
    
    while (t>0):
        count += t%6
        t = int(t/6)
        
    t = N - i
        
    while (t>0):
        count += t%9
        t = int(t/9)
        
    if(result > count):
        result = count
           

print(result)

Submission status: Accepted

Solution code:
n=int(input())
s_6=[6**(6-i) for  i in range(6)] 
s_9=[9**(5-i) for  i in range(5)]
amari=[0,1,2,3,4,5,1,2,3,1,2,3,2,3]

best=float("inf")
for i in range(n+1):
    count_6=0
    n_6=i
    for j in range(len(s_6)):
        count_6+=n_6//s_6[j]
        n_6=n_6%s_6[j]

    n_9=n-i
    count_9=0
    for j in range(len(s_9)):
        count_9+=n_9//s_9[j]
        n_9=n_9%s_9[j]

    best=min(best, count_6+count_9+ amari[n_6+n_9])

print(best)

Submission status: Accepted

Solution code:
#abc099c

n=int(raw_input())
res=n
for i in xrange(n+1):
 s=0
 t=i
 while t>0:
  s+=t%6
  t/=6
 t=n-i
 while t>0:
  s+=t%9
  t/=9
 res=min(s,res)
print res

Submission status: Accepted

Solution code:
def g(n, a):
    for i in range(1, 100):
        if a**i > n:
            return a**(i-1)
    return -1

dp = {}
def solve(n):
    if n < 6:
        return n
    if not n in dp:
        a = g(n, 6)
        b = g(n, 9)
        dp[n] = min(solve(n-a)+1, solve(n-b)+1)
    return dp[n]

# assert solve(127) == 4
# assert solve(3) == 3
# assert solve(44852) == 16

print solve(input())

Submission status: Accepted

Solution code:
#DPトレーニング
#ABC099 C
#dp[i]と言うと本来「i番目までの整数の中から整数を選んで総和をとったときの総和の最大値」
#だが、これを読み替え「整数を選んで総和iにしたときの回数の最小値」とする

N = int(input())

F = [1]
F += [pow(6,i) for i in range(1,7)]
F += [pow(9,i) for i in range(1,6)]

dp = [0]

for i in range(1,N+1):
    dp.append(dp[i-1]+1) #1を選択すると、回数は1回増える
    for f in F:
        if i-f>=0: #一番回数の少ないトコからその値に辿り着けるfを選択
            dp[i] = min(dp[i],dp[i-f]+1) 
            
print(dp[N])

Submission status: Accepted

Solution code:
N=int(input().strip())
pays=[]
p1=set([1,])
n=6
while n<=N:
    p1.add(n)
    n*=6
n=9
while n<=N:
    p1.add(n)
    n*=9
pays.append(p1)
p2=p1
i=1
while i<=N:
    if N in p2:
        break
    else:
        p3=set()
        i+=1
        for i1 in p2:
            for i2 in p1:
                if i1+i2 <=N:
                    p3.add(i1+i2)
        p2=p3
print(i)

Submission status: Accepted

Solution code:
N=int(input())

ans=[1]
cnt=1
while 6**cnt<100000:
  ans.append(6**cnt)
  cnt+=1
cnt=1
while 9**cnt<100000:
  ans.append(9**cnt)
  cnt+=1

bfs=[10**10 for x in range(N+1)]
bfs[0]=0
for i in range(N+1):
  for j in range(len(ans)):
    if i+ans[j]<=N:
      bfs[i+ans[j]]=min(bfs[i+ans[j]],bfs[i]+1)

print(bfs[N])

Submission status: Accepted

Solution code:
n = int(input())

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

print(sol(n))

Submission status: Accepted

Solution code:
N = int(input())
v = [9**5, 9**4, 9**3, 9**2, 9, 6**6, 6**5, 6**4, 6**3, 6**2, 6, 1]
dp = [0] + [float('inf')] * N
for i in range(N):
    for j in v:
        if i + j <= N:
            dp[i + j] = min(dp[i + j], dp[i] + 1)
print(dp[N])

Submission status: Accepted

Solution code:
import bisect
n=int(input())
six=[6**(i) for i in range(10)]
nine=[9**(i) for i in range(10)]
times=[0,1,2,3,4,5,1,2,3]
times.extend([0]*100000)
for i in range(6):
    times[i]=i

def solve(n):
    if n==0 or times[n]!=0:
        return times[n]
    six_ex=bisect.bisect_right(six,n)-1
    nine_ex=bisect.bisect_right(nine,n)-1
    six_n=1+solve(n-six[six_ex])
    nine_n=1+solve(n-nine[nine_ex])

    times[n]=min(six_n, nine_n)
    return times[n]

print(solve(n))

Submission status: Accepted

Solution code:
from itertools import count, takewhile
from functools import lru_cache
 
@lru_cache(maxsize=None)
def dfs(n):
  if n == 0: return 0
  
  max9 = max(takewhile(lambda x: x<=n, (9**i for i in count())))
  max6 = max(takewhile(lambda x: x<=n, (6**i for i in count())))
  return min(dfs(n-max9), dfs(n-max6))+1
 
print(dfs(int(input())))

Submission status: Accepted

Solution code:
N=int(input())


X=[1]+[6**i for i in range(1,7)]+[9**i for i in range(1,6)]
X.sort()
X.reverse()

ANS=1000000



i=5



for i_0 in range(max(N//X[0]-i,0),N//X[0]+1):
    N_0=N-X[0]*i_0
    for i_1 in range(max(N_0//X[1]-i,0),N_0//X[1]+1):
        N_1=N_0-X[1]*i_1
        for i_2 in range(max(N_1//X[2]-i,0),N_1//X[2]+1):
            N_2=N_1-X[2]*i_2
            for i_3 in range(max(N_2//X[3]-i,0),N_2//X[3]+1):
                N_3=N_2-X[3]*i_3
                for i_4 in range(max(N_3//X[4]-i,0),N_3//X[4]+1):
                    N_4=N_3-X[4]*i_4
                    for i_5 in range(max(N_4//X[5]-i,0),N_4//X[5]+1):
                        N_5=N_4-X[5]*i_5
                        for i_6 in range(max(N_5//X[6]-i,0),N_5//X[6]+1):
                            N_6=N_5-X[6]*i_6
                            for i_7 in range(max(N_6//X[7]-i,0),N_6//X[7]+1):
                                N_7=N_6-X[7]*i_7
                                for i_8 in range(max(N_7//X[8]-i,0),N_7//X[8]+1):
                                    N_8=N_7-X[8]*i_8
                                    for i_9 in range(max(N_8//X[9]-i,0),N_8//X[9]+1):
                                        N_9=N_8-X[9]*i_9
                                        i_10=N_9//6
                                        N_10=N_9-X[10]*i_10
                                        if ANS>i_0+i_1+i_2+i_3+i_4+i_5+i_6+i_7+i_8+i_9+i_10+N_10:
                                            ANS=i_0+i_1+i_2+i_3+i_4+i_5+i_6+i_7+i_8+i_9+i_10+N_10


                                            




print(ANS)

Submission status: Accepted

Solution code:
N=int(input())


X=[1]+[6**i for i in range(1,7)]+[9**i for i in range(1,6)]
X.sort()
X.reverse()

ANS=1000000



i=4



for i_0 in range(max(N//X[0]-i,0),N//X[0]+1):
    N_0=N-X[0]*i_0
    for i_1 in range(max(N_0//X[1]-i,0),N_0//X[1]+1):
        N_1=N_0-X[1]*i_1
        for i_2 in range(max(N_1//X[2]-i,0),N_1//X[2]+1):
            N_2=N_1-X[2]*i_2
            for i_3 in range(max(N_2//X[3]-i,0),N_2//X[3]+1):
                N_3=N_2-X[3]*i_3
                for i_4 in range(max(N_3//X[4]-i,0),N_3//X[4]+1):
                    N_4=N_3-X[4]*i_4
                    for i_5 in range(max(N_4//X[5]-i,0),N_4//X[5]+1):
                        N_5=N_4-X[5]*i_5
                        for i_6 in range(max(N_5//X[6]-i,0),N_5//X[6]+1):
                            N_6=N_5-X[6]*i_6
                            for i_7 in range(max(N_6//X[7]-i,0),N_6//X[7]+1):
                                N_7=N_6-X[7]*i_7
                                for i_8 in range(max(N_7//X[8]-i,0),N_7//X[8]+1):
                                    N_8=N_7-X[8]*i_8
                                    for i_9 in range(max(N_8//X[9]-i,0),N_8//X[9]+1):
                                        N_9=N_8-X[9]*i_9
                                        i_10=N_9//6
                                        N_10=N_9-X[10]*i_10
                                        if ANS>i_0+i_1+i_2+i_3+i_4+i_5+i_6+i_7+i_8+i_9+i_10+N_10:
                                            ANS=i_0+i_1+i_2+i_3+i_4+i_5+i_6+i_7+i_8+i_9+i_10+N_10


                                            




print(ANS)

Submission status: Accepted

Solution code:
from itertools import count, takewhile
from functools import lru_cache

@lru_cache(maxsize=None)
def dfs(n):
  if n < 6:
    return n
  max9 = max(takewhile(lambda x: x<=n, (9**i for i in count())))
  max6 = max(takewhile(lambda x: x<=n, (6**i for i in count())))
  return min(dfs(n-max9), dfs(n-max6))+1
 
print(dfs(int(input())))

Submission status: Accepted

Solution code:
N=int(input())


X=[1]+[6**i for i in range(1,7)]+[9**i for i in range(1,6)]
X.sort()
X.reverse()


DP=[i for i in range(100001)]

def dpmin(i):
    Y=i
    for j in X:
      if i-j>=0:
        Y=min(Y,DP[i-j]+1)

    return Y

for i in range(100001):
    DP[i]=dpmin(i)

print(DP[N])

Submission status: Accepted

Solution code:
from itertools import count, takewhile
 
def dfs(n, d={}):
  if n < 6:
    return n
  if n in d:
    return d[n]
  max9 = max(takewhile(lambda x: x<=n, (9**i for i in count())))
  max6 = max(takewhile(lambda x: x<=n, (6**i for i in count())))
  d[n] = min(dfs(n-max9), dfs(n-max6))+1
  return d[n]
 
print(dfs(int(input())))

Submission status: Accepted

Solution code:
from itertools import takewhile, chain, count
 
n = int(input())
 
def powers(a, n):
   return takewhile(lambda x: x<=n, (a**i for i in count(1)))
 
draws = sorted(set(chain([1], powers(6, n), powers(9, n))))
d = {}
for draw, last_draw in zip(draws[1:], draws):
  d[draw, 0] = 0
  for i in range(1, n+1):
    d[draw, i] = min(d.get((draw, i-draw), n)+1, d.get((last_draw, i), i))
 
print(d.get((max(draws), n), n))

Submission status: Accepted

Solution code:
def s(n,p):
  while n>0:yield n%p;n//=p
c=lambda*a:sum(s(*a));n=int(input());print(min(c(i,6)+c(n-i,9)for i in range(n+1)))

Submission status: Accepted

Solution code:
def s(n,c):
  if n<6:return c+n
  a=b=1
  while a*6<=n:a*=6
  while b*9<=n:b*=9
  return min(s(n-a,c+1),s(n-b,c+1))
print(s(int(input()),0))

Submission status: Accepted

Solution code:
#補助関数
def convert(num,radix):
    res = 0
    while num > 0:
        res += num % radix
        num //= radix
    return res

#入力
INF = (1 << 31)
N   = int(input())
ans = INF

#計算
for i in range(N + 1):
    dec6 = i
    dec9 = N - i
    ans  = min(ans , convert(dec6,6) + convert(dec9,9))

#出力
print(ans)

Submission status: Accepted

Solution code:
a = []
N = 100000
i = 6
a.append(1)
while i<=N:
    a.append(i)
    i*=6
i = 9
while i<=N:
    a.append(i)
    i*=9
a.sort()
n = len(a)
dp = [10*20]*100001

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

for mon in range(2,100001):
    for i in range(n):
        if a[i]>mon:
            break
        dp[mon] = min(dp[mon],dp[mon-a[i]]+1)
print(dp[int(input())])

Submission status: Accepted

Solution code:
N = int(input())
A=[]
A.append(1)
for i in range(1,7):
    A.append(6**i)
for i in range(1,6):
    A.append(9**i)
A.sort()
dp=[10*5+5]*(N+1)
dp[0]=0
for i in range(1,N+1):
    for s in range(len(A)):
        if i-A[s]>=0:
            dp[i]=min(dp[i-A[s]]+1,dp[i])
print(dp[N])

Submission status: Accepted

Solution code:
n_max = 100000

bs = [(6 ** i, 6) for i in range (1, 10)]
bs.extend([(9 ** i, 9) for i in range (1, 10)])
bs = list(sorted(filter(lambda x: x[0] <= n_max, bs)))
bms = []
s = 5
for b, i in bs:
    s += b * (i - 1)
    bms.append((b, i, s))

#print(bs)
#print(bms, len(bms))

#m = 44852
m = int(input())

stack = [(m, 0, len(bms) - 1)]
#print("search start!")
result = 10000
while stack:
    m, n, bms_i = stack.pop()
    b, i, s = bms[bms_i]
    #print(m, n, bms_i, b, i, s)

    if n > result:
        #print("skip!", m, n, bms_i)
        continue
    if m > s:
        continue
    if bms_i < 0:
        if m <= 6 and m + n < result:
            result = m + n
        #    print('get result!', result)
        continue

    for j in range(i):
        next_m = m - b * j
        if next_m >= 0 and n + j < result:
            stack.append((next_m, n + j, bms_i - 1))

print(result)

Submission status: Accepted

Solution code:
n = int(input())

ans = 0
mod_base = [59049, 46656, 7776, 6561, 1296, 729, 216, 81, 36, 9, 6, 1]
mod_list = [59049, 46656, 7776, 6561, 1296, 729, 216, 81, 36, 9, 6, 1]
ans_list = [0 for _ in range(100000)]

for mod in mod_base:
	ans_list[mod - 1] = 1

for i in range(10000):
	if ans_list[n - 1] != 0:
		break
	new_mod_list = []
	for j in mod_list:
		for k in mod_base:
			if j + k <= 100000 and ans_list[j + k - 1] == 0:
				new_mod_list.append(j + k)
				ans_list[j + k - 1] = i + 2
	mod_list = sorted(new_mod_list, reverse=True)

print(ans_list[n - 1])

Submission status: Accepted

Solution code:

# coding: utf-8

# In[243]:


N = int(input())


# In[244]:


list_9 = [9]
for i in range(4):
    list_9.append(list_9[i] * 9)
    
list_6 = [6]
for i in range(5):
    list_6.append(list_6[i] * 6)


# In[245]:


amount_list = list_9 + list_6 + [1]
amount_list.sort(reverse=True)


# In[247]:


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


# In[248]:


for i in range(len(dp)):
    for amount in amount_list:
        if i >= amount:
            dp[i] = min(dp[i],dp[i-amount]+1)
print(dp[N])

Submission status: Accepted

Solution code:
n = int(input())
dp = [float('Inf')]*(n+1)
np = [9**i for i in range(1, 6)]
sp = [6**i for i in range(1, 7)]
dp[0] = 0
for i in range(1, len(dp)):
  
  for j in np:
    if j > i:
      break
    dp[i] = min(dp[i], dp[i-j]+1)
    
  for j in sp:
    if j > i:
      break
    dp[i] = min(dp[i], dp[i-j]+1)
  
  dp[i] = min(dp[i], dp[i-1]+1)

print(dp[-1])

Submission status: Accepted

Solution code:
def oper(n):
    res = 100001
    sn = [i for i in range(0, 100001)]
    for i in range(1, 7):
        for j in range(1, 100001):
            sn[j] = min(sn[j], j // (6 ** i) + sn[j % (6 ** i)])

    nn = [i for i in range(0, 100001)]
    for i in range(1, 6):
        for j in range(1, 100001):
            nn[j] = min(nn[j], j // (9 ** i) + nn[j % (9 ** i)])

    for i in range(n + 1):
        res = min(res, sn[i] + nn[n - i])

    return res


if __name__ == "__main__":
    n = input()
    print oper(n)

Submission status: Accepted

Solution code:
def it(n,p):
  while n > 0:
    yield n%p
    n //= p
cost = lambda *a: sum(it(*a))

n = int(input())
print(min(cost(x,6)+cost(n-x,9) for x in range(n+1)))

Submission status: Accepted

Solution code:
m = [1]
for i in range(1,7):
    if 6**i < 100000:
        m.append(6**i)
    if 9**i < 100000:
        m.append(9**i)
        
N = int(input())

dp = [10**9 for x in range(100001)]
dp[0] = 0
for v in range(1,100001):
    for i in range(len(m)):
        if v >= m[i] and dp[v - m[i]] != -1:
            dp[v] = min(dp[v],1 + dp[v-m[i]])

print(dp[N])

Submission status: Accepted

Solution code:
SixNum = [i for i in range(0,100001)]
for i in range(1,7):
        for j in range(1,100001):
                SixNum[j] = min(SixNum[j],j//(6**i) + SixNum[j%(6**i)])

NineNum = [i for i in range(0,100001)]
for i in range(1,6):
        for j in range(1,100001):
                NineNum[j] = min(NineNum[j],j//(9**i) + NineNum[j%(9**i)])

N = int(input())
ans = 100001
for i in range(0,N+1):
        ans = min(ans,SixNum[i]+NineNum[N-i])
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
res = N;
for i in range(N + 1):
    cc = 0
    t = i
    while t:
        cc += t % 6; t //= 6
    t = N - i
    while t:
        cc += t % 9; t //= 9
    if res > cc:
        res = cc
print(res)

Submission status: Accepted

Solution code:
def c_strange_bank(N):
    # 100,000 以下の6または9の冪乗(10万円より多く引き出す必要はない)
    money_withdraw = [1, 6, 9, 36, 81, 216,
                      729, 1296, 6561, 7776, 46656, 59049]
    # dp[k]はk円引き出すために必要な最小の操作回数
    dp = [float('inf') for _ in range(N + 1)]
    dp[0] = 0  # 0円引き出すために必要な回数は0
    for k in range(1, N + 1):
        for money in money_withdraw:
            if money > k:
                continue
            else:
                # k円引き出すために必要な最小回数を更新するとしたら、
                # k-money円から追加でmoney円を(1回)引き出したときの回数である
                dp[k] = min(dp[k - money] + 1, dp[k])
    ans = dp[-1]
    return ans

N = int(input())
print(c_strange_bank(N))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

def ret_ans(n):
    li = [1]
    li.extend([6 ** i for i in range(1, 15) if 6 ** i <= n])
    li.extend([9 ** i for i in range(1, 15) if 9 ** i <= n])
    li.sort(reverse=True)
    
    s = set([n])
    cnt = 1
    while True:
        ts = set(s)
        for e in li:
            for c in s:
                if c - e == 0:
                    return cnt
                if c - e > 0:
                    ts.add(c - e)
        s = ts
        cnt += 1
 

def solve():
    print(ret_ans(int(input())))

if __name__=="__main__":
    solve()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

def ret_ans(n):
    li = [1]
    li.extend([6 ** i for i in range(0, 15) if 6 ** i <= n])
    li.extend([9 ** i for i in range(1, 15) if 9 ** i <= n])
    li.sort(reverse=True)
    
    s = set([n])
    cnt = 1
    while True:
        ts = set(s)
        for e in li:
            for c in s:
                if c - e == 0:
                    return cnt
                if c - e > 0:
                    ts.add(c - e)
        s = ts
        cnt += 1
 

def solve():
    print(ret_ans(int(input())))

if __name__=="__main__":
    solve()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

def ret_ans(n):
    li = [1]
    li.extend([6 ** i for i in range(0, 15) if 6 ** i <= n])
    li.extend([9 ** i for i in range(1, 15) if 9 ** i <= n])
    li.sort(reverse=True)
    
    s = set([n])
    cnt = 1
    while True:
        ts = set(s)
        for e in li:
            for c in s:
                if c - e == 0:
                    return cnt
                if c - e > 0:
                    ts.add(c - e)
        s = ts
        cnt += 1
 

def solve():
    print(ret_ans(int(input())))

if __name__=="__main__":
    solve()

Submission status: Accepted

Solution code:
INF=9999999

n=int(input())
dp=[INF for i in range(n+1)]
dp[-1]=0
for i in range(n,0,-1):
    e6=1
    while 6**e6<=i:
        dp[i-6**e6]=min(dp[i]+1,dp[i-6**e6])
        e6+=1
    e9=1
    while 9**e9<=i:
        dp[i-9**e9]=min(dp[i]+1,dp[i-9**e9])
        e9+=1
ans=INF
for i in range(n):
    if dp[i]==0:
        continue
    ans=min(ans,i+dp[i])
if ans==INF:
    ans=n
print(ans)

Submission status: Accepted

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

for i in range(1, n+1):
    a = 0
    b = 0
    while 6**(a+1) <= i: 
        a += 1
    while 9**(b+1) <= i:
        b += 1
    l += [min([l[i-6**p] for p in range(1, a+1)] + [l[i-9**q] for q in range(1, b+1)] + [l[i-1]]) + 1]

print(l[n])

Submission status: Accepted

Solution code:
N=int(input())
ans=N
def func1():
    global ans
    for i in range(N+1):
        cnt=0
        t=i
        while(t>0):
            cnt+=t%6
            t/=6
            t=int(t)
        t=N-i
        while(t>0):
            cnt+=t%9
            t/=9
            t=int(t)
        if(ans>cnt):
            ans=cnt
    return ans

func1()
print(ans)

Submission status: Accepted

Solution code:
a = int(input())
k = a
for i  in range(a+1):
  al = 0
  t = i
  while t > 0:
    al += t%6
    t //=6
  t = a - i
  while t > 0:
    al += t%9
    t //=9
  if al < k:
    k = al

print(k)

Submission status: Accepted

Solution code:
from sys import stdin

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

def sum_num(num):
    sum = 0
    for i in range(len(num)):
        sum += int(num[i])
    return sum

N = int(stdin.readline().rstrip())

x = 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 x > cc:
        x = cc

print(x)

Submission status: Accepted

Solution code:
n = int(input())
v = []
i = 6
while i<=n:
    v.append(i)
    i *= 6
i=9
while i <= n:
    v.append(i)
    i *= 9
v.sort(reverse=True)
dic = dict()
def dp(i, N):
    if i == len(v):
        return N
    if (i, N) not in dic:
        dic[(i, N)] = min(dp(i, N-v[i])+1, dp(i+1, N)) if N-v[i] >= 0 else dp(i+1, N)
    return dic[(i, N)]
print(dp(0, n))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

def main():
    n = int(input())
    li = dp(n)
    print(li[n])

def dp(n):
    inf=float('inf')
    dp = [inf for i in range(n+1)]
    dp[0] = 0
    money_list = get_money_list()
    for i in range(1, n + 1):
        for pay in money_list:
            if pay > i:
                continue
            else:
                dp[i] = min(dp[i - pay] + 1, dp[i])
    return dp

def create_list(n):
    i = 1
    money_list = []
    while i < 100000:
        money_list.append(i)
        i = i * n
    return money_list

def get_money_list():
    li = create_list(9)
    li.extend(create_list(6))
    li = list(set(li))
    li.sort(key=int, reverse=True)
    return li

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
six = [6,36,216,1296,7776,46656]
nine = [9,81,729,6561,59049]

def dfs(n):
    if n < 6:
        return n
    six_max, nine_max = (1, 1)

    for i in six:
        if n < i:
            break
        six_max = i
    
    for i in nine:
        if n < i:
            break
        nine_max = i
    
    ans = 123
    
    if nine_max != 1:
        ans = dfs(n - nine_max) + 1
    if six_max != 1:
        ans = min(ans, dfs(n - six_max) + 1)
    return ans

print(dfs(int(input())))

Submission status: Accepted

Solution code:
import math
from itertools import product

N = int(input())

values = sorted([9**i for i in range(1, math.ceil(math.log(100000, 9)))] +
                [6**i for i in range(math.ceil(math.log(100000, 6)))])
values = [x for x in values if x <= N]
dp = [N] * (N + 1)
dp[0] = 0
for i, v in product(range(1, N + 1), values):
    if i - v >= 0:
        dp[i] = min(dp[i - v] + 1, dp[i])
print(dp[N])

Submission status: Accepted

Solution code:
N = int(input())
#num = [1]
#print("a")
"""
#memo = [[ -1 for i in range(12)]for j in range(100000)]
n = 6
while True:
    num.append(n)
    n *= 6
    if n > 100000:
        break
n = 9
while True:
    num.append(n)
    n *= 9
    if n > 100000:
        break
num.sort()

ans = 0
print(num)
#while N > 6:

def DP(n , index):
    if index == 0:
        return  n
    elif n == 0:
        return 0
    min_ = 10000000
    if n < num[index]:
        #print(n,num[index])
        return DP(n,index - 1)
    can = num[index]
    #print(index)
#    print(n//can)
    for i in range(n // can+1):
        min_ = min(min_ , DP(n - i * can,index - 1) + i)
 #       print(i,n,index,DP(n - i*can,index-1))
    
     #   print(min_)
    #print(min_)
    memo[n][index] = min_
    return min_
    
print(DP(N,11))
"""

def ninep(N):
    if N <9:
        return N
    ans = 0
    while N > 0:
        ans += N % 9
        N =N // 9
    return ans


def sixp(N):
    if N <6:
        return N
    ans = 0
    while N > 0:
        ans += N % 6
        N = N // 6
    return ans


ans = 1000000
for i in range(N+1):
    ans = min(ans,ninep(i) + sixp(N - i))
#    print(ninep(i), sixp(N - i),i)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())

units = [59049, 46656, 7776, 6561, 1296, 729, 216, 81, 36, 9, 6, 1]

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

for i in range(2, N+1):
    for u in units:
        p = i-u
        if p >= 0:
            dp[i] = min(dp[p]+1, dp[i])

print(dp[N])

Submission status: Accepted

Solution code:
import math

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

for i in range(1,N+1):
	memo[i] = memo[i-1]+1
	j = 1
	while pow(6,j) <= i:  
		memo[i] = min(memo[i],memo[i-pow(6,j)]+1)
		j += 1
	j = 1
	while pow(9,j) <= i:
		memo[i] = min(memo[i],memo[i-pow(9,j)]+1)
		j += 1

print(memo[-1])

Submission status: Accepted

Solution code:
N = int(input())

def calc(x, base):
    r = 0
    while x:
        x, m = divmod(x, base)
        r += m
    return r

result = min(calc(i, 6) + calc(N - i, 9) for i in range(N + 1))

print(result)

Submission status: Accepted

Solution code:
N = int(input())

res = 100000

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

print(res)

Submission status: Accepted

Solution code:
N = int(input())

result = N
for i in range(0,N+1):
    count = 0
    tmp = i 
    while tmp > 0:
        count += tmp%6
        tmp //= 6
    tmp = N - i 
    while tmp > 0:
        count += tmp%9
        tmp //=9
    
    if result > count:
        result = count

print(result)

Submission status: Accepted

Solution code:
n = int(input())

dp = [10 ** 5]*(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])

Submission status: Accepted

Solution code:
##n円をx円の指数の和で表すときの操作数
def getCnt(n, x):
    ret = 0
    while (n > 0):
        ret += n % x
        n //= x
    return ret

if __name__ == '__main__':
    n = int(input())
    ans = n
    for i in range(n + 1):
        cnt = 0
        cnt += getCnt(i, 6)
        cnt += getCnt(n - i, 9)
        ans = min(ans, cnt)
    print(ans)

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())

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

    if res < ans:
        ans = res



print(ans)

Submission status: Accepted

Solution code:
N=int(raw_input())
M=[999999 for i in range(N+1)]
possible=sorted([1]+[6**i for i in range(1,100) if 6**i<=N]+[9**i for i in range(1,100) if 9**i<=N])
M[0]=0
for p in possible:
    M[p]=1

for m in range(N+1):
    tmp=999999
    for p in possible:
        if m-p>0:
            tmp=min(tmp, M[m-p]+1)

    M[m]=min(tmp,M[m])

print M[N]

Submission status: Accepted

Solution code:
n=int(input())
a=[]
for i in range(n+1):
  a.append(0)
for i in range(1,n+1):
  if i<=5:
    a[i]=i
  elif i<=8:
    a[i]=i-5
  else:
    j=1
    next1=0
    while 6**j<=i:
      next1=6**j
      j+=1
    k=1
    next2=0
    while 9**k<=i:
      next2=9**k
      k+=1
    if a[i-next1]<a[i-next2]:
      a[i]=a[i-next1]+1
    else:
      a[i]=a[i-next2]+1
print(a[n])

Submission status: Accepted

Solution code:
N = int(input())

ans = N
for i in range(N+1):
    cc = 0
    num_6 = i
    num_9 = N - i
    while num_6 > 0:
        cc += (num_6 % 6)
        num_6 //= 6
    while num_9 > 0:
        cc += (num_9 % 9)
        num_9 //= 9
    if ans > cc:
        ans = cc

print(ans)

Submission status: Accepted

Solution code:
n = int(input())

n_max=100000

a1=[1]

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

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

#print(a9)
#print(a6)

k1=a1+a6+a9
kn=list(k1)
#print(k1)
#print(kn)


ans=1

while (1==1):
	if n in kn: break
	kn=[i+j for i in kn for j in k1 if i+j<=n]
	kn=list(set(kn))
	ans+=1
#	print(ans, kn)

print(ans)

exit(0)

Submission status: Accepted

Solution code:
N = int(input())

ans = N

for A in range(N+1):
    counter = 0
    temp = A
    while temp > 0:
        q, r = divmod(temp, 6)
        counter += r
        temp = q

    temp = N - A
    while temp > 0:
        q, r = divmod(temp, 9)
        counter += r
        temp = q

    if ans > counter:
        ans = counter

print(ans)

Submission status: Accepted

Solution code:
n = int(input())

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