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):
N = int(input())

INF = 10 ** 5 + 1

dp = [0 for _ in range(INF)]

for n in range(1, N + 1):
    dp[n] = INF
    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
import math
from collections import defaultdict


sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]


mod = 10**9 + 7


def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))



N = I()

val = [1]
temp = 1
while 1:
    temp *= 6
    if temp<=10**5:
        val.append(temp)
    else:
        break

temp = 1
while 1:
    temp *= 9
    if temp<=10**5:
        val.append(temp)
    else:
        break

val.sort(reverse=True)

def rec(price,i):
    if i==len(val)-1:
        return price
    else:
        q,m = divmod(price,val[i])
        if m==0:
            return q
        else:
            if q>=9:
                return float('inf')
            else:
                x = []
                for j in range(q+1):
                    x.append(rec(price-j*val[i],i+1) + j)
                return min(x)

print(rec(N,0))

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

Solution (Python):


N = int(input())

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

print(ans)

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

Solution (Python):


class Method1:
  def __init__(self, N):
    self.N = N
    self.memo = [-1] * 110000
  
  def rec(self,n):
    if n == 0:
      return 0
    if self.memo[n] != -1:
      return self.memo[n]
    res = n
    cnt = 0
    while 6 ** cnt <= n:
      res = min(res, self.rec(n - 6 ** cnt) + 1)
      cnt += 1
    cnt = 0
    while 9 ** cnt <= n:
      res = min(res, self.rec(n - 9 ** cnt) + 1)
      cnt += 1
    self.memo[n] = res
    return res

  def ans(self,):
    print(self.rec(self.N))
    

class Method2():
  def __init__(self, N):
    self.N = N
    self.dp = [N] * 110000
  def ans(self, ):
    self.dp[0] = 0
    for n in range(1,self.N + 1):
      cnt = 0
      while 6 ** cnt <= n:
        self.dp[n] = min(self.dp[n], self.dp[n - 6 ** cnt] + 1)
        cnt += 1
      cnt = 0
      while 9 ** cnt <= n:
        self.dp[n] = min(self.dp[n], self.dp[n - 9 ** cnt] + 1)
        cnt += 1
    print(self.dp[self.N])


class Method3():
  def __init__(self, N):
    self.N = N
    self.dp = [N] * 110000
    
if __name__ == '__main__':
  inputN = int(input())
  
  method = Method2(inputN)
  method.ans()

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

Solution (Python):
def main():
    N = int(input())
    dp = [float('inf') for _ in range(N+1)]
    dp[0] = 0
    cand = [1]
    p = 6
    while p <= N:
        cand.append(p)
        p *= 6
    p = 9
    while p <= N:
        cand.append(p)
        p *= 9

    for i in range(1, N+1):
        for j in cand:
            if i-j >= 0:
                dp[i] = min(dp[i], dp[i-j]+1)
    return dp[N]


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

Solution (Python):

n = int(input())
a = [1]
i = 6
while i <= n:
  a.append(i)
  i *= 6
i = 9
while i <= n:
  a.append(i)
  i *= 9
t = [0] * (n + 1)
for i in range(1, n + 1):
  k = float("inf")
  for j in a:
    if i - j >= 0 and k > t[i - j] + 1:
      k = t[i - j] + 1
  t[i] = k
print(t[n])

Solution (Python):

n = int(input())
a = [1]
i = 6
while i <= n:
  a.append(i)
  i *= 6
i = 9
while i <= n:
  a.append(i)
  i *= 9
t = [float("inf")] * (n + 1)
t[0] = 0
for i in range(1, n + 1):
  k = float("inf")
  for j in a:
    if i - j >= 0 and k > t[i - j] + 1:
      k = t[i - j] + 1
  t[i] = k
print(t[n])

Solution (Python):
n = int(input())
a = [1]
i = 6
while i <= n:
  a.append(i)
  i *= 6
i = 9
while i <= n:
  a.append(i)
  i *= 9
t = [float("inf")] * (n + 1)
t[0] = 0
for i in range(n):
  for j in a:
    if i + j <= n and t[i + j] > t[i] + 1:
      t[i + j] = t[i] + 1
print(t[n])

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

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

arr = [1,6,9]

for i in range(len(arr)):
    oriArrVal = arr[i]
    val = arr[i]
    while val <= N:
        index = val
        while index <= N:
            dp[index] = min(dp[index],dp[index - val]+1)
            index += 1
            
        if oriArrVal == 1:
            val += index
        else : val *= oriArrVal

print(dp[N])

Solution (Python):
def resolve():
    N=int(input())
    mini=10**10
    for i in range(N+1):
        j=N-i
        mini=min(mini,f(i,6)+f(j,9))
    print(mini)


def f(n,m):
    i=0
    while n>0:
        i=i+n%m
        n=n//m
    return(i)
resolve()

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

n = int(input())

dp = [0] * (n+1)

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

print(dp[-1])

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








memo = [[N * 2] * (N + 1) for _ in range(15)]
memo[0][0] = 0

values = []

i = 1
while i <= N:
    values.append(i)
    i *= 6
i = 9
while i <= N:
    values.append(i)
    i *= 9

for i in range(len(values)):
    v = values[i]
    for w in range(N + 1):
        if v > w:
            memo[i + 1][w] = memo[i][w]
        else:
            memo[i + 1][w] = min(memo[i][w], memo[i + 1][w - v] + 1)
print(memo[len(values)][N])

Solution (Python):
import numpy  as np

N = int(input())


def make_array(shape, defval=0, dtype=int):
    res = np.zeros(shape, dtype)
    res[:] = defval
    return res.tolist()


memo = make_array((15, N + 1), N * 2)
memo[0][0] = 0

values = []

i = 1
while i <= N:
    values.append(i)
    i *= 6
i = 9
while i <= N:
    values.append(i)
    i *= 9

for i in range(len(values)):
    v = values[i]
    for w in range(N + 1):
        if v > w:
            memo[i + 1][w] = memo[i][w]
        else:
            memo[i + 1][w] = min(memo[i][w], memo[i + 1][w - v] + 1)
print(memo[len(values)][N])

Solution (Python):
import numpy  as np

N = int(input())




memo = np.zeros((15, N + 1),int)
memo[:, :] = N * 2
memo = memo.tolist()
memo[0][0] = 0

values = []

i = 1
while i <= N:
    values.append(i)
    i *= 6
i = 9
while i <= N:
    values.append(i)
    i *= 9

for i in range(len(values)):
    v = values[i]
    for w in range(N+1):
        if v > w:
            memo[i + 1][w] = memo[i][w]
        else:
            memo[i + 1][w] = min(memo[i][w], memo[i+1][w - v] + 1)
print(int(memo[len(values)][N]))

Solution (Python):
n=int(input())
dp=list(range(110000))
for i in range(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())
memo = [-1] * (n+1)
import sys
sys.setrecursionlimit(1000000)
def f(n):
    if n == 0:
        return 0
    if memo[n] != -1:
        return memo[n]
    res = n
    pow6 = 1
    pow9 = 1
    res = min(res, f(n - 1) + 1)
    while pow6*6 <= n:
        pow6 *= 6
        res = min(res, f(n - pow6) + 1)
        
    while pow9*9 <= n:
        pow9 *= 9
        res = min(res, f(n - pow9) + 1)
        
    memo[n] = res
    return res
print(f(n))

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

Solution (Python):
N = int(input())
dp = [1e10]*(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):
import bisect
N = int(input())

ans = N
sixs = [1]
i = 6
while i <= N:
    sixs.append(i)
    i *= 6
nines = [1]
i = 9
while i <= N:
    nines.append(i)
    i *= 9

for i in range(N+1):
    
    cnt = 0
    a = i
    b = N-i
    while a > 0:
        idx = bisect.bisect_right(sixs, a)
        cnt += a // sixs[idx-1]
        a -= (a // sixs[idx-1]) * sixs[idx-1]

    while b > 0:
        idx = bisect.bisect_right(nines, b)
        cnt += b // nines[idx-1]
        b -= (b // nines[idx-1]) * nines[idx-1]

    ans = min(ans, cnt)

print(ans)

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

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


dp=list(range(n+1))

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

print(dp[-1])

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

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


dp=list(range(n+1))

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

print(dp[-1])

Solution (Python):



def get_all_values(N, v):
    all_values = []

    current = v
    while current <= N:
        all_values.append(current)
        current *= v

    return all_values


def get_min_number(memo, all_values, N):
    if N in memo:
        return memo[N]

    if N in all_values:
        return 1
    elif N < 6:
        return N
    else:
        min_number = min(
            [get_min_number(memo, all_values, N - v) + 1 for v in all_values if N - v > 0]
        )
        memo[N] = min_number
        return min_number


def solve(N):
    
    all_values = [1] + get_all_values(N, 6) + get_all_values(N, 9)
    sorted_all_values = list(reversed(sorted(all_values)))

    
    memo = {}
    ans = get_min_number(memo, sorted_all_values, N)

    return ans


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

    
    ans = solve(N)

    
    print(ans)


if __name__ == "__main__":
    main()

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

res=[]

for i in range(1,y+1):
	cnt=0
	y1=i
	y2=y-i

	for j in range(6,0,-1):
		t9=9**j
		if y1>=t9:
			cnt+=y1//t9
			y1=y1%t9
	y2+=y1

	for j in range(7,0,-1):
		t6=6**j
		if y2>=t6:
			cnt+=y2//t6
			y2=y2%t6

	cnt+=y2
	res.append(cnt)

print(min(res))

Solution (Python):
import bisect as bi
N = int(input())
li6 = [6 ** i for i in range(7)]
li9 = [9 ** j for j in range(6)]

def s69(n):
  if n < 6:
    return n
  else:
    s6 = li6[bi.bisect(li6, n)-1]
    s9 = li9[bi.bisect(li9, n)-1]
    return min(n // s6 + s69(n % s6), 1 + s69(n-s9))
print (s69(N))

Solution (Python):
N = int(input())
ans = N
for n9 in range(N//9+1):
    a = N - 9*n9
    if a < 0:
        continue
    c = 0
    while a >= 6:
        c += a % 6
        a = a // 6
    c2 = 0
    while n9 >= 9:
        c2 += n9 % 9
        n9 = n9 // 9
    cost = a + c + c2 + n9
    ans = min(ans, cost)
print(ans)

Solution (Python):
import math
from collections import deque

n = int(input())

log_six = math.floor(math.log(n, 6))
log_nine = math.floor(math.log(n, 6))

count = [-1]*(n*100)
count[0] = 0
todo = deque([0])

while todo:
    i = todo.popleft()

    for j in range(1, log_six+1):
        money = i + 6 ** j

        if money <= n and count[money] is -1:
            count[money] = count[i] + 1
            todo.append(money)

    for k in range(1, log_nine+1):
        money = i + 9 ** k

        if money <= n and count[money] is -1:
            count[money] = count[i] + 1
            todo.append(money)

    if count[i+1] is -1:
        count[i+1] = count[i] + 1
        todo.append(i+1)

    if count[n] != -1:
        break

print(count[n])

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

A = []

for i in range(1, 10):
    A.append(6 ** i)
    A.append(9 ** i)
    A.append(1)

B = [x for x in A if x < 1000000 ]


dp = [0] * (N + 1)
for i in range(N+1):
    if i == 0:
        dp[0] = 0
    else:
        tmp = 10 ** 10
        for j in B:
            if i >= j :
                tmp = min(tmp, dp[i-j]+1)
        dp[i] = tmp

print(dp[-1])

Solution (Python):
n = int(input())
dp = [i for i in range(n+1)]

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

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

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

    dp = [float('inf')] * (N + 10)
    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])

main()

Solution (Python):
n = int(input())
dp = list(range(100010))
for i in range(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())
ans=n
for i in range(n+1):
    cnt=0
    t=i
    while t>0:
        cnt+=t%6
        t//=6
    t=n-i
    while t>0:
        cnt+=t%9
        t//=9
    ans=min(ans,cnt)
print(ans)

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

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

cnt = list(range(n+1))
options = [1]


p = 1
while 9**p <= n:
    options.append(9**p)
    p += 1
p = 1
while 6**p <= n:
    options.append(6**p)
    p += 1

options = sorted(options)
for i in range(n+1):
    for j in options:
        if i>=j:
            """If (i-j) yen could be withdrawn at less than (i-j) times,
            i yen will be done by additional j yen-withdrawal.
            """
            cnt[i] = min(cnt[i], cnt[i-j]+1)

print(cnt[n])

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




li = []
for i in range(1, 6):
  li.append(9**i)
  li.append(6**i)
li.append(6**6)
li.append(1)
li.sort()


DP = list(range(n + 1))

for l in li:
    for j in range(l, n + 1):
        DP[j] = min(DP[j - l] + 1, DP[j])
print(DP[-1])

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




li = []
for i in range(1, 6):
  li.append(9**i)
  li.append(6**i)
li.append(6**6)
li.append(1)
li.sort()


DP = list(range(n + 1))

for l in li:
    for j in range(l, n + 1):
        DP[j] = min(DP[j - l] + 1, DP[j])
print(DP[-1])

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

dp = [float("INF")] * (max+1)
dp[0] = 0
for i in range(1,max+1):
  power = 1
  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())

a = n // 9 + 1

ans = 10**10
tmp = 0

for i in range(a):
    six = (n - 9 * i) // 6
    one = (n-9*i-6*six)
    si = six
    nine = i
    tmp = 0
    while nine > 0:
        tmp += nine % 9
        nine = nine // 9
    while six > 0:
        tmp += six % 6
        six = six // 6
    ans = min(ans,tmp+one)

print(ans)

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

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

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

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

dp = [float("INF")] * (max+1)
dp[0] = 0
for i in range(1,max+1):
  power = 1
  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):
from math import floor
N = int(input())

cnt = N 
for i in range(N+1):
    tmp_cnt = 0
    s = 1
    while i >= s:
        tmp_cnt += (i // s) % 6
        s *= 6
    j = N-i
    k = 1
    while j >= k:
        tmp_cnt += (j // k) % 9
        k *= 9
    
    if tmp_cnt < cnt:

        cnt = tmp_cnt
        
print(cnt)

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

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

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

for n in range(1, 100001):
    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 bisect as bi

li6 = [6 ** i for i in range(7)]
li9 = [9 ** i for i in range(6)]

def s69(n):
  if n < 6:
    return n
  else:
    s6 = li6[bi.bisect(li6, n)-1]
    s9 = li9[bi.bisect(li9, n)-1]
    return min(n // s6 + s69(n % s6), 1 + s69(n-s9))
  
print (s69(int(input())))

Solution (Python):
import bisect as bi

li6 = [6 ** i for i in range(7)]
li9 = [9 ** i for i in range(6)]

def s69(n):
  if n < 6:
    return n
  else:
    s6 = li6[bi.bisect(li6, n)-1]
    s9 = li9[bi.bisect(li9, n)-1]
    return min(n // s6 + s69(n % s6), 1 + s69(n-s9), n // s9 + s69(n % s9))
  
print (s69(int(input())))

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

Solution (Python):

n = int(input())
ans = 100000
for i6 in range(16668):
    count = 0
    n1 = n-i6*6
    if n1>=0:
        j = 0
        while j<=5:
            count = count + (i6%(6**(j+1)))//(6**j)
            i6 -= i6%(6**(j+1))
            j += 1
        j = 0
        i9 = n1//9
        count += n1%9
        while j<=5:
            count += (i9%(9**(j+1)))//(9**j)
            i9 -= i9%(9**(j+1))
            j += 1
        ans = min(ans,count)
print(ans)

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

dp = [float('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):
n = int(input())

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

Solution (Python):

import collections
import itertools

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


n = getint()

array6 = [6]
while array6[-1] < n:
    array6.append(6 * array6[-1])

array9 = [9]
while array9[-1] < n:
    array9.append(9 * array9[-1])

cache = [-1] * (n + 1)
def solve(rest):
    res = cache[rest]
    if res >= 0:
        return res
    res = rest

    for m6 in reversed(array6):
        if m6 <= rest:
            res = min(res, solve(rest - m6) + 1)
            break
    for m9 in reversed(array9):
        if m9 <= rest:
            res = min(res, solve(rest - m9) + 1)
            break
    cache[rest] = res
    return res

print(solve(n))

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

print(dp[N])

Solution (Python):
n=int(input())
k=[1,6,6**2,6**3,6**4,6**5,6**6,9,9**2,9**3,9**4,9**5]
dp=[n]*(n+1)
dp[0]=0

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

print(dp[n])

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

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

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

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

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

print(dp[0])

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

ans = N
for i in range(N+1):
  count = 0
  t=i
  while t>0:
    count+=t%6
    t=math.floor(t/6)

  t = N-i

  while t>0:
    count += t%9
    t=math.floor(t/9)

  if ans>count:
    ans = count

print(ans)

Solution (Python):
n=int(input())
a=[1, 6, 36, 216, 1296, 7776, 46656]
b=[1, 9, 81, 729, 6561, 59049]
def ab_cal(num,arr):
  i=len(arr)-1
  cnt1=0
  while num>0:
    if arr[i]<=num:
      num-=arr[i]
      cnt1+=1
    else:
      i-=1
  return cnt1

ans = 10**9
for i in range(0,n+1):
  cnt=ab_cal(i,a)+ab_cal(n-i,b)
  ans=min(ans,cnt)
print(ans)

Solution (Python):
n = int(input())
dp = [0]
for i in range(1,n+1):
  can = []
  cnt9 = 1
  cnt6 = 1
  while i >= 9 ** cnt9:
    here = i - 9 ** cnt9
    can.append(dp[here] + 1)
    cnt9 += 1
  while i >= 6 ** cnt6:
    here = i - 6 ** cnt6
    can.append(dp[here] + 1)
    cnt6 += 1
  can.append(dp[i-1] + 1)
  dp.append(min(can))
print(dp[-1])

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

Solution (Python):
n = int(input())
x = [1]
i = 6
while i < 100000:
    x.append(i)
    i *= 6
i = 9
while i < 100000:
    x.append(i)
    i *= 9

dp = [0] * 100001
for i in range(1, 100001):
    tmp = []
    for xx in x:
        if i - xx >= 0:
            tmp.append(dp[i-xx]+1)
    dp[i] = min(tmp)
print(dp[n])

Solution (Python):
import itertools, operator, functools, sys

sys.setrecursionlimit(10 ** 9 + 7)

n = int(input())

amounts = [1]
amounts.extend(itertools.takewhile(lambda x: x <= n, itertools.accumulate(itertools.repeat(6), func=operator.mul)))
amounts.extend(itertools.takewhile(lambda x: x <= n, itertools.accumulate(itertools.repeat(9), func=operator.mul)))
amounts.sort(reverse=True)

@functools.lru_cache(maxsize=None)
def f(x):
    if x == 0:
        return 0
    
    count = float('inf')
    for amount in amounts:
        if x - amount >= 0:
            count = min(count, f(x - amount) + 1)
    return count

print(f(n))

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

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

Solution (Python):
import math

n = int(input())
ans = n
for i in range(n+1):
    cc = 0
    t = i
    while (t > 0):
        cc += t % 6
        t = math.floor(t/6)
    t = n - i
    while (t > 0):
        cc += t % 9
        t = math.floor(t/9)
    ans = min(ans, cc)
print(ans)

Solution (Python):


def powers_of_x(x: int, N: int) -> set:
    
    from itertools import count, takewhile

    if x == 1:
        return set()
    ret = set(x ** p for p in takewhile(lambda p: x ** p <= N, count(1)))
    return ret


def main():
    n = int(input())
    dp = [i for i in range(n + 1)]  
    cand = powers_of_x(6, n) | powers_of_x(9, n)
    for i in range(n + 1):
        for j in cand:
            if i - j >= 0:
                dp[i] = min(dp[i], dp[i - j] + 1)
    print(dp[-1])


if __name__ == "__main__":
    main()

Solution (Python):
import sys

sys.setrecursionlimit(300000)

N = int(input())

memo = [None for _ in range(N + 1)]


def f(n):
    if n == 0:
        return 0
    if memo[n] is not None:
        return memo[n]
    ans = n
    pow = 1
    while pow <= n:
        ans = min(ans, f(n - pow) + 1)
        pow *= 6
    pow = 1
    while pow <= n:
        ans = min(ans, f(n - pow) + 1)
        pow *= 9
    memo[n] = ans
    return ans


print(f(N))

Solution (Python):
import sys

input = sys.stdin.readline

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

yen = [6 ** i for i in range(1, 8) if 6 ** i <= n]
yen += [9 ** i for i in range(1, 7) if 9 ** i <= n]

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

print(dp[-1])

Solution (Python):


def main():
    n = int(input())
    dp = [i for i in range(n + 1)]  
    cand = [6 ** i for i in range(1, 7) if 6 ** i <= n]
    cand += [9 ** i for i in range(1, 6) if 9 ** i <= n]
    for i in range(n + 1):
        for j in cand:
            if i - j >= 0:
                dp[i] = min(dp[i], dp[i - j] + 1)
    print(dp[-1])


if __name__ == "__main__":
    main()

Solution (Python):


def main():
    n = int(input())
    dp = [i for i in range(n + 1)]  
    cand = [6 ** i for i in range(1, 7) if 6 ** i <= n]
    cand += [9 ** i for i in range(1, 6) if 9 ** i <= n]
    for i in range(n + 1):
        for j in cand:
            if j > n:
                break
            if i - j >= 0:
                dp[i] = min(dp[i], dp[i - j] + 1)
    print(dp[-1])


if __name__ == "__main__":
    main()

Solution (Python):


def main():
    n = int(input())
    dp = [i for i in range(n + 1)]  
    cand = []  
    for i in (6, 9):
        p = 1
        while i ** p <= n:
            cand += [i ** p]
            p += 1
    for i in range(n + 1):
        for j in cand:
            if j > n:
                break
            if i - j >= 0:
                dp[i] = min(dp[i], dp[i - j] + 1)
    print(dp[-1])


if __name__ == "__main__":
    main()

Solution (Python):


def main():
    n = int(input())
    
    dp = [i for i in range(n + 1)]
    cand = (6, 9, 36, 81, 216, 729, 1296, 6561, 7776, 46656, 59049)
    for j in cand:
        for i in range(n + 1):
            if j > n:
                break
            if i - j >= 0:
                dp[i] = min(dp[i], dp[i - j] + 1)
    print(dp[-1])


if __name__ == "__main__":
    main()

Solution (Python):

def main():
    n = int(input())
    
    dp = [i for i in range(n + 1)]
    cand = (6, 9, 36, 81, 216, 729, 1296, 6561, 7776, 46656, 59049)
    for i in range(n + 1):
        for j in cand:
            if j > n:
                break
            if i - j >= 0:
                dp[i] = min(dp[i], dp[i - j] + 1)
    print(dp[-1])


if __name__ == "__main__":
    main()

Solution (Python):

import sys, math, fractions, itertools


def solve(N: int):
    mn = N
    for i in range(N+1):
        s = i
        n = N - i
        sc = 0
        nc = 0
        while(s > 0):
            sc += s % 6
            s //= 6
        while(n > 0):
            nc += n % 9
            n //= 9
        if sc + nc < mn:
            mn = sc + nc
    print(mn)
    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):
n = int(input())
dp = [10**9]*30000000
dp[0] = 0
pow6 = [6**i for i in range(10) if 6**i <= n]
pow9 = [9**i for i in range(10) if 9**i <= n]

for i in range(n):
    for p6 in pow6:
        dp[i+p6] = min(dp[i+p6], dp[i]+1)
    for p9 in pow9:
        dp[i+p9] = min(dp[i+p9], dp[i]+1)
print(dp[n])

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

Solution (Python):
n=int(input())
l=sorted([6**i for i in range(1,7)]+[9**i for i in range(6)])
dp=[float('inf')]*(n+1)
dp[0]=0
for i in range(1,n+1):
    for j in range(12):
        if i-l[j]>=0:dp[i]=min(dp[i],dp[i-l[j]]+1)
print(dp[-1])

Solution (Python):
N = int(input())
l = [0,1,2,3,4,5,1,2,3,1] + [0] * N
j = k = 1
for i in range(10,N+1):
    if i >= 6**(j+1):j+=1
    if i >= 9**(k+1):k+=1
    al = []
    m = i//9**(k)
    for v in range(1,m+1):
        n = i - v*(9**k)
        al.append(v+l[n])
    o = i//6**(j)
    for u in range(1,o+1):
        p = i - u*(6**j)
        al.append(u+l[p])
    l[i] = min(al)
print(l[N])

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

dp = [float('inf')] * (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[-1])

Solution (Python):
n = int(input())
li = [1,6,6**2,6**3,6**4,6**5,6**6,9,9**2,9**3,9**4,9**5]
dp = [100000]*100001
dp[0] = 0
for i in range(100001):
  for s in li:
    if i+s <= 100000:
      dp[i+s] = min(dp[i]+1,dp[i+s])
print(dp[n])

Solution (Python):
N = int(input())
dp = [0] * 100050
money = set()
i = 0
while(6**i < 10**5):
    money.add(6**i)
    i += 1
i = 0
while(9**i < 10**5):
    money.add(9**i)
    i += 1
mm = []
for i in range(1, 10**5+1):
    if i in money:
        mm.append(i)
    dp[i] = min([dp[i-k] for k in mm]) + 1

print(dp[N])

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

for i in range(n//6+1):
    cnt = 0
    k = i
    while k != 0:
        cnt += k % 6
        k = k // 6
    j = (n-i*6) // 9
    k = j
    while k != 0:
        cnt += k % 9
        k = k // 9
    ans = min(ans, cnt+(n-i*6-j*9))

print(ans)