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


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

ANS=1000000







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


                                            




print(ANS)

Solution (Python):
import bisect
max = 100000
m6 = [1]
m9 = [1]
i = 6
while i<max:
    m6.append(i)
    i*=6
i = 9
while i<max:
    m9.append(i)
    i*=9

def res(n):
    if n < 6:
        return n
    else:
        i6 = bisect.bisect(m6,n)-1
        i9 = bisect.bisect(m9,n)-1
        r = 1+min(res(n-m6[i6]),res(n-m9[i9]))
        return r
N = int(input())
print(res(N))

Solution (Python):
from itertools import count

n = int(input())

dp = [0]*(n+1)

def it(n):
  yield 1
  m = 6
  while m <= n:
    yield m
    m *= 6
  m = 9
  while m <= n:
    yield m
    m *= 9

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

print(dp[n])

Solution (Python):
N = int(input())
l = [1, 6, 9, 36, 81, 216, 729, 1296, 6561, 7776, 46656, 59049]
dp = [float('inf')] * (N + 1)
dp[0] = 0

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

Solution (Python):
def solve_coin_change(coins, value):
    table = [None for x in range(value + 1)]
    table[0] = []
    for i in range(1, value + 1):
        for coin in coins:
            if coin > i: 
                continue
            elif not table[i] or len(table[i - coin]) + 1 < len(table[i]):
                if table[i - coin] != None:
                    table[i] = table[i - coin][:]
                    table[i].append(coin)

    if table[-1] != None:
        return len(table[-1])
    else:
        return -1      


coins1 = [1]
coins6 = [6]
coins9 = [9]

maximum = 100000
i = 1
while True:
    new = coins6[i-1] * coins6[0]
    if new <= maximum:
        coins6.append(new)
        i += 1
    else:
        break
i = 1
while True:
    new = coins9[i-1] * coins9[0]
    if new <= maximum:
        coins9.append(new)
        i += 1
    else:
        break

n = int(input())
print(solve_coin_change(coins1 + coins6 + coins9, n))

Solution (Python):
from heapq import *

N = int(input())

result = 100000

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

h = []

xs = {}

heappush(h, (0, 0))

while 1:
    r, m = heappop(h)
    if m == N:
        result = r
        break
    for n in ns:
        s = r + 1
        x = m + n
        if x <= N and not x in xs:
            xs[x] = s
            heappush(h, (s, x))

print(result)

Solution (Python):



def solve():
    n = int(input())
    li = [1]
    li.extend([6 ** i for i in range(1, 15) if 6 ** i <= n])
    li.extend([9 ** i for i in range(1, 15) if 9 ** i <= n])
    li.sort(reverse=True)

    cnt = 0
    s = set([n])
    bf = False
    while not bf:
        ts = set(s)
        for e in li:
            for c in s:
                if c - e == 0:
                    bf = True
                    break
                if c - e > 0:
                    ts.add(c - e)
            if bf:
                break
        if not bf:
            s = ts
        cnt += 1
    print(cnt)


if __name__=="__main__":
    solve()

Solution (Python):
def main():
    n = int(input())
    dp = [float('inf')]*(n+1)
    dp[0] = 0

    ls = [1, 6, 9]
    ks = [1]

    for l in ls[1:]:
        i = 1
        while True:
            if l ** i <= n:
                ks.append(l**i)
            else:
                break
            i += 1

    for k in ks:
        for i in range(len(dp)):
            if i+k >= len(dp):
                break
            if dp[i]+1 < dp[i+k]:
                dp[i+k] = dp[i]+1
    print(dp[n])

main()

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

ans = 100000

d = []

for a in range(1,7):d.append( 6**a )
for a in range(1,6):d.append( 9**a )
d.append(1)
d.sort()


dp = [1000000000] * 100001
dp[0] = 0
for x in range(0,n+1):
  for y in d:
    if x-y >= 0:
      dp[x] = min( dp[x-y] + 1, dp[x] )

print dp[n]

Solution (Python):
from collections import defaultdict as dd
from collections import Counter
from pprint import pprint as pp

YN = {True: 'Yes', False: 'No'}
ri = lambda: int(input())
ria = lambda: list(map(int, input().split()))
rian = lambda n: [ria() for _ in range(n)]
rs = lambda: input()
rsa = lambda: input().split()
rsn = lambda n: [rs() for _ in range(n)]

N = ri()

l = []
for i in range(1,6):
  l.append(9**i)
for i in range(7):
  l.append(6**i)
l.sort(reverse=True)

cache = {n:1 for n in l}
def f(n):
  if n in cache:
    return cache[n]
  ret = 100000
  for i in l:
    if i <= n:
      ret = min(ret, f(n-i)+1)
  cache[n] = ret
  return ret
print(f(N))

Solution (Python):
N=int(input())
ar=[9**i for i in range(1,6)]
for i in range(1,7):ar.append(6**i)
ar.append(1)
ar.sort()
inf=10**5
DP=[inf for _ in range(N+1)]
DP[0]=0
for i in range(len(ar)):
    for j in range(ar[i],N+1):
        DP[j]=min(DP[j],DP[j-ar[i]]+1)
print(DP[N])

Solution (Python):
N = int(input())
enable = [1] + [6**i for i in range(1, 7)] + [9**i for i in range(1, 6)]
dp = [-1 for i in range(N+1)]
for i in enable:
    if i <= N:
        dp[i] = 1

def find_min(x):
    min_res = float('INF')
    for i in enable:
        if x - i >= 0:
            min_res = min(min_res, dp[x-i])
    return min_res

for i in range(1, N + 1):
    if dp[i] == -1:
        dp[i] = find_min(i) + 1

print(dp[N])

Solution (Python):
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

Solution (Python):
INF = 100000
dp = [INF]*100002
count = 0

index = [[0, 0]]
while index:
    x, count  = index[0]
    count += 1
    index.pop(0)
    dp[x+1] = count
    i = 1
    while x + 6**i < INF:
        if dp[x+6**i] > count:
            dp[x+6**i] = count
            index.append([x+6**i, count])
        i += 1
    i = 1
    while x + 9**i < INF:
        if dp[x+9**i] > count:
            dp[x+9**i] = count
            index.append([x+9**i, count])
        i += 1

n = int(input())
for i in range(n, 0, -1):
    if dp[i] < INF:
        print(dp[i]+n-i)
        break

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

dp = [0]*(N+100001)
for i in range(99999):
    dp[i] = 10**10

for i in range(100000,N+100001):
    dp[i] = min(dp[i-1] + 1,
                dp[i-6] + 1,
                dp[i-9] + 1,
                dp[i-36] +1,
                dp[i-81] + 1,
                dp[i-216] + 1,
                dp[i-729] + 1,
                dp[i-1296] + 1,
                dp[i-6561] + 1,
                dp[i-7776] + 1,
                dp[i-46656] + 1,
                dp[i-59049] + 1)

print(dp[N+99999])

Solution (Python):
from sys import stdin, stdout


n = int(stdin.readline())
step = [1]

cur = 6
while cur <= n:
    step.append(cur)
    cur *= 6

cur = 9
while cur <= n:
    step.append(cur)
    cur *= 9
    
dp = [float('inf') for i in range(n + 1)]
dp[0] = 0

for i in range(n):
    if dp[i] == float('inf'):
        continue
    
    for v in step:
        if v + i <= n:
            dp[i + v] = min(dp[i + v], dp[i] + 1)
    
stdout.write(str(dp[n]))

Solution (Python):
n = int(input())
a = list()
a.append(1)
a.append(6)
a.append(6*6)
a.append(6*6*6)
a.append(6*6*6*6)
a.append(6*6*6*6*6)
a.append(6*6*6*6*6*6)
a.append(9)
a.append(9*9)
a.append(9*9*9)
a.append(9*9*9*9)
a.append(9*9*9*9*9)
a.sort()
T = [0]+[float('inf')]*n
for i in range(len(a)):
    for j in range(a[i], n+1):
        T[j] = min(T[j], T[j-a[i]]+1)
print(T[-1])

Solution (Python):
ans = [0] * 100001
ans[0] = 0

n = int(input())

for i in range(1,n+1):
    cand1 = ans[i-1]
    cand2 = 100001
    cand3 = 100001
    x = 6
    while (x<=i):
        cand2 = ans[i-x]
        x=6*x
    y = 9
    while (y<=i):
        cand3 = ans[i-y]
        y=9*y
    ans[i] = min(cand1,cand2,cand3) + 1

print(ans[n])

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

Solution (Python):
from sys import stdin

n = int(stdin.readline().strip())

dp = [0 for i in range(100010)]
dp[0] = 0
dp[1] = 1

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

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

print(dp[n])

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

amts = [1]
tmp = 6
while tmp <= n:
  amts.append(tmp)
  tmp *= 6
  
tmp = 9
while tmp <= n:
  amts.append(tmp)
  tmp *= 9


kaisus = [1e5] * (n+1)
kaisus[0] = 0
for i in range(1, n+1):
  for amt in amts:
    temp = i - amt
    if temp >= 0:
      kaisus[i] = min(kaisus[i], kaisus[temp] + 1)
      
print(kaisus[n])

Solution (Python):
N = int(input())
mi = 100000
for q in range(11120):
    a = 0
    n = q*9
    pn = N-n
    if(n>N) : break;
    for i in range(6,0,-1):
        if(n >= 9**i) :
            a += n//(9**i)
            n%=(9**i)
    for i in range(8,0,-1):
        if(pn >= 6**i) :
            a += pn//(6**i)
            pn%=(6**i)
    a += pn;
    mi = min(mi,a)
print(mi)

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

Solution (Python):

N = int(input())

DP = list(range(N+1))
L = []

i = 1
while True:
    if 6**i > N:
        break
    L.append(6**i)
    i += 1

i = 1
while True:
    if 9**i > N:
        break
    L.append(9**i)
    i += 1
    
for l in sorted(L):
    for j in range(l, N+1):
        DP[j] = min(DP[j-l]+1, DP[j])
print(DP[-1])

Solution (Python):
MAX_N = 10 ** 5
dp = list(range(MAX_N+1))
for t in (6,9):
    v = t
    while v < MAX_N:
        for i in range(MAX_N + 1):
            if i + v < len(dp):
                dp[i+v] = min(dp[i+v], dp[i] + 1)
        v *= t
print(dp[int(input())])

Solution (Python):
N = input()
T = [N]*(N+1)
T[0] = 0
for i in range(1,N+1):
  for j in xrange(20):
    if i-9**j<0:
      break
    T[i] = min(T[i], T[i-9**j]+1)
  for j in xrange(20):
    if i-6**j<0:
      break
    T[i] = min(T[i], T[i-6**j]+1)
print T[N]

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

print(min(dp[i] + N-i for i in range(N+1)))

Solution (Python):
def sinsu(M,k):
    L=0
    MM=M
    while(True):
        L+=MM%k
        MM=MM//k
        if MM==0:
            break
    return L
N=int(input())
ans=N
for i in range(N+1):
    a=i
    b=N-i
    tmp=sinsu(a,6)+sinsu(b,9)
    if ans>tmp:
        ans=tmp
print(ans)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    c = set([n])
    for k in range(100):
        d = set()
        for t in c:
            ci = -1
            for i in range(100):
                if 6**i > t:
                    ci = i-1
                    break
            d.add(t-6**ci)
            ci = -1
            for i in range(100):
                if 9**i > t:
                    ci = i-1
                    break

            d.add(t-9**ci)
        c = d
        if 0 in d:
            return k+1

    return -1


print(main())

Solution (Python):



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


N=int(input())

ans = 100000
for i in range(N+1):
    ans = min(ans, sum_digits(i,6)+sum_digits(N-i,9))

print(ans)

Solution (Python):
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

n = ni()

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