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

Solution (Python):
from sys import stdin
N = int(stdin.readline().rstrip())
six_pows = [6**i for i in range(10)]
nine_pows = [9**i for i in range(10)]

ans = float("inf")

for i in range(N+1):
    count = 0
    tmp = i
    while tmp > 0:
        j = 0
        while six_pows[j] <= tmp:
            j += 1
        tmp -= six_pows[j-1]
        count += 1 

    tmp = N - i
    while tmp > 0:
        j = 0
        while nine_pows[j] <= tmp:
            j += 1
        tmp -= nine_pows[j-1]
        count += 1
    
    ans = min(ans, count)

print(ans)

Solution (Python):
N=int(input())
def cou(n,x):
    i=0
    while(n>0):
        i+=n%x
        n//=x
    return i
ans=N

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

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

Solution (Python):
MAXINT = 100010    


N = int(input())


dp = [MAXINT] * (N + 1)


dp[0] = 0


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

print(dp[N])

Solution (Python):
n = int(input())
dp = [float('inf')] * 100010

dp[0] = 0

for i in range(n + 1):

  dp[i] = min(dp[i], dp[i-1] + 1)

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

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


print(dp[n])

Solution (Python):
N = int(input())
dp = [10**20]*(N+10)
dp[0] = 0
for i in range(N+10):
    k = 0
    j = 1
    while i-6**k >= 0:
        dp[i] = min(dp[i-6**k]+1,dp[i])
        k += 1
    while i-9**j >= 0:
        dp[i] = min(dp[i-9**j]+1,dp[i])
        j += 1
print(dp[N])

Solution (Python):
N = int(input())
dp = [10**20]*(N+10)
dp[0] = 0
for i in range(N+10):
    k = 0
    j = 1
    while i-6**k >= 0:
        dp[i] = min(dp[i-6**k]+1,dp[i])
        k += 1
    while i-9**j >= 0:
        dp[i] = min(dp[i-9**j]+1,dp[i])
        j += 1
print(dp[N])

Solution (Python):
n = int(input())

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

    res = min(res, cnt)

print(res)

Solution (Python):
import sys
import os
from sys import stdin
import math


input = stdin.readline
sys.setrecursionlimit(20000000)


N = int(input())
i_6 = math.ceil(math.log(N, 6))
i_9 = math.ceil(math.log(N, 9))

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

for i in range(N):
    for j in range(i_6 + 1):
        if (i + 6 ** j) > N:
            break
        if dp[i] < dp[i + 6 ** j]:
            dp[i + 6 ** j] = dp[i] + 1

    for k in range(i_9 + 1):
        if (i + 9 ** k) > N:
            break
        if dp[i] < dp[i + 9 ** k]:
            dp[i + 9 ** k] = dp[i] + 1

print(dp[N])

Solution (Python):
import sys
import os
from sys import stdin
import math


input = stdin.readline
sys.setrecursionlimit(20000000)


N = int(input())
i_6 = math.ceil(math.log(N, 6))
i_9 = math.ceil(math.log(N, 9))

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

for i in range(N):
    for j in range(i_6 + 1):
        if (i + 6 ** j) > N:
            break
        if dp[i] < dp[i + 6 ** j]:
            dp[i + 6 ** j] = dp[i] + 1

    for k in range(i_9 + 1):
        if (i + 9 ** k) > N:
            break
        if dp[i] < dp[i + 9 ** k]:
            dp[i + 9 ** k] = dp[i] + 1

print(dp[N])

Solution (Python):
n = int(input())
coins = [1]

i = 1
while True:
  coin = 6**i
  if coin > 100000:
    break
  coins.append(coin)
  i += 1

i = 1
while True:
  coin = 9**i
  if coin > 100000:
    break
  coins.append(coin)
  i += 1

dp = [0] * (n+1)

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

print(dp[n])

Solution (Python):
n=int(input())
dp=list(range(n+1))
C=[]
i=1
while n>=6**i:
    C.append(6**i)
    C.append(9**i)
    i+=1
i=1
while n>=9**i:
    C.append(9**i)
    i+=1
C.sort()


for c in C:
    for i in range(n+1):
        if i-c<0:continue
        dp[i]=min(dp[i],dp[i-c]+1)
print(dp[-1])

Solution (Python):
n=int(input())
dp=list(range(n+1))
C=[]
i=1
while n>=6**i:
    C.append(6**i)
    i+=1
i=1
while n>=9**i:
    C.append(9**i)
    i+=1
C.sort()


for c in C:
    for i in range(n+1):
        if i-c<0:continue
        dp[i]=min(dp[i],dp[i-c]+1)
print(dp[-1])

Solution (Python):
input_num = int(input())

combinations = [(row1, row2, row3, row4, row5, row6)
               for row1 in range(0, 6)
               for row2 in range(0, 6)
               for row3 in range(0, 6)
               for row4 in range(0, 6)
               for row5 in range(0, 6)
               for row6 in range(0, 6)]


num_list = []

for i in combinations:
  row1, row2, row3, row4, row5, row6 = i
  draw = 6 ** 1 * row1 ++ 6 ** 2 * row2 + 6 ** 3 * row3 + 6 ** 4 * row4 + 6 ** 5 * row5 + 6 ** 6 * row6
  if draw > input_num:
    continue
  else:
    result = input_num - draw
    draw_list = sum(i)
    for n in reversed(range(1, 6)):
      draw_n = result // 9 ** n
      result -= 9 ** n * draw_n
      draw_list += draw_n
    draw_list += result
    num_list.append(draw_list)
    
print(str(min(num_list)))

Solution (Python):
N=int(input())
INF=10**9
dp=[INF]*(N+1)
dp[0]=0
list=[1]
i=1
while(6**i<=N):
    list.append(6**i)
    i+=1
i=1
while(9**i<=N):
    list.append(9**i)
    i+=1
for i in range(N+1):
    for k in list:
        if i+k<=N:
            dp[i+k]=min(dp[i+k],1+dp[i])
print(dp[N])

Solution (Python):





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 Base_n_to_10(X,n):
    out = 0
    for i in range(1,len(str(X))+1):
        out += int(str(X)[-i])*(n**(i-1))
    return out


N = int(input())

after_draw_9 = []
for i in range(N // 9 + 1):
  cost_9 = sum(map(int, Base_10_to_n(9*i,9)))
  after_draw_9.append((N-9*i, cost_9))


solver = []
for i in range(len(after_draw_9)):
  cost_6 = sum(map(int, Base_10_to_n(after_draw_9[i][0], 6)))
  solver.append(after_draw_9[i][1] + cost_6)
  

print(min(solver))

Solution (Python):
N = int(input())

L =[1,6**1,6**2,6**3,6**4,6**5,6**6,9**1,9**2,9**3,9**4,9**5]
X = [0]*(N+1)
for i in range(1, N+1):
    X[i] = 100000

for i in range(N+1):
    for l in L:
        if i+l <= N:
            X[i+l] = min(X[i] + 1, X[i+l])
        
print(X[-1])

Solution (Python):
from collections import deque
INF = float('inf')
n = int(input())
g = {i: [] for i in range(n + 1)}
for i in range(n):
    g[i].append(i + 1)
    num = 6
    while num <= n:
        g[i].append(i + num)
        num *= 6
    num = 9
    while num <= n:
        g[i].append(i + num)
        num *= 9
queue = deque([0])
dist = [INF] * (n + 1)
dist[0] = 0
while queue:
    c = queue.pop()
    for node in g[c]:
        if node <= n and dist[node] == INF:
            queue.appendleft(node)
            dist[node] = dist[c] + 1
print(dist[n])

Solution (Python):
N = int(input())

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

Solution (Python):
import sys


sys.setrecursionlimit(1000000)


MAX_N = 100001

memo = [-1] * MAX_N


def f(n):
    
    if n == 0:
        return 0
    
    if memo[n] != -1:
        return memo[n]

    res = sys.maxsize

    pow9 = 1
    while pow9 <= N:
        if n - pow9 < 0:
            break
        res = min(res, f(n-pow9)+1)
        pow9 *= 9


    pow6 = 1
    while pow6 <= N:
        if n - pow6 < 0:
            break
        res = min(res, f(n-pow6)+1)
        pow6 *= 6

    
    memo[n] = res

    return res


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

    print(f(N))

Solution (Python):
import sys


sys.setrecursionlimit(1000000)


MAX_N = 100001

memo = [-1] * MAX_N


def f(n):
    
    if n == 0:
        return 0
    
    if memo[n] != -1:
        return memo[n]

    res = sys.maxsize

    pow9 = 1
    while pow9 <= N:
        if n - pow9 < 0:
            break
        
        
        res = min(res, f(n-pow9)+1)
        pow9 *= 9

    pow6 = 1
    while pow6 <= N:
        if n - pow6 < 0:
            break
        res = min(res, f(n-pow6)+1)
        pow6 *= 6

    
    memo[n] = res

    return res


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

    print(f(N))

Solution (Python):
n=int(input())

ans=n
for i in range(n+1):
    count=0
    pow6=6
    while pow6<=i:
        count+= (i%(pow6*6))//pow6
        pow6*=6
    pow9=9
    while pow9<=n-i:
        count+= ((n-i)%(pow9*9))//pow9
        pow9*=9
    count+= (i%6)+((n-i)%9)
    ans=min(ans,count)
print(ans)

Solution (Python):


def get_sum_digits(n, m):
    r = 0
    while n:
        r, n = r + n % m, n // m
    return r

N = int(input())
ans = 10*5
for i in range(N+1):
    ans = min(ans, get_sum_digits(i, 6) + get_sum_digits(N-i, 9))
print(ans)

Solution (Python):
N=int(input())
def cou(n,x):
    i=0
    while(n>0):
        i+=n%x
        n//=x
    return i
ans=N
for j in range(N+1):
    ans=min(ans,cou(j,6)+cou(N-j,9))
print(ans)

Solution (Python):
l9 = []
l9.append(1)
tmp = 1
while tmp <= 10**5:
  tmp *= 9
  l9.append(tmp)
l6 = []
l6.append(1)
tmp = 1
while tmp <= 10**5:
  tmp *= 6
  l6.append(tmp)

  
import bisect 
n = int(input())
ans = 10**6

for i in range(0, n+1):

  a = i
  b = n - i
  p = 0
  while a > 0:
    idx = bisect.bisect_left(l6, a)
    if a == l6[idx]:
      a -= l6[idx]
    else:
      a -= l6[idx-1]
    p += 1
    
  q = 0
  while b > 0:
    idx = bisect.bisect_left(l9, b)
    if b == l9[idx]:
      b -= l9[idx]
    else:
      b -= l9[idx-1]
    q += 1
    
  ans = min(ans, p+q)

print(ans)

Solution (Python):
n = int(input())
ans = 10**6
for i in range(0, n+1):
  cnt = 0
  
  a = i
  b = n - i
  p = 0
  
  while a > 0:
    p += a % 6 
    a = a // 6
    
  q = 0
  while b > 0:
    q += b % 9
    b = b // 9
    
  ans = min(ans, p+q)
  
  
print(ans)

Solution (Python):

N=int(input())
dp = [N]*100001
dp[0]=0
for i in range(1,N+1):
    temp = 1
    while temp <= i:
        dp[i]=min(dp[i], dp[i-temp] + 1)
        temp *= 6

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

print(dp[N])

Solution (Python):
n = int(input())

def ind6(x):
    j = 0
    while 6 ** (j + 1) <= x:
        j += 1
    return j
def ind9(x):
    j = 0
    while 9 ** (j + 1) <= x:
        j += 1
    return j
    
ans = [1000] * 100001

for i in range(6):
    ans[i] = i 

for i in range(100001):
    if ans[i] == 1000:
        ans[i] = min(ans[i-1]+1,ans[i-6**ind6(i)]+1,ans[i-9**ind9(i)]+1)
print(ans[n])

Solution (Python):
n=int(input())

dp=[0]*100010
dp[0]=0


for i in range(1,100010):
  n6=0
  n9=0
  li=[]
  while 6**(n6+1)<=i:
    n6+=1
  while 9**(n9+1)<=i:
    n9+=1
  for j in range(n6+1):
    li.append(dp[i-6**n6])
  for jj in range(n9+1):
    li.append(dp[i-9**n9])
  dp[i]=min(li)+1
print(dp[n])

Solution (Python):


N = int(input())

MAX = 100000

dp = [0]*(N+1)

coins = [1]
for d in range(1,10):
    t = 6 ** d
    if t > MAX:
        break
    coins.append(t)

for d in range(1,10):
    t = 9 ** d
    if t > MAX:
        break
    coins.append(t)

coins.sort()





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

    for c in coins[1:]:
        for i in range(c, N+1):
            if dp[i-c] + 1 < dp[i]:
                dp[i] = dp[i-c]+1
    return dp[N]
print(solve(N))

Solution (Python):
n = int(input())
ans = n
l9 = [9**i for i in range(6,0,-1)]
l6 = [6**i for i in range(7,-1,-1)]
for i in range(n//9+1):
  x9 = i*9
  x61= n-x9
  csum = 0
  for x in l9:
    csum += x9//x
    x9 %= x
  for x in l6:
    csum += x61//x
    x61 %= x
  if ans > csum:
    ans = csum
print(ans)

Solution (Python):
n=int(input())
a=n
for i in range(n+1):
    ni,si=i,n-i
    m=0
    while ni!=0:m+=ni%9;ni//=9
    while si!=0:m+=si%6;si//=6
    a=min(a,m)
print(a)

Solution (Python):
n=int(input())
a=n
for i in range(n+1):
  ni,si=i,n-i
  m=0
  while ni!=0:m+=ni%9;ni//=9
  while si!=0:m+=si%6;si//=6
  a=min(a,m)
print(a)

Solution (Python):
N = int(input())

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

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

for n in range(1, N + 1):
	dp[n] = min([dp[n - f] + 1 if 0 <= n - f else INF for f in l])
	
print(dp[-1])

Solution (Python):
N = int(input())

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

INF = 10 ** 3
dp = [0] + [INF] * N

for n in range(1, N + 1):
	
	for f in l:
		if 0 <= n - f:
			dp[n] = min([dp[n], dp[n - f] + 1])
			
print(dp[-1])

Solution (Python):
N = int(input())
M = 100

ans = 0
dp = [99999] * 100010

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

Solution (Python):
def solve(N: int):
    coins = set()
    coins.add(1)
    i = 1
    while 6**i <= N:
        coins.add(6**i)
        i += 1
    i = 1
    while 9**i <= N:
        coins.add(9**i)
        i += 1
         

    dp = [float('inf')] * (N + 1)
    dp[0] = 0
    
    for n in range(1, N + 1):
        for coin in coins:
            if n - coin >= 0:
                dp[n] = min(dp[n - coin] + 1, dp[n])
                
    return dp[N]
N = int(input())
print(solve(N))

Solution (Python):
def smaller(x, y):
	if x < y: return x
	return y

nine = []
six = []
a = 9
while a <= 100000:
	nine.append(a)
	a *= 9
a = 6
while a <= 100000:
	six.append(a)
	a *= 6

dp = [0]
for i in range(1, 100001):
	min = dp[i-1]+1
	for j in range(0, len(nine)):
		if i < nine[j]: break
		min = smaller(min, dp[i-nine[j]]+1)
	for j in range(0, len(six)):
		if i < six[j]: break
		min = smaller(min, dp[i-six[j]]+1)
	dp.append(min)
print dp[int(raw_input())]

Solution (Python):
n = int(input())

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

dp[0] = 0

for i in range(1, 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])

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

Solution (Python):
N = int(input())

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

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

Solution (Python):
N = int(input())
ans = N

for i in range(N + 1):
    cnt = 0
    t1 = i
    t2 = N - i
    while t1 > 0:
        cnt += t1 % 6
        t1 //= 6

    while t2 > 0:
        cnt += t2 % 9
        t2 //= 9
        
    ans = min(ans, cnt)

print(ans)

Solution (Python):

import sys
input = sys.stdin.readline

n = int(input())
ans = n
for x in range(n+1):
    c = 0
    t = x
    for i in range(10**5):
        c += t%6
        t //= 6
        if t <= 0:
            break
    t = n-x
    for j in range(10**5):
        c += t%9
        t //= 9
        if t <= 0:
            break
    if ans > c:
        ans = c
print(ans)

Solution (Python):
n = int(input())

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

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

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

print(dp[n])

Solution (Python):
n = int(input())

dp = [10**5] *(n+1)

dp[0] = 0

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

Solution (Python):
n = int(input())
ans = n
for i in range(n+1):
    c = 0
    t = i
    while(t > 0):
        c += t%6
        t //= 6
    t = n-i
    while(t > 0):
        c += t%9
        t //= 9
    if ans > c:
        ans = c
print(ans)

Solution (Python):
N = int(input())

min_count = N
for i in range(N + 1):

    count = 0

    six = i
    while six > 0:
        count += six % 6
        six //= 6

    nine = N - i
    while nine > 0:
        count += nine % 9
        nine //= 9

    min_count = min(min_count, count)

print(min_count)

Solution (Python):
N = int(input())

dp = [float('inf')]* 100001

SIXL = [ 6**i for i in range(0,7)]
NINEL = [9**i for i in range(0,6)]
X = sorted(SIXL + NINEL)
dp = [float('inf')]*(N+1)
dp[0] = 0
for i in range(1,N+1):
  for j in X:
    if i-j >= 0:
      dp[i] = min(dp[i],dp[i-j] + 1)
print(dp[-1])

Solution (Python):
import sys, os

f = lambda:list(map(int,input().split()))
if 'local' in os.environ :
    sys.stdin = open('./input.txt', 'r')

def solve():
    n = f()[0]
    dp = [0] * (n+1)

    dp[1] = 1

    for i in range(2, 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])

solve()

Solution (Python):
def f(num, base):
    ret = 1
    while num >= ret:
        ret *= base
    return ret // base


a = {int(input())}
cnt = 0
while all(a):
    a = {x - f(x, 6) for x in a} | {x - f(x, 9) for x in a}
    cnt += 1

print(cnt)

Solution (Python):


import sys


s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N = i2n()
    coins = [1]
    d = 6
    while d <= N:
        coins.append(d)
        d *= 6
    d = 9
    while d <= N:
        coins.append(d)
        d *= 9
    dp = [0] * (N+1)
    for i in range(1, N+1):
        n = 100000
        for c in coins:
            if i - c < 0:
                continue
            t = dp[i-c] + 1
            if t < n:
                n = t
        dp[i] = n
    print(dp[N])

main()

Solution (Python):


import sys


s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N = i2n()
    coins = [1]
    d = 6
    while d <= N:
        coins.append(d)
        d *= 6
    d = 9
    while d <= N:
        coins.append(d)
        d *= 9
    dp = [0] * (N+1)
    for i in range(1, N+1):
        n = 100000
        for c in coins:
            if i - c < 0:
                continue
            t = dp[i-c] + 1
            if t < n:
                n = t
        dp[i] = n
    print(dp[N])

main()

Solution (Python):
n=int(input())
dp=[0]
for i in range(1,n+1):
    if i<6:
        dp.append(dp[i-1]+1)
    elif 6<=i<9:
        dp.append(dp[i-6]+1)
    else:
        i6=i
        count6=0
        while i6>=6:
            i6=i6/6
            count6=count6+1
        a=dp[i-6**count6]+1
        i9=i
        count9=0
        while i9>=9:
            i9=i9/9
            count9=count9+1
        b=dp[i-9**count9]+1
        dp.append(min(a,b))
print(dp[n])

Solution (Python):
n = int(input())
res=n
for i in range(n+1):
    cc,t = 0,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)

Solution (Python):
import sys
input = sys.stdin.readline

n = int(input())
dp = [sys.maxsize] * 110000
dp[0] = 0

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

Solution (Python):


N = int(input())

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

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


print (dp[N])

Solution (Python):

import sys


def solve(N: int):
    dp = list(range(N + 1))
    for i in [6,9]:
        j = 1
        while i ** j <= N:
            base = i ** j
            idx = 0
            while idx + base <= N:
                dp[idx + base] = min(dp[idx + base], dp[idx] + 1)
                idx += 1
            j += 1
    
    ret = dp[N]
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    solve(N)

if __name__ == '__main__':
    main()

Solution (Python):


from sys import stdout
from bisect import bisect_left as binl
from copy import copy, deepcopy
from collections import defaultdict


mod = 1


def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return tuple(map(int, input_tuple))


def intina():
    return [int(i) for i in input().split()]


def intinl(count):
    return [intin() for _ in range(count)]


def modadd(x, y):
    global mod
    return (x + y) % mod


def modmlt(x, y):
    global mod
    return (x * y) % mod


def lcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


def combination(x, y):
    assert(x >= y)

    if y > x // 2:
        y = x - y

    ret = 1

    for i in range(0, y):
        j = x - i
        i = i + 1

        ret = ret * j
        ret = ret // i

    return ret


def get_divisors(x):
    retlist = []
    for i in range(1, int(x**0.5) + 3):
        if x % i == 0:
            retlist.append(i)
            retlist.append(x // i)
    return retlist


def get_factors(x):
    retlist = []
    for i in range(2, int(x**0.5) + 3):
        while x % i == 0:
            retlist.append(i)
            x = x // i
    retlist.append(x)
    return retlist


def make_linklist(xylist):
    linklist = {}
    for a, b in xylist:
        linklist.setdefault(a, [])
        linklist.setdefault(b, [])
        linklist[a].append(b)
        linklist[b].append(a)
    return linklist


def calc_longest_distance(linklist, v=1):
    distance_list = {}
    distance_count = 0
    distance = 0
    vlist_previous = []
    vlist = [v]
    nodecount = len(linklist)

    while distance_count < nodecount:
        vlist_next = []
        for v in vlist:
            distance_list[v] = distance
            distance_count += 1
            vlist_next.extend(linklist[v])
        distance += 1
        vlist_to_del = vlist_previous
        vlist_previous = vlist
        vlist = list(set(vlist_next) - set(vlist_to_del))

    max_distance = -1
    max_v = None
    for v, distance in distance_list.items():
        if distance > max_distance:
            max_distance = distance
            max_v = v

    return (max_distance, max_v)


def calc_tree_diameter(linklist, v=1):
    _, u = calc_longest_distance(linklist, v)
    distance, _ = calc_longest_distance(linklist, u)
    return distance





def main():
    n = intin()

    ans = n

    for i in range(n // 6 + 1):
        count = 0

        s6 = i * 6
        ii = i
        for j in range(1, n + 1):
            scount = ii % 6
            count += scount
            ii = ii // 6
            s6 -= (6**j) * scount
            if not s6:
                break

        s9 = n - i * 6
        ii = s9

        for j in range(0, n + 1):
            scount = ii % 9
            count += scount
            ii = ii // 9
            s9 -= (9**j) * scount
            if not s9:
                break

        ans = min(ans, count)

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
n=int(input())
dp=[0]+[10**6]*100010

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

print(dp[n])

Solution (Python):
import math

N = int(input())

ans = N
for i in range(N+1):
    tmp_ans = 0
    tmp_N = i
    while tmp_N > 0:
        tmp_ans += tmp_N % 9
        tmp_N //= 9
    tmp_N = N-i
    while tmp_N > 0:
        tmp_ans += tmp_N % 6
        tmp_N //= 6
    ans = min(ans, tmp_ans)
print(ans)

Solution (Python):
n=int(input())
l=[1]
for i in [6,9]:
    x=i
    while x<=n:
        l.append(x)
        x*=i
dp=[10**9]*(n+1)
dp[0]=0
for x in l:
    for i in range(n):
        if i+x<=n:dp[i+x]=min(dp[i+x],dp[i]+1)
        else:break
print(dp[n])

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

Solution (Python):

def getNumCoin(C,n):
    T=[float('inf') for i in range(n+1)]
    T[0]=0
    m=len(C)
    
    for i in range(m):
        for j in range(C[i],n+1):
            T[j]=min(T[j], T[j-C[i]]+1)
    return T[n]
  
N=int(input())
nine=[0,1,9,9**2,9**3,9**4,9**5]
six=[6,6**2,6**3,6**4,6**5,6**6]
L=sorted(nine+six)
print(getNumCoin(L,N))

Solution (Python):


import math
import heapq


def nine(n):
  ret = 0
  for r in range(6,0,-1):
    p,n = divmod(n,9**r)
    ret += p
  return ret+n

def six(n):
  ret = 0
  for r in range(7,0,-1):
    p,n = divmod(n,6**r)
    ret += p
  return ret+n



if __name__ == "__main__":
  N = int(input())
  heap_q = []
  for l in range(N+1):
    heapq.heappush(heap_q,nine(l)+six(N-l))
  print(heapq.heappop(heap_q))

Solution (Python):


import math



def nine(n):
  ret = 0
  for r in range(6,0,-1):
    p,n = divmod(n,9**r)
    ret += p
  return ret+n

def six(n):
  ret = 0
  for r in range(7,0,-1):
    p,n = divmod(n,6**r)
    ret += p
  return ret+n



if __name__ == "__main__":
  N = int(input())
  ans = [N for _ in range(N+1)]
  for l in range(N+1):
    ans[l] = nine(l)+six(N-l)
  print(min(ans))

Solution (Python):


import math



def nine(n):
  ret = 0
  for r in range(6,0,-1):
    p,n = divmod(n,9**r)
    ret += p
  return ret+n

def six(n):
  ret = 0
  for r in range(7,0,-1):
    p,n = divmod(n,6**r)
    ret += p
  return ret+n



if __name__ == "__main__":
  N = int(input())
  ans = N
  for l in range(N+1):
    ans = min(ans,nine(l)+six(N-l))
  print(ans)

Solution (Python):
N = int(input())
INF = 10 ** 6
six = [[6 ** i * j for j in range(1, 6)] for i in range(1, 7)]
nin = [[9 ** i * j for j in range(1, 9)] for i in range(1, 6)]
dp = [INF] * (100010)
dp[0] = 0
for p in [6, 9]:
    for n in range(1, 10 ** 5 + 1):
        power = 1
        while power <= n:
            dp[n] = min(dp[n], dp[n - power] + 1)
            power *= p
print(dp[N])

Solution (Python):
n=int(input())
dp=[0]*n
l69=sorted([1]+[6**i for i in range(1,7)]+[9**i for i in range(1,6)])
g=0
for i in range(n):
    for j in range(len(l69)):
        if i+1-l69[j]>=0:
            g=j
    dp[i]=min(dp[i-p]+1 for p in l69[:g+1])

print(dp[n-1])

Solution (Python):
import bisect

def main():
    buf = input()
    N = int(buf)
    withdrawal = []
    withdrawal += [int(6 ** x) for x in range(10)]
    withdrawal += [int(9 ** x) for x in range(10)]
    withdrawal = list(sorted(withdrawal))
    stack = [[N, 0]]
    best = 999
    while stack:
        current = stack.pop()
        if current[1] > best:
            continue
        if current[0] == 0:
            if current[1] < best:
                best = current[1]
            continue
        point = bisect.bisect_right(withdrawal, current[0])
        stack.append([current[0]-withdrawal[point-1], current[1]+1])
        stack.append([current[0]-withdrawal[point-2], current[1]+1])
    print(best)

if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
Inf = float("inf")
dp = [Inf]*(N+1)
dp[0] = 0
for i in range(1,N+1):
        still1 = 1
        while still1 <= N:
                dp[i] = min(dp[i],1+dp[i-still1])
                still1 *= 6
        still2 = 1
        while still2 <= N:
                dp[i] = min(dp[i],1+dp[i-still2])
                still2 *= 9
print(dp[i])

Solution (Python):
N=int(input())
list=[1]
i=1
while(6**i<=N):
    list.append(6**i)
    i+=1
i=1
while(9**i<=N):
    list.append(9**i)
    i+=1
dp=[0 for i in range(N+1)]

for i in range(N):
    kouho=10**9
    for k in list:
        if i+1-k>=0:
            kouho=min(kouho,dp[i+1-k]+1)
    dp[i+1]=kouho
print(dp[N])

Solution (Python):


def main():
    num = int(input())
    ans = 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 ans > cc:
            ans = cc

    print(ans)



if __name__ == '__main__':
    main()

Solution (Python):
n=int(input())
l9=list(9**i for i in range(1,6))
l6=list(6**j for j in range(1,8))
l=sorted(l9+l6)
dp=[_ for _ in range(100010)]
for k in l:
    for m in range(k,n+1):
        dp[m]=min(dp[m-k]+1,dp[m])
print(dp[n])

Solution (Python):
n=int(input())
ll=[6,9,36,81,216,729,1296,6561,7776,46656,59049]
dp=[i for i in range(100010)]

for l in ll:
    for x in range(l,n+1):
        dp[x]=min(dp[x],dp[x-l]+1)
print(dp[n])

Solution (Python):
N = int(input())

def f9(a,i):
    if a < 9**i:
        return i-1
    return f9(a,i+1)

def f6(a,i):
    if a < 6**i:
        return i-1
    return f6(a,i+1)

def func(a,ans):
    if a < 6:
        return ans+a
    elif a < 9:
        return ans+1+(a-6)
    return min(func(a-6**f6(a,0),ans+1),func(a-9**f9(a,0),ans+1))

print(func(N,0))