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):
import math
n = (int)(input())

ans = n
l = (int)(math.log(n, 9)+1)

for i in range(n+1):
  tmp_ans = 0
  a_six = i
  a_nine = n-i
  for i in reversed(range(7)):
    tmp = a_six//6**i
    tmp_ans += tmp
    a_six -= tmp*6**i
  a_nine += a_six
  for i in reversed(range(7)):
    tmp = a_nine//9**i
    tmp_ans += tmp
    a_nine -= tmp*9**i
  if ans > tmp_ans:
    ans = tmp_ans

print(ans)

Solution (Python):



def func():
    N = int(input())
    step = [0 for i in range(N+1)]

    for i in range(1, N+1):
        minimum = step[i-1]+1
        p = 0
        r = 0
        while i >= 9 ** (p+1):
            p += 1
            minimum = min(minimum, 1+step[i-9**p])
        while i >= 6 ** (r+1):
            r += 1
            minimum = min(minimum, 1+step[i-6**r])
        step[i] = minimum

    print(step[N])

if __name__ == "__main__":
 
    func()

Solution (Python):
from bisect import bisect_right
import sys
from functools import lru_cache

sys.setrecursionlimit(10**8)

N = int(input())






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



@lru_cache(maxsize=None)
def dfs(n):
	r = bisect_right(l, n)
	if r <= 0:
		return n
	min_num = 10**9
	for i in range(r):
		min_num = min(min_num, dfs(n-l[i])+1)
	return min_num

print(dfs(N))

Solution (Python):
n = int(input())
six_list = [1,6,36,216,1296,7776,46656]
nine_list = [1,9,81,729,6561,59049]
six_list.reverse()
nine_list.reverse()
rest = n
ans = n




for a in range(n+1):
        
        six_rest = a 
        nine_rest = n-a
        count_6 = 0
        count_9 = 0
        for number in six_list:
                if six_rest//number >= 1:
                        count_6 += six_rest//number
                        six_rest -= six_rest//number * number
        for number in nine_list:
                if nine_rest//number >= 1:
                        count_9 += nine_rest//number
                        nine_rest -= nine_rest//number * number
        if ans > count_6 + count_9:
                ans = count_6 + count_9

print(ans)

Solution (Python):
N = int(input())
ans = N
for i in range(N // 9 + 1):
  cnti = 0
  _i = i
  while _i :
    cnti += _i % 9
    _i //= 9
  cntj = 0
  j = (N - 9 * i) // 6
  _j = j
  while _j:
    cntj += _j % 6
    _j //= 6
  ans = min(cnti + cntj + N - 9 * i - 6 * j, ans)
print(ans)

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

A = []

tmp = 6

while tmp<=N:
    A.append(tmp)
    tmp = tmp*6
    

tmp = 9

while tmp<=N:
    A.append(tmp)
    tmp = tmp*9
    
A.sort()
    
dp = [[0 for i in range(N+1)] for j in range(len(A)+1)]

for i in range(N+1):
    dp[0][i] = i
    
for i in range(len(A)):
    for j in range(N+1):
        if A[i]<=j:
            dp[i+1][j] = min(dp[i+1][j-A[i]]+1, dp[i][j])
        else:
            dp[i+1][j] = dp[i][j]
            
print(dp[len(A)][N])

Solution (Python):

N = int(input())

memo = [None] * (N + 1)

def cut(val, pow6, pow9):
    
    rets = [100000] * 2
    if memo[val] != None: return memo[val]
    
    p6_tmp = pow6
    for x in list(range(pow6))[::-1]:
        if val < (6 ** (x + 1)): p6_tmp -= 1
        else:
            rets[0] = cut(val - (6 ** (x + 1)), p6_tmp, pow9) + 1
            break
    else: rets[0] = val
    
    p9_tmp = pow9
    for x in list(range(pow9))[::-1]:
        if val < (9 ** (x + 1)): p9_tmp -= 1
        else:
            rets[1] = cut(val - (9 ** (x + 1)), pow6, p9_tmp) + 1
            break
    else: rets[1] = val
    
    ret = min(rets)
    if memo[val] == None: memo[val] = ret
    return ret

print(cut(N, 32, 32))

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

Solution (Python):
n = int(input())
res = float('inf')
for a in range(n+1):
    
    rest = n - a
    cnt = 0
    for i in range(6,-1,-1):
        if a // (6**i) != 0:
            cnt += a // (6**i)
            a %= 6 ** i
    for i in range(5,-1,-1):
        if rest // (9**i) != 0:
            cnt += rest // (9**i)
            rest %= 9 ** i
    res = min(res, cnt)
print(res)

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

reslis = []
for i in range(N + 1):
    count = 0
    temp = i
    while True:
        count += temp % 9
        if temp//9 == 0:
            break
        else:
            temp = temp//9
    temp = N - i
    while True:
        count += temp % 6
        if temp//6 == 0:
            break
        else:
            temp = temp//6
    reslis.append(count)


reslis.sort()
print(reslis[0])

Solution (Python):
N = int(input())
table = [1e100 for i in range(100000 + 10)]
table[0] = 0

for i in range(1, 8):
    if 6 ** i <= 100000 + 10:
        table[6 ** i] = 1

    if 9 ** i <= 100000 + 10:
        table[9 ** i] = 1

for i in range(1, 100000 + 10):
    table[i] = table[i - 1] + 1
    for j in range(1, 8):
        if i - 6 ** j >= 0:
            table[i] = min(table[i], table[i - 6 ** j] + 1)
        if i - 9 ** j >= 0:
            table[i] = min(table[i], table[i - 9 ** j] + 1)

print(table[N])

Solution (Python):
import math

N = int(input())



C = [1]
for i in range(math.floor(math.log(N,9)) + 2):
    if i !=0 :
        C.append(9 ** i)
for i in range(math.floor(math.log(N,6)) + 2):
    if i != 0:
        C.append(6 ** i)


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

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

print(dp[N])

Solution (Python):
import math

N = int(input())



C = [1]
for i in range(math.ceil(math.log(N,9)) + 3):
    if i !=0 :
        C.append(9 ** i)
for i in range(math.ceil(math.log(N,6)) + 3):
    if i != 0:
        C.append(6 ** i)


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

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

print(dp[N])

Solution (Python):
from math import log
n = int(input())
a = 10**5

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

Solution (Python):
N = int(input())
nine = [9**5, 9**4, 9**3, 9**2, 9, 1]
six = [6**6, 6**5, 6**4, 6**3, 6**2, 6, 1]
counter = 100000

for i in range(N+1):
    j = N-i
    countN = 0
    for k in nine:
        if not i:
            break
        countN += i // k
        i = i % k

    countS = 0
    for k in six:
        if not j:
            break
        countS += j // k
        j = j % k

    counter = min(counter, countN+countS)

print(counter)

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

Solution (Python):
n = int(input())
paySix = []
payNine = []
i = 0
while 6**i <= n:
   paySix.append(6**i)
   i += 1
i = 0
while 9**i <= n:
   payNine.append(9**i)
   i += 1

maxCount = n
sum = 0
for j in range(n+1):
    count = 0
    count6 = 0
    count9 = 0
    nine = j
    six = n - j
    for i in reversed(range(len(payNine))):
        count9 += int(nine/payNine[i])
        nine -= int(nine/payNine[i])*payNine[i]
    
    for i in reversed(range(len(paySix))):
        count6 += int(six/paySix[i])
        six -= int(six/paySix[i])*paySix[i]
    
    maxCount = min(maxCount, count9+count6)
print(maxCount)
"""
pay = [1]
i = 1
while 6**i <= n:
   pay.append(6**i)
   i += 1
i = 1
while 9**i <= n:
   pay.append(9**i)
print(i)
pay = sorted(pay)
print(len(pay))
count = 0
for i in reversed(range(len(pay))):
    
    count += int(n/pay[i])
    n -= int(n/pay[i])*pay[i]
    if n == 0:
        print(count)
"""
""""
for i in range(1, 100000):
    if 9 ** i < n:
        nine.append(9 ** i)
    else:
        break
for i in range(1, 100000):
    if 6 ** i < n:
        six.append(6 ** i)
    else:
        break

count = 0
last = n
while last >= 9:
    if nine:
        while nine[-1] > last:
            nine.pop()
    if six:
        while six[-1] > last:
            six.pop()

    if nine:
        tmp9 = nine[-1]
        num9 = int(last / tmp9)
    if six:
        tmp6 = six[-1]
        num6 = int(last / tmp6)

    if num9 < num6:
        count += num9
        last %= tmp9
        nine.pop()
    elif num9 == num6 and last % tmp9 <= last % tmp6:
        count += num9
        last %= tmp9
        nine.pop()
    else:
        count += num6
        last %= tmp6
        six.pop()


count += int(last / 6)
last %= 6
print(count + last)
"""

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

def base_n(x, n):
    results = 0
    while x > 0:
        results += x % n
        x //= n
    return results

print(min([base_n(i, 6) + base_n(N - i, 9) for i in range(N + 1)]))

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

base = [1]
for i in range(1, 7):
    if 6 ** i <= N:
        base.append(6 ** i)
for i in range(1, 6):
    if 9 ** i <= N:
        base.append(9 ** i)
ans = N
dp = [0] * (N + 1)
for i in range(1, N + 1):
    dp[i] = min([dp[i - j] + 1 if i - j >= 0 else j for j in base])

print(dp[N])

Solution (Python):
def calc(x, base):
    res = 0
    while x:
        x, m = divmod(x, base)
        res += m
    return res


def main():
    N = int(input())
    ans = min(calc(i, 6) + calc(N - i, 9) for i in range(N + 1))
    print(ans)


main()

Solution (Python):
def powerset(n, lessequal):
    retval = []
    power = n
    while power <= lessequal:
        retval += [power]
        power *= n
    return retval


def main():
    N = int(input())
    dp = [0] * (N + 1)
    for i in range(1, N + 1):
        withdraw = [1] + powerset(6, i) + powerset(9, i)
        dp[i] = min([dp[i - x] for x in withdraw]) + 1
    print(dp[N])


if __name__ == "__main__":
    main()

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

min_cnt = float('inf')
for i in range(0, n+1, 9):
    cnt = 0
    t = i
    while t >= 9:
        cnt += t % 9
        t //= 9
    cnt += t

    t = (n-i)
    while t >= 1:
        cnt += t % 6
        t //= 6
    cnt += t

    if cnt < min_cnt:
        min_cnt = cnt
print(min_cnt)

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

ans = N
for i in range(N + 1):
    nine, pvt = 0, i
    while pvt > 0:
        nine += pvt % 9
        pvt //= 9

    six, pvt = 0, N - i
    while pvt > 0:
        six += pvt % 6
        pvt //= 6
    
    ans = min(ans, nine + six)
print(ans)

Solution (Python):
N = int(input())
koho = [1]
i=1
while True:
    if i > 1e6:
        break
    i *= 6
    koho.append(i)
i=1
while True:
    if i > 1e6:
        break
    i *= 9
    koho.append(i)

dp = [0] * (N+1)
for i in range(1, N+1):
    tmp = []
    for k in koho:
        if k > i:
            continue
        tmp.append(dp[i - k] + 1)
    dp[i] = min(tmp)
print(dp[N])

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

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

hiki9 = []
hiki6 = []
n = int(log(N) / log(9) + 1)  
for i in range(n+1):
    hiki9.append(9**i)
n = int(log(N) / log(6) + 1)
for i in range(n+1):
    hiki6.append(6**i)
hiki9.sort(reverse=True)
hiki6.sort(reverse=True)
x = []
for i in range(N+1):
    n9 = i
    tmpx = 0
    for h in hiki9:
        while h <= n9:
            n9 -= h
            tmpx += 1
    n6 = N - i
    for h in hiki6:
        while h <= n6:
            n6 -= h
            tmpx += 1
    x.append(tmpx)
x.sort()
print(x[0])

Solution (Python):
N = int(input())
B6 = [6**i for i in range(1,7)]
B9 = [9**i for i in range(1,6)]
L = B6 + B9
L = sorted(list(set(L)))
dp = [int(i) for i in range(N+1)]

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

Solution (Python):

N=int(input())
i=0
t=0
ans=N
for i in range(N+1):
    nine = 0
    six = 0
    t=i
    while (t>0):
        nine+=t%9
        t//=9
    t=N-i
    while (t>0):
        six+=t%6
        t//=6
    if ans>nine+six:
        ans=nine+six
print(ans)

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

INF = float('inf')
dp = [INF for i in range(n+1)]

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

print(dp[n])

Solution (Python):
N = int(input())
B6 = [6**i for i in range(1,8)]
B9 = [9**i for i in range(1,7)]
L = sorted(list(set(B6+B9)))
dp = [i for i in range(N+1)]
for i in L :
    for j in range(i,N+1) :
        dp[j] = min(dp[j], dp[j-i]+1)
print(dp[-1])

Solution (Python):
N = int(input())
B6 = [6**i for i in range(1,8)]
B9 = [9**i for i in range(1,7)]
L = sorted(list(set((B6+B9))))
dp = [i for i in range(N+1)]
for i in L :
    for j in range(i,N+1) :
        dp[j] = min(dp[j], dp[j-i]+1)
print(dp[-1])

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

dp = [i for i in range(N+1)]
B6 = [6**i for i in range(1,8)]
B9 = [9**i for i in range(1,7)]
L = B6 + B9
L = sorted(list(set(L)))

for i in L :
    for j in range(i, N+1) :
        dp[j] = min(dp[j-i]+1, dp[j])
print(dp[-1])

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

sixs = [6, 36, 216, 1296, 7776, 46656]

ans = N
for ptn in itertools.product(range(6), repeat=6):
    money = ope = 0
    for s,p in zip(sixs,ptn):
        money += s*p
        ope += p
    if money > N: continue
    if ope > ans: continue
    rem = N - money
    while rem:
        ope += rem%9
        rem //= 9
    ans = min(ans, ope)
print(ans)

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

sys.setrecursionlimit(10**5)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n = ni()

res = 1
coin = [1]
i = 1
while res < 10**5:
    coin.append(6**i)
    i += 1
    res *= 6
    
res = 1
i = 1
while res < 10**5:
    coin.append(9**i)
    i += 1
    res *= 9
    
coin.sort()
    
dp = [10**5]*(n+1)
dp[0] = 0

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

Solution (Python):

iN = int(input())

a6 = [0]*7
for i in range(7):
    a6[i] = 6 ** i
a6.reverse()
a9 = [0]*6
for i in range(6):
    a9[i] = 9 ** i
a9.reverse()

iAns = iN
for i in range(iN+1):
    iD = iN - i
    iC = 0
    for j in range(7):
        if i:
            iG = a6[j]
            if i >= iG:
                iC += (i // iG)
                i %=iG
    if iAns <= iC:
        continue
    for j in range(6):
        if iD :
            iG = a9[j]
            if iD >= iG:
                iC += (iD // iG)
                iD %= iG
    if iAns > iC:
        iAns = iC
print(iAns)

Solution (Python):

iN = int(input())

a6 = [0]*7
for i in range(7):
    a6[i] = 6 ** i
a6.reverse()
a9 = [0]*6
for i in range(6):
    a9[i] = 9 ** i
a9.reverse()

iAns = iN
for i in range(iN+1):
    iD = iN - i
    iC = 0
    for j in range(7):
        if i:
            iG = a6[j]
            if i >= iG:
                iC += (i // iG)
                i %=iG
    for j in range(6):
        if iD :
            iG = a9[j]
            if iD >= iG:
                iC += (iD // iG)
                iD %= iG
    if iAns > iC:
        iAns = iC
print(iAns)

Solution (Python):

from sys import stdin


d_in = lambda: int(stdin.readline())  


def get_order(n, m):
    order = 0
    while n > 0:
        n = n // m
        order += 1
    return order


def decimal2bit(n, m):
    """
    nのm進数表現
    """
    if n == 0:
        return []
    order = get_order(n, m)
    ans = []
    for i in range(order, -1, -1):
        ans.append(n // (m ** i))
        n -= m ** i * ans[-1]
    return ans


def search(n):
    ans = float('inf')
    for i in range(n // 9 + 1):
        nine = decimal2bit(9 * i, 9)
        six = decimal2bit(n - 9 * i, 6)
        ans = min(ans, sum(nine) + sum(six))
    print(ans)


if __name__ == '__main__':
    N = d_in()
    search(N)

Solution (Python):
N = int(input())
B6 = [6**i for i in range(1,7)]
B9 = [9**i for i in range(1,6)]
L = B6 + B9
L = sorted(list(set(L)))
dp = [i for i in range(N+1)]
for i in L :
    for j in range(i,(N+1)) :
        dp[j] = min(dp[j-i]+1,dp[j])
ans = dp[N]
print(ans)

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

dp = [i for i in range(N+1)]
B6 = [6**i for i in range(1,8)]
B9 = [9**i for i in range(1,7)]
L = B6 + B9
L = sorted(list(set(L)))

for i in L :
    for j in range(i, N+1) :
        dp[j] = min(dp[j-i]+1, dp[j])
print(dp[-1])

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

cands = [1]
for i in range(1, 10):
    if 6**i <= 100000:
        cands.append(6**i)
    if 9**i <= 100000:
        cands.append(9**i)
cands = sorted(cands)

ans = list(range(n+1))
for c in cands[1:]:
    for i in range(n+1):
        if i < c:
            pass
        else:
            ans[i] = min(ans[i], ans[i-c] + 1)
print(ans[-1])

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

c = [i for i in range(n + 1)]

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

Solution (Python):
a = int(input())
ans = [100000]*100010
ans[0] = 0
for n in range(1,100001):
    power = 1
    while power <= n:
        ans[n] = min(ans[n],ans[n-power] + 1)
        power *= 6
    power = 1
    while power <= n:
        ans[n] = min(ans[n],ans[n-power] + 1)
        power *= 9
print(ans[a])

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