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())
sixs = [6,36,216,1296,7776,46656]
nines = [9,81,729,6561,59049]
lis = [i for i in range(170000)]
for i in range(0,100001):
 for j in sixs:
  if lis[i+j] > lis[i]+1:
    lis[i+j] = lis[i] + 1
 for j in nines:
  if lis[i+j] > lis[i]+1:
    lis[i+j] = lis[i] + 1
print(lis[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+=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:
import itertools
import math
import sys

MAX_N = 100000
MAX_LOG6 = int(math.log(MAX_N, 6))
MAX_LOG9 = int(math.log(MAX_N, 9))

def main(N):
    dp = [MAX_N] * (N + 1)
    for i in range(min(N + 1, 6)):
        dp[i] = i
    for i in range(N + 1):
        t = 1
        for j in range(1, MAX_LOG6 + 1):
            t *= 6
            if i - t < 0:
                break
            dp[i] = min(dp[i], dp[i - t] + 1)
        t = 1
        for j in range(1, MAX_LOG9 + 1):
            t *= 9
            if i - t < 0:
                break
            dp[i] = min(dp[i], dp[i - t] + 1)
    print(dp[N])

if __name__ == '__main__':
    N = int(sys.stdin.readline())
    main(N)

Submission status: Accepted

Solution code:
n=int(input())
s=[59049, 46656, 7776, 6561, 1296, 729, 216, 81, 36, 9, 6]
best=float("inf")

for i0 in range(2):
  if i0*s[0]>n or i0>=best: continue
  for i1 in range(3):
    if i0*s[0]+i1*s[1]>n or i0+i1>=best: continue
    for i2 in range(6):
      if i0*s[0]+i1*s[1]+i2*s[2]>n or i0+i1+i2>=best: continue
      for i3 in range(6):
        if i0*s[0]+i1*s[1]+i2*s[2]+i3*s[3]>n or i0+i1+i2+i3>=best: continue
        for i4 in range(6):
          if i0*s[0]+i1*s[1]+i2*s[2]+i3*s[3]+i4*s[4]>n or i0+i1+i2+i3+i4>=best: continue
          for i5 in range(6):
            if i0*s[0]+i1*s[1]+i2*s[2]+i3*s[3]+i4*s[4]+i5*s[5]>n or i0+i1+i2+i3+i4+i5>=best: continue
            for i6 in range(6):
              if i0*s[0]+i1*s[1]+i2*s[2]+i3*s[3]+i4*s[4]+i5*s[5]+i6*s[6]>n or i0+i1+i2+i3+i4+i5+i6>=best: continue
              for i7 in range(6):
                if i0*s[0]+i1*s[1]+i2*s[2]+i3*s[3]+i4*s[4]+i5*s[5]+i6*s[6]+i7*s[7]>n or i0+i1+i2+i3+i4+i5+i6+i7>=best: continue
                for i8 in range(6):
                  if i0*s[0]+i1*s[1]+i2*s[2]+i3*s[3]+i4*s[4]+i5*s[5]+i6*s[6]+i7*s[7]+i8*s[8]>n or i0+i1+i2+i3+i4+i5+i6+i7+i8>=best: continue
                  for i9 in range(6):
                    if i0*s[0]+i1*s[1]+i2*s[2]+i3*s[3]+i4*s[4]+i5*s[5]+i6*s[6]+i7*s[7]+i8*s[8]+i9*s[9]>n or i0+i1+i2+i3+i4+i5+i6+i7+i8+i9>=best: continue
                    for i10 in range(6):
                      if i0*s[0]+i1*s[1]+i2*s[2]+i3*s[3]+i4*s[4]+i5*s[5]+i6*s[6]+i7*s[7]+i8*s[8]+i9*s[9]+i10*s[10]>n or i0+i1+i2+i3+i4+i5+i6+i7+i8+i9+i10>=best: continue
                      num= n - (i0*s[0]+i1*s[1]+i2*s[2]+i3*s[3]+i4*s[4]+i5*s[5]+i6*s[6]+i7*s[7]+i8*s[8]+i9*s[9]+i10*s[10])
                      best=min(best, i0+i1+i2+i3+i4+i5+i6+i7+i8+i9+i10+num)

print(best)

Submission status: Accepted

Solution code:
N = int(input())
result = 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
    result = c if result > c else result

print(result)

Submission status: Accepted

Solution code:
N = int(input())

result = 100000000000

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

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

print(result)

Submission status: Accepted

Solution code:
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:
import copy
N=input()

def nine(m):
	if m<9: return m
	for i in range(1000):
		t=9**i
		if t>m:
			t1=9**(i-1)
			return m-t1
def six(m):
	if m<6: return m
	for i in range(1000):
		t=6**i
		if t>m:
			t2=6**(i-1)
			return m-t2


Z=15
k=1<<Z

b=set()
for i in range(k):

	n=copy.deepcopy(N)
	ans=0
	for j in range(Z):
		if n<6:
			b.add(ans+n)
			break
		if i&(1<<j)!=0:
			#9
			n=nine(n)
			ans+=1
		else:
			#6
			n=six(n)
			ans+=1


print min(b)

Submission status: Accepted

Solution code:
n = int(input())

lis = [1, 6, 36, 216, 1296, 7776, 46656,
     9, 81, 729, 6561, 59049]
m = len(lis)

dp = [float('inf') for _ in range(n+1)]
dp[0] = 0

for j in range(1,n+1):
    temp = []
    for i in range(m):
        if j < lis[i]:
            continue
        else:
            temp.append(dp[j-lis[i]]+1)
    dp[j] = min(temp)

print(dp[n])

Submission status: Accepted

Solution code:
N = int(input())
cnt = 0
i = 10
dp = [0,1,2,3,4,5,1,2,3,1]
while i<=N:
    idx_n,idx_s = 0,0
    while i-(9**idx_n)>=0:
        idx_n += 1
    idx_n -= 1
    while i-(6**idx_s)>=0:
        idx_s += 1
    idx_s -= 1
    dp.append(min(1+dp[i-(9**idx_n)],1+dp[i-(6**idx_s)]))
    i += 1
print(dp[N])

Submission status: Accepted

Solution code:
N = int(raw_input())
m = N
for i in range(N+1):
    c = 0
    six = i
    nine = N-i
    while six > 0:
        c += six % 6
        six /= 6
    while nine > 0:
        c += nine % 9
        nine /= 9
    if m > c:
        m = c
print m

Submission status: Accepted

Solution code:
N = int(input())
cnt = 0
i = 10
dp = [0,1,2,3,4,5,1,2,3,1]
while i<=N:
    idx_n,idx_s = 0,0
    while i-(9**idx_n)>=0:
        idx_n += 1
    idx_n -= 1
    while i-(6**idx_s)>=0:
        idx_s += 1
    idx_s -= 1
    dp.append(min(1+dp[i-(9**idx_n)],1+dp[i-(6**idx_s)]))
    i += 1
print(dp[N])

Submission status: Accepted

Solution code:
N = int(input())

counter = 0

cand = set()

cand.add(1)
i = 1
while 6 ** i <= N:
    cand.add(6 ** i)
    i += 1

i = 1
while 9 ** i <= N:
    cand.add(9 ** i)
    i += 1

c = sorted(cand, reverse=True)

T = [N+1] * (N + 1)
T[0] = 0
for i in range(len(c)):
    for j in range(N - c[i] + 1):
        T [j + c[i]] = min(T[j + c[i]], T[j] + 1)

print(T[N])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000)

def count(ans, c, i, l, k):
    if(i == 0):
        if(ans[0] > c + l):
            ans[0] = c + l
        return

    for j in range(l // k[i], -1, -1):
        c += j
        l -= k[i] * j
        i -= 1
        count(ans, c, i, l, k)
        i += 1
        l += k[i] * j
        c -= j
        if(ans[0] <= c + l // k[i]): return

n = int(input())

k = [1]
a = 1
b = 1
while(k[len(k)-1] <= n):
    if(6 ** a < 9 ** b):
        k.append(6 ** a)
        a += 1
    elif(6 ** a > 9 ** b):
        k.append(9 ** b)
        b += 1
    else:
        k.append(6 ** a)
        a += 1
        b += 1

ans = [1000000]
count(ans, 0, len(k)-1, n, k)

print(ans[0])

Submission status: Accepted

Solution code:
n = int(input())
money_list = (59049, 46656, 7776, 6561, 1296, 729, 216, 81, 36, 9, 6, 1)
ans = 0
for i in money_list:
  while n >= i:
    if (46656*2) <= n:
      n -= 46656
      ans += 1
    elif (6561*2) <= n < (7776+6561) or (6561*3) <= n <= (6561*3+1296):
      n -= 6561
      ans += 1
    elif (729*2) <= n < (1296+729) or (729*3) <= n < (1259+729+216):
      n -= 729
      ans += 1
    elif (81*3) <= n <= (81*3+2) or (81*3+6) <= n < (216+36): #249: #(245):
      n -= 81
      ans += 1
    elif 12 <= n < 15:
      n -= 6
      ans += 1
    else:
      n -= i
      ans += 1

print(ans)

Submission status: Accepted

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

import copy
import sys

def solve(n, actions, offset):

    res = 0
    val = 1000000
    if n == 0 or len(actions) == 0:
        return(offset)
    while (val > n):
        val = actions.pop()
    if val == 1:
        return(n + offset)
    while n >= val * 3:
        res += 1
        n -= val
    tmp = 1000000
    i = 0
    while n >= 0:
        tmp = min(tmp, solve(copy.copy(n), copy.copy(actions), copy.copy(i)))
        i += 1
        n -= val
    return(tmp + res + offset)


n = int(input())

res = 0

actions = [1]

for i in range(1, 6 + 1):
    actions.append(6 ** i)
    actions.append(9 ** i)

print(solve(n, actions, 0))

Submission status: Accepted

Solution code:
list_money = [1]
list_money.extend([6**i for i in range(1, 7)])
list_money.extend([9**i for i in range(1, 6)])
list_money = list(set(list_money))
list_money = list(sorted(list_money))

l = len(list_money)
n = int(input())

dp = [[0 for j in range(n+1)] for i in range(l)]
for j in range(n+1):
    dp[0][j] = j

for i in range(1, l):
    num = list_money[i]
    for j in range(1, n+1):
        ij_list = [dp[i-1][j]]
        if j >= num:
            ij_list.append(dp[i][j-num]+1)
        dp[i][j] = min(ij_list)

print(dp[-1][-1])

Submission status: Accepted

Solution code:
N = int(input())


COINS = [1,6,6**2,6**3,6**4,6**5,6**6,9**1,9**2,9**3,9**4,9**5]
COINS.sort(reverse=True)
inf = 2**30

A = [inf] * (N+1)
A[0] = 0;
for i in range(N+1):
	for coin in COINS:
		if i - coin >= 0:
			A[i] = min(A[i - coin]+1, A[i])
print(A[N])

Submission status: Accepted

Solution code:
from math import log
 
def exp(n, base):
    e = int(log(n, base))
    if base ** (e + 1) <= n:
        return e + 1
    else:
        return e
 
def min_withdraw(n):
    if n < 6:
        return n
    else:
        exp_nine = exp(n, 9)
        exp_six = exp(n, 6)
        return 1 + min(min_withdraw(n - (6 ** exp_six)), min_withdraw(n - (9 ** exp_nine)))
    
    
if __name__ == '__main__':
    n = int(input())
    print(min_withdraw(n))

Submission status: Accepted

Solution code:
n = int(input())
ans = [n]
pay = []
for i in range(1, 10):
    if 6 ** i < 100000:
        pay.append(6 ** i)
    if 9 ** i < 100000:
        pay.append(9 ** i)
pay.sort(reverse=True)

def func(n, times):
    for i in range(len(pay)):
        n2 = n
        times2 = times
        if pay[i] <= n2:
            n2 -= pay[i]
            times2 += 1
            if ans[0] > times2 + n2:
                ans[0] = times2 + n2
            if n2 >= 6 and times2 < ans[0]:
                func(n2, times2)
            if n2 > pay[i]*2:
                break


func(n, 0)
print(ans[0])

Submission status: Accepted

Solution code:
N = int(input())

lst = []
for i in range(10):
    if 6 ** i > 100000:
        break
    lst.append(6 ** i)
for j in range(1, 9):
    if 9 ** j > 100000:
        break
    lst.append(9 ** j)

DP = [N for i in range(N + 1)]
DP[0] = 0

for i in lst:
    for j in range(i, N + 1):
        DP[j] = min(DP[j], DP[j - i] + 1)

print(DP[N])

Submission status: Accepted

Solution code:
import collections

def main():
    n = int(input())
    c = search(n)
    print(c)

def search(n):
    q = collections.deque()
    q.append((0, n, []))

    while q:
        cnt, rest, lst = q.popleft()
        for c in candidates(rest):
            if c == rest:
                return cnt + 1
            elif c < rest:
                q.append((cnt + 1, rest - c, lst + [c]))

def candidates(n):
    if n < 6:
        return [1]
    elif n < 9:
        return [6, 1]
    else:
        s = []
        p = 9
        while p <= n:
            p *= 9
        s.append(p // 9)

        q = 6
        while q <= n:
            q *= 6
        s.append(q // 6)

        return s

main()

Submission status: Accepted

Solution code:
N = int(input())

i = 0
j = 0
list = [1]

while(N >= 9**i):
    i += 1
    list.append(9**i)
while(N >= 6**j):
    j += 1
    list.append(6**j)

list.remove(9**i)
list.remove(6**j)
list.sort()

a = [[0 for i in range(N+1)] for j in range(len(list))]

for j in range(N+1):
    a[0][j] = j

for i in range(1,len(list)):
    for j in range(N+1):
        if j < list[i]:
            a[i][j] = min(a[i-1][j], a[i][j-1]+1)
        else:
            a[i][j] = min(a[i-1][j], a[i][j - list[i]]+1)

print(a[len(list)-1][N])

Submission status: Accepted

Solution code:
def knapsack(V,n):
    if n == -1:
        return V
    if (V,n) in OS_dict.keys():
        return OS_dict[(V,n)]
    elif V < cost[n]:
        r = knapsack(V,n-1)
        OS_dict[(V, n)] = r
        return r
    else:
        r = min(knapsack(V-cost[n],n)+value[n],knapsack(V,n-1)) 
        OS_dict[(V,n)] = r
        return r



N = int(input())
now = 9
cost = []
value = []
while now <= N:
    cost.append(now)
    now *= 9
now = 6
while now <= N:
    cost.append(now)
    now *= 6
for x in range(len(cost)):
    value.append(1)
OS_dict = {}
V = N
best = knapsack(V,len(cost)-1)
print(best)

Submission status: Accepted

Solution code:
def min_num_part_sum(a,A):
    N=len(a)
    inf=float('inf')
    dp=[inf for i in range(A+1)]
    dp[0]=0
    for i in range(N):
        for j in range(A+1):
            if a[i]<=j:
                dp[j]=min(dp[j-a[i]]+1,dp[j])
            else:
                dp[j]=dp[j]
    return dp[A]

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

n=int(input())

print(min_num_part_sum(can_pay,n))

Submission status: Accepted

Solution code:
import math
N0=int(input())
count=0
temp=9999999
for i5 in range(1,-1,-1):
    N = N0-(9**5) *i5
#    print(N)
    if N<0: continue
    for i4 in range(8,-1,-1):
        N=N0-(9**5) *i5-(9**4)*i4
#        print(N)
        if N<0: continue
        for i3 in range(8,-1,-1):
            N=N0-(9**5) *i5-(9**4)*i4-(9**3)*i3
#            print(N)
            if N<0: continue
            for i2 in range(8,-1,-1):
                N=N0-(9**5) *i5-(9**4)*i4-(9**3)*i3-(9**2)*i2
#                print(N)
                if N<0: continue
                for i1 in range(8,-1,-1):
                    N=N0-(9**5) *i5-(9**4)*i4-(9**3)*i3-(9**2)*i2-9*i1
#                    print(N)
                    if N<0: continue

                    while(N>0):
                        count = count + 1
                        N=N-6**int(math.log(N,6))
                        
                    temp = min([temp,i5+i4+i3+i2+i1+count])
                    count=0
            
print(temp)

Submission status: Accepted

Solution code:
N = int(input())
ans = 112345
for i in range(N + 1):
    a = i
    b = N - i
    c = 0
    while a:
        c += a % 6
        a //= 6
    while b:
        c += b % 9
        b //= 9
    ans = min(ans, c)
print(ans)

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()
dic = dict()
def dp(i, N):
    if i < 0:
        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(len(v)-1, n))

Submission status: Accepted

Solution code:
N = int(input())
dp = [100000 for i in range(N+1)]
dp[:2] = [0, 1]
f = lambda n: [n**i for i in range(10) if n**i <= 100000]
c = f(6)+f(9)
for i in range(100000):
    for x in c:
        if i+x <= N:
            dp[i+x] = min(dp[i+x], dp[i]+1)
else:
    print(dp[N])

Submission status: Accepted

Solution code:
import random

N = int(input())
n = N

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

def prob_solver(n):
    result = 0
    for price in l:
        if n < price:
            continue
        x = random.randint(0, n // price)
        result += x
        n -= x * price
    return result + n

ans = n
for _ in range(10000):
    ans = min(ans, prob_solver(n))

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:

n = int(input())
queue = [[n,0]]
count = 0
maxi = 10000
ax = [1000 for i in range(1000)]

while queue:
    ato,count = queue.pop(0)
    if ato <= 1000:
        if ax[ato-1] > count:
            ax[ato-1] = count
        else:continue

    if ato == 0:
        maxi = min(maxi,count)
        continue
    a = ato
    b = ato
    counta = 0
    countb = 0
    countc = 0
    if ato >= 6:
        while a >= 9:
            a = a//9
            counta +=1
        while b >=6:
            b = b//6
            countb +=1
    else:
        countc = ato
    if counta > 0:
        queue.insert(0,[ato-9**counta,count+1])
    if countb >0:
        queue.insert(0,[ato-6**countb,count+1])
    if countc > 0:
        queue.insert(0,[0, count + ato])

print(maxi)

Submission status: Accepted

Solution code:
n = int(input())
possible = [1]
i=1
while i <= 100000:
  i = i*6
  possible+=[i]
i=1
while i <= 100000:
  i = i*9
  possible+=[i]
possible.sort(reverse =1)
ans = 0
table = set([n])
while True:
  if 0 in table:
    print(ans)
    break
  ans+=1
  nexttable = set()
  for num in table:
    for p in possible:
      if num - p >= 0:
        nexttable.add(num-p)
  table =nexttable

Submission status: Accepted

Solution code:
N = int(raw_input())
ans = 100000
for i in range(N+1):
  a = i
  b = N -i
  da = 0
  db = 0
  while a > 0:
    da += a % 9
    a /= 9
  while b > 0:
    db += b % 6
    b /= 6
  ans = min(ans, da+db)
print ans

Submission status: Accepted

Solution code:
N = int(input())
dp = [-1 for i in range(100010)]

availableValues = sorted(
    [
        1,
        6,
        36,
        216,
        1296,
        7776,
        46656,
        9,
        81,
        729,
        6561,
        59049,
    ],
    reverse=True)


def solve(n):
    if dp[n] != -1:
        return dp[n]

    ans = 110000
    for i in availableValues:
        if i < n:
            ans = min(ans, solve(n - i) + 1)
        if i == n:
            ans = 1
    dp[n] = ans
    return dp[n]


print(solve(N))

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()
dic = dict()
def dp(i, N):
    if N == 0:
        return 0
    if i < 0:
        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(len(v)-1, n))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product

sys.setrecursionlimit(50000)


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@lru_cache(maxsize=None)
def r(N):
    if N == 0:
        return 0

    c = 1
    while True:
        if c * 9 <= N:
            c *= 9
        else:
            break
    b = 1
    while True:
        if b * 6 <= N:
            b *= 6
        else:
            break
    if c >= 9:
        ac = r(N - c) + 1
    else:
        ac = sys.maxsize

    if b >= 6:
        ab = r(N - b) + 1
    else:
        ab = sys.maxsize

    return min(N, ab, ac)


@mt
def slv(N):
    return r(N)


def main():

    N = read_int()
    print(slv(N))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin
hi = 10**5
dp = [10**6] * (hi + 5)
dp[0] = 0
coins = [1]
cur = 1
while True:
 cur *= 6
 if cur > hi:
  break
 coins.append(cur)
cur = 1
while True:
 cur *= 9
 if cur > hi:
  break
 coins.append(cur)
for v in coins:
 for i in xrange(v,100001):
  dp[i] = min(dp[i], dp[i-v] + 1)
n = int(stdin.readline())
print dp[n]

Submission status: Accepted

Solution code:

base = [1,6,9]
SISU = 6
seiyaku = ([1])
MAX = 999999999
for i in range(1, 7):
    seiyaku.append(pow(base[1], i))
    seiyaku.append(pow(base[2], i))
seiyaku.sort()
# print(seiyaku)

N = int(input())
count = 0
DP = [0,1]
for n in range(2, N+1):
    arr = []
    i = 0
    while n >= seiyaku[i]:
        arr.append(DP[n-seiyaku[i]] + 1)
        i += 1
    # print(n, i, arr)
    DP.append(min(arr))


print(DP[N])

Submission status: Accepted

Solution code:
N = int(input())
k = [1]
for i in range(1, 7):
    k.append(6**i)
for i in range(1, 6):
    k.append(9**i)
k.sort()

m = len(k)

dp = [[0 for j in range(N+1)] for i in range(m+1)]
dp[1] = [int(i) for i in range(N+1)]
for i in range(2, m+1):
    for j in range(N+1):
        if j - k[i-1] > -1:
            dp[i][j] = min(dp[i-1][j], dp[i][j-k[i-1]]+1)
        else:
            dp[i][j] = dp[i-1][j]
print(dp[m][N])

Submission status: Accepted

Solution code:
N = int(input())                            
ans = 0                                     
                                            
def num(x,y):                               
    base = x                                
    while x <= y:                           
        x = x * base                        
    return x // base                        
a = N                                       
#while a >= 6:                              
#    ans += 1                               
#    n6 = num(6,a)                          
#    n9 = num(9,a)                          
#    if a >= 12 and a <= 14:                
#        a = a - n6                         
#    elif n6 < n9:                          
#        a = a -n9                          
#    else:                                  
#        a = a - n6                         
def ttt(a):                                 
    if a <= 5:                              
        return a                            
    else:                                   
        n6 = num(6,a)                       
        n9 = num(9,a)                       
        return min(ttt(a-n9),ttt(a-n6)) + 1 
print(ttt(a))

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
d = deque()
move = deque()
memo = {0:0}
for i in range(N):
    tmp = 6**i
    if tmp > N:
        break
    else:
        move.append(tmp)
for i in range(N):
    tmp = 9**i
    if tmp > N:
        break
    else:
        move.append(tmp)

move.reverse()
d.append((0,0))
flag = True
while(flag):
    tmp = d.pop()
    for i in move:
        tmp2 = (tmp[0] + i,tmp[1] + 1)
        if tmp2[0] < N:
            if not tmp2[0] in memo:
                d.appendleft(tmp2)
                memo[tmp2[0]] = tmp2[1]
            elif tmp2[1] < memo[tmp2[0]]:
                d.appendleft((tmp2, tmp[1] + 1))
                memo[tmp2] = tmp[1] + 1
        elif tmp2[0] == N:
            print(tmp2[1])
            flag = False
            break

Submission status: Accepted

Solution code:
# C
import numpy as np

N = int(input())

res = 100000

res_9 = np.zeros(100001, dtype="int32")
res_6 = np.zeros(100001, dtype="int32")
for i in range(10):
    res_9 += (np.arange(100001) // (9**i)) % 9
for j in range(10):
    res_6 += (np.arange(100001) // (6**j)) % 6

for k in range(N + 1):
    res = min(res, res_9[k] + res_6[N - k])
print(res)

Submission status: Accepted

Solution code:
import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(10000)

# Debug output
def chkprint(*args):
    names = {id(v):k for k,v in inspect.currentframe().f_back.f_locals.items()}
    print(', '.join(names.get(id(arg),'???')+' = '+repr(arg) for arg in args))

# Binary converter
def to_bin(x):
    return bin(x)[2:]

# --------------------------------------------

dp = None
mintime = 9999

def f(current, time, draws):
    global mintime

    if time > mintime:
        return 999999

    if current == 0:
        mintime = min(mintime, time)
        return time

    i = 0
    while draws[i] > current:
        i += 1

    if i + 1 == len(draws):
        return f(current - draws[i], time + 1, draws)
    else:
        return min(f(current-draws[i], time+1, draws), f(current-draws[i+1], time+1, draws))

def main():
    N = int(input())
    draws = [59049, 46656, 7776, 6561, 1296, 729, 216, 81, 36, 9, 6, 1]

    print(f(N, 0, draws))

main()

Submission status: Accepted

Solution code:
n = int(input())
v = [1,6,36,216,1296,7776,46656,9,81,729,6561,59049]
dp = [float("inf") for i in range(n+1)]
dp[0] = 0
for i in range(n):
	for j in v:
		if i + j <= n:
			dp[i+j] = min(dp[i+j], dp[i]+1)
print("{}".format(dp[n]))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
N = int(input())

wd = [1]
n = 1
while 6**n <= N:
    wd.append(6**n)
    n += 1
n = 1
while 9**n <= N:
    wd.append(9**n)
    n += 1
if N in wd:
    print(1)
    exit()
wd.sort()

INF = float('inf')
mem = [INF] * (N+1)
def dfs(n):
    if mem[n] != INF: return mem[n]
    if n < 6: return n
    mn = INF
    for d in wd[1:]:
        if n-d < 0: break
        mn = min(mn, 1 + dfs(n-d))
    mem[n] = mn
    return mn

print(dfs(N))

Submission status: Accepted

Solution code:
# ABC099A
A = int(input())
# A, B = map(int, input().split())

coins = [0]
mon = (1,6,9,36,81,216,729,1296,6561,7776,46656,59049)

for i in range(1,A+1):
    least=100
    for j in mon:
        if(len(coins)>=j):
            if(coins[i-j]<least):
                least=coins[i-j]
        else:
            break;
    coins.append(least+1)

print(coins[A])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import functools
sys.setrecursionlimit(10**6)

N = int(input())
MAXN = 10**5
six_ps = [6**i for i in range(1, 7)]
nine_ps = [9**i for i in range(1, 6)]


@functools.lru_cache(maxsize=None)
def rec(n):
    if n < 6:
        return n

    if n in six_ps or n in nine_ps:
        return 1

    six_tmps = [1 + rec(n - six_p) if six_p < n else MAXN for six_p in six_ps]
    six_tmp = min(six_tmps)

    nine_tmps = [
        1 + rec(n - nine_p) if nine_p < n else MAXN for nine_p in nine_ps
    ]
    nine_tmp = min(nine_tmps)

    return min(six_tmp, nine_tmp)


print(rec(N))

Submission status: Accepted

Solution code:
from math import pow
N = int(input())
MAX_INT = 2**32 - 1

candidate_numbers_set = set()
candidate_numbers_set.add(1)

current_num = 6
while current_num <= N:
    candidate_numbers_set.add(current_num)
    current_num *= 6

current_num = 9
while current_num <= N:
    candidate_numbers_set.add(current_num)
    current_num *= 9

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

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

print(dp[N])

Submission status: Accepted

Solution code:
n = int(input())
k = [0] * (n + 1)
for i in range(min(n + 1, 6)): k[i] = i
for i in range(6, n + 1):
    m = k[i - 1] + 1
    for j in range(1, 8):
        l = pow(6, j)
        if l > i: break
        m = min(m, k[i - l] + 1)
    for j in range(1, 8):
        l = pow(9, j)
        if l > i: break
        m = min(m, k[i - l] + 1)
    k[i] = m
print(k[n])

Submission status: Accepted

Solution code:
N = int(input())

As = [1]
As += [6 ** i for i in range(1, 7) if 6 ** i <= N]
As += [9 ** i for i in range(1, 6) if 9 ** i <= N]

As.sort(reverse=True)

Ms = [float('inf')] * (N + 1)
Ms[0] = 0
for A in As:
    for i in range(N):
        if Ms[i] != float('inf') and i + A <= N:
            Ms[i + A] = min(Ms[i + A], Ms[i] + 1)

print(Ms[N])

Submission status: Accepted

Solution code:
cost = [1]
i = 1
while 6**i <= 100000:
	cost.append(6**i)
	i += 1
i = 1
while 9**i <= 100000:
	cost.append(9**i)
	i += 1
cost.sort()
cost.reverse()

n = int(input())
ans = [0 for i in range(100001)]
for i in range(len(cost)):
	ans[cost[i]] = 1
for i in range(1,100001):
	if ans[i] == 0:
		tempans = []
		for k in range(len(cost)):
			if i-cost[k] >= 0:
				tempans.append(ans[i-cost[k]])
		ans[i] = min(tempans)+1
print(ans[n])

Submission status: Accepted

Solution code:
N=int(input())
c=1,6,9,36,81,216,729,1296,6561,7776,46656,59049

DP = [N for i in range(N + 1)]
DP[0] = 0
for cost in c:
    for i in range(cost, N + 1):
        DP[i] = min(DP[i], DP[i - cost] + 1)
print(DP[N])

Submission status: Accepted

Solution code:
n = int(input())
ba = [0] * 20000
tempSum = 0
minCount = 100000
c = 0
while 9 * c <= n:

    cSum = 0
    temp = 9 * c
    while temp > 0:
        cSum += temp % 9
        temp = temp // 9

    b = (n - 9 * c) // 6
    temp = 6 * b
    bSum = 0
    while temp > 0:
        bSum += temp % 6
        temp = temp // 6
    a = n - 9 * c - 6 * b
        
    minCount = min(minCount, a + bSum + cSum)
    
    c += 1

print(minCount)

Submission status: Accepted

Solution code:
n = int(input())
max = 100000
dp = [max for i in range(n+1)]
dp[0] = 0
div_list = [1]
j = 1
k = 1
while(j*6 <= n):
    if 6**j <= n:
        if 6**j not in div_list:
            div_list.append(6**j)
    if 9**k <= n:
        if 9**k not in div_list:
            div_list.append(9**j)
    if 6**k > n and 9**j > n:
        break
    j += 1
    k+= 1
sorted(div_list)

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

print(dp[len(dp)-1])

Submission status: Accepted

Solution code:
money = int(input())

six = [6**i for i in range(1, 8)]
nine = [9**i for i in range(1, 7)]

all = [1] + sorted(six + nine)

dp = [100000 for i in range(100001)]
dp[0] = 0

for i in range(0, 100001):
    for el in all:
        temp = i + el
        if temp < 100001:
            dp[temp] = min(dp[temp], dp[i] + 1)

print(dp[money])

Submission status: Accepted

Solution code:
# 1. priority_queue

import heapq

N = int(input())
cost = [1 << 60 for i in range(N + 1)]

que = [] ; cost[0] = 0
heapq.heappush(que, 0)

while len(que) != 0:
    elem = heapq.heappop(que)

    # 9
    for i in range(6):
        new_num = elem + 9 ** i
        if new_num <= N and cost[new_num] > cost[elem] + 1:
            cost[new_num] = cost[elem] + 1
            heapq.heappush(que, new_num)

    # 6
    for i in range(7):
        new_num = elem + 6 ** i
        if new_num <= N and cost[new_num] > cost[elem] + 1:
            cost[new_num] = cost[elem] + 1
            heapq.heappush(que, new_num)

ans = 1 << 60
for i in range(N + 1):
    ans = min(ans, cost[i] + (N - i))
print(ans)