Problem:


Score : 300 points

Problem Statement

To make it difficult to withdraw money, a certain bank allows its customers to withdraw only one of the following amounts in one operation:

1 yen (the currency of Japan)

6 yen, 6^2(=36) yen, 6^3(=216) yen, ...

9 yen, 9^2(=81) yen, 9^3(=729) yen, ...

At least how many operations are required to withdraw exactly N yen in total?

It is not allowed to re-deposit the money you withdrew.

Constraints

1 \leq N \leq 100000

N is an integer.

Input

Input is given from Standard Input in the following format:

N

Output

If at least x operations are required to withdraw exactly N yen in total, print x.

Sample Input 1

127

Sample Output 1

4

By withdrawing 1 yen, 9 yen, 36(=6^2) yen and 81(=9^2) yen, we can withdraw 127 yen in four operations.

Sample Input 2

3

Sample Output 2

3

By withdrawing 1 yen three times, we can withdraw 3 yen in three operations.

Sample Input 3

44852

Sample Output 3

16



Sample input:
127


Sample output:
4

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Jun 10 21:28:22 2018

@author: maezawa
"""

n = int(input())

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

dp = [float('inf') for _ in range(n+1)]
dp[0] = 0
#print(n,m)
#print(c)
#print(*dp, sep='\n')

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

print(dp[n])

Submission status: Accepted

Solution code:
N = int(input())
A = [1, 6, 36, 216, 1296, 7776, 46656, 9, 81, 729, 6561, 59049]
L = [0]
for i in range(1, N+1):
    M = []
    for a in A:
        if i - a >= 0:
            M.append(L[i-a]+1)
    L.append(min(M))
print(L[-1])

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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      

# Driver program to test above function
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))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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()
#print d

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]

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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]))

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
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])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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]

Submission status: Accepted

Solution code:
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)))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

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)

Submission status: Runtime Error

Solution code:
n = int(input())
ans, index6, index9, num6, num9 = 0, 0, 0, 0, 0
INF = float('inf')

def a10_to_n(x, n):
    if x//n:
        return a10_to_n(x//n, n)+str(x%n)
    else:
        return str(x)

def index(n, num6, index6, num9, index9):
    val = str(a10_to_n(n, 6))
    for i, j in enumerate(val):
        if int(j) != 0:
            num6 = int(j)
            index6 = len(val)-i-1
            break
    val = str(a10_to_n(n, 9))
    for i, j in enumerate(val):
        if int(j) != 0:
            num9 = int(j)
            index9 = len(val)-i-1
            break
    return num6, index6, num9, index9

num6, index6, num9, index9 = index(n, num6, index6, num9, index9)
while index6 > 1 or index9 > 1:
    if 6**index6 <= 9**index9:
        n -= num9*9**index9
        ans += num9
    else:
        n -= num6*6**index6
        ans += num6
    num6, index6, num9, index9 = index(n, num6, index6, num9, index9)
    
a = [INF for _ in range(n+1)]
a[n] = 0
for i in range(n, -1, -1):
    if i-9 >= 0:
        a[i-9] = min(a[i]+1, a[i-9])
    if i-6 >= 0:
        a[i-6] = min(a[i]+1, a[i-6])
    if i-1 >= 0:
        a[i-1] = min(a[i]+1, a[i-1])
print(ans+a[0])

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10000)  # RecursionError対策

def func(n):
    if n==0:
        return 0 # 終端条件
    if memo[n] != -1:
        return memo[n] # 探索済み

    res = n

    for i in range(1,n+1):
        pow6 = 6 ** i
        if pow6 > n:
            break
        res = min(res, func(n-pow6)+1)

    for i in range(1,n+1):
        pow9 = 9 ** i
        if pow9 > n:
            break
        res = min(res, func(n-pow9)+1)

    memo[n] = res
    return res


N = int(input())

max_n = 110000
memo = [-1] * max_n
ans = func(N)
print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

def func(n):
    if n==0:
        return 0 # 終端条件
    if memo[n] != -1:
        return memo[n] # 探索済み

    res = n

    for i in range(1,n+1):
        pow6 = 6 ** i
        if pow6 <= n:
            res = min(res, func(n-pow6)+1)
        else:
            break

    for i in range(1,n+1):
        pow9 = 9 ** i
        if pow9 <= n:
            res = min(res, func(n-pow9)+1)
        else:
            break

    memo[n] = res
    return res


N = int(input())

max_n = 110000
memo = [-1] * max_n
ans = func(N)
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())

dp = [10**5]*(N+1)
dp[0] = 0
dp[1] = 1
s = 6
n = 9
for i in range(2,N+1):
    if 6*s <= i:
        s *= 6
    if 9*n <= i:
        n *= 9
    dp[i] = min(dp[i-1], dp[i-s], dp[i-n])+1
print(dp[N])

Submission status: Runtime Error

Solution code:
N=int(input())
dp=[0]*100000
a=1
b=6
c=9
for i in range(1,N+1):
  if i>=b*6:
    b*=6
  if i>=c*9:
    c*=9
  if i<6:
    dp[i]=i
  elif i<9:
    dp[i]=min(dp[i-a]+1,dp[i-b]+1)
  else:
    dp[i]=min([dp[i-a]+1,dp[i-b]+1,dp[i-c]+1])
print(dp[N])

Submission status: Runtime Error

Solution code:
n = int(input())
money = []
for i in range(n):
    if 6**i>n:
        break
    money.append(6**i)
for j in range(1,n):
    if 9**j>n:
        break
    money.append(9**j)
money.sort()
print(money)

ans = {}
for i in range(len(money)):
    if n//money[-(i+1)]>0:
        ans.setdefault(money[-(i+1)],n//money[-(i+1)])
    n = n%money[-(i+1)]
if ans[9]>=1 and ans[1]>=3:
    ans[9]-=1
    ans[1]-=3
    ans.setdefault(6,0)
    ans[6]+=2

#print(ans)
print(sum(ans.values()))

Submission status: Runtime Error

Solution code:
n = int(input())
lst_take = []
max_val = 100000
used = []
for i in range(1,15):
  if 6 ** i <=  max_val:
    lst_take.append(6**i)
  if 9 ** i <= max_val:
    lst_take.append(9**i)  
lst_take = sorted(set(lst_take), reverse=True)
while True:
  if n==0:
    break
    
  flag = True
  for i in lst_take:
    if i <= n and i not in used:
      n -= i
      count += 1
      used.append(i)
      flag = False
      break
  if flag:
    count += n
    break
print(count)

Submission status: Runtime Error

Solution code:
n = int(input())
dp = [float("Inf")]*(n+1)
for i in range(5):
    dp[i] = i
for i in range(n):
    for j in range(1,n//6+1):
        if i + 6**j > n:
            break
        dp[i+6**j] = min(dp[i+6**j], dp[i] + 1)
    for j in range(1,n//9+1):
        if i + 9**j > n:
            break
        dp[i+9**j] = min(dp[i+9**j], dp[i] + 1)
print(dp[-1])

Submission status: Runtime Error

Solution code:
n = int(input())
dp = [float("Inf")]*(n+1)
dp[0] = 0
for i in range(n):
    if dp[i] == float("Inf"):
        pass
    else:
        for j in range(1,n//6):
            if i + 6**j > n:
                break
            dp[i+6**j] = min(dp[i+6**j], dp[i] + 1)
        for j in range(1,n//9):
            if i + 9**j > n:
                break
            dp[i+9**j] = min(dp[i+9**j], dp[i] + 1)
ans = n
for i in range(n-5, n+1):
    ans = min(ans, dp[i]+n-i)
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
dp = [float("Inf")]*(n+1)
dp[0] = 0
for i in range(n):
    if dp[i] == float("Inf"):
        pass
    else:
        for j in range(1,n//6):
            if i + 6**j > n:
                break
            dp[i+6**j] = min(dp[i+6**j], dp[i] + 1)
        for j in range(1,n//9):
            if i + 9**j > n:
                break
            dp[i+9**j] = min(dp[i+9**j], dp[i] + 1)
ans = float("Inf")
for i in range(n-5, n+1):
    ans = min(ans, dp[i]+n-i)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
from functools import lru_cache


sys.setrecursionlimit(100000)


@lru_cache(maxsize=None)
def rec(n):
    if n == 0:
        return 0
    res = n
    i = 1
    while i <= n:
        res = min(res, rec(n - i) + 1)
        i *= 6
    i = 9
    while i <= n:
        res = min(res, rec(n - i) + 1)
        i *= 9
    return res


N = int(input())
print(rec(N))

Submission status: Runtime Error

Solution code:
L=[1]
n=int(input())
x = 6
y = 9
while x <= n:
  L.append(x)
  x *= 6
while y <= n:
  L.append(y)
  y *= 9
L.sort()#[1,6,9,36,81]
dp = [float("Inf")]*(n+1)
dp[0] = 0
for i in range(n+1):#0~81
  for j in L:#1,6,9
    dp[i+j] = min(dp[i+j],dp[i]+1)#dp=[0,1,...1,.1]
print(dp[n])

Submission status: Runtime Error

Solution code:
n = int(input())

memo = [-1]*(n+1)

def func(n):
    if n == 0:
        return 0

    if memo[n] != -1:
        return memo[n]

    res = n
    i = 1
    while i <= n:
        res = min(res, func(n-i)+1)
        i *= 6

    j = 1
    while j <= n:
        res = min(res, func(n-j)+1)
        j *= 9

    memo[n] = res
    return memo[n]

ans = func(n)
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
import sys
sys.setrecursionlimit(100000)
dp = [-1] * (N + 1)
def rec(n):
    if n == 0:
        return 0
    if dp[n] != -1:
        return dp[n]
    res = n
    i = 0
    while n >= i ** 6:
        pow6 = i ** 6
        res = min(res, rec(n - pow6) + 1)
        i += 1

    j = 0
    while n >= j ** 9:
        pow9 = j ** 9
        res = min(res, rec(n - pow9) + 1)
        i += 1

    dp[n] = res
    return dp[n]
print(rec(N))

Submission status: Runtime Error

Solution code:
n=int(input())

#初期化
#コイン1円
dp=[i for i in range(n+1)]

#コイン6円
i=1
while 6**i<=n:
    dp[6**i]=1
    i+=1
#コイン6円
i=1
while 9**i<=n:
    dp[9**i]=1
    i+=1

for i in range(1,n+1):
    for j in range(i):
        dp[i]=min(dp[i],dp[j]+dp[i-j])
    if i%1000==0:
        #print(i)
print(dp[-1])

Submission status: Runtime Error

Solution code:
# coding: utf-8
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# dp
N = ir()
INF = 10 ** 8
dp = np.array([INF] * 100001)
dp[0] = 0
for i in range(5, 0, -1):
    num = 9 ** i
    for j in range(100000):
        if j+num <= N:
            dp[j+num] = min(dp[j+num], dp[j]+1)

for i in range(6, 0, -1):
    num = 6 ** i
    for j in range(100000):
        if j+num <= N:
            dp[j+num] = min(dp[j+num], dp[j]+1)

num = 1
for j in range(100000):
    dp[j+num] = min(dp[j+num], dp[j]+1)

answer = dp[N]
print(answer)

Submission status: Runtime Error

Solution code:
import sys
n = int(input())
mem = [None]*(n+1)
def DFS(k, d):
    if k<0 or d>2000:
        return 10**9
    if k==0:
        return 0
    if k<6:
        return k
    if mem[k] is not None:
        return mem[k]
    tmp = 10**5
    for i in range(1, 7):
        tmp = min(tmp, DFS(k-6**i, d+1)+1)
    for i in range(1, 6):
        tmp = min(tmp, DFS(k-9**i, d+1)+1)
    mem[k] = tmp
    return tmp
if n<6:
    print(n)
else:
    print(DFS(n, 0))

Submission status: Runtime Error

Solution code:
import sys
n = int(input())
mem = [None]*(n+1)
def DFS(k, d):
    if k<0 or d>5000:
        return 10**9
    if k==0:
        return 0
    if k<6:
        return k
    if mem[k] is not None:
        return mem[k]
    tmp = 10**5
    for i in range(1, 7):
        tmp = min(tmp, DFS(k-6**i, d+1)+1)
    for i in range(1, 6):
        tmp = min(tmp, DFS(k-9**i, d+1)+1)
    mem[k] = tmp
    return tmp
if n<6:
    print(n)
else:
    print(DFS(n, 0))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の呼び出し制限

N = int(input())

def ch(x, y):
    cnt = 0
    while x**cnt <= y:
        cnt += 1
    return cnt

coin = [1]
for i in range(1, ch(6, N)):
    coin.append(6**i)

for i in range(1, ch(9, N)):
    coin.append(9**i)

def rec(n):
    if n == 0: return 0
    if memo[n] != -1: return memo[n]
    
    res = n
    
    for c in coin:
        res = min(res, rec(n-c)+1)
    
    memo[n] = res
    return memo[n]

memo = [-1]*(10**5+10)
rec(N)
print(memo[N])

Submission status: Runtime Error

Solution code:
%
n = int(input())

def func(n, i):
    ans = 0
    while  n > 0:
        ans += n % i
        n // = i
    return ans

b = n
for i in range(n+1):
    tmp = func(i, 6) + func(n-1, 9)
    b = min(tmp, b)

print(b)

Submission status: Runtime Error

Solution code:
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial
from bisect import bisect_left #bisect_left(list, value)
#from fractions import gcd
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

N = int(input())
INF = 10**18

res = 0
dp = [INF]*(2*N)
dp[0] = 0
for i in range(0, N+1):
    dp[i+1] = min(dp[i+1], dp[i]+1)

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

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

print(dp[N])

Submission status: Runtime Error

Solution code:
SIX  = [6**i for i in range(1,7)]
NINE = [9**i for i in range(1,5)]
SIX.extend(NINE)
SIX.append(1)
SIX = sorted(SIX,reverse=True)
N2 =N
cnt=0
for s in SIX:
    if N2 >=s:
        
        P,N2 = divmod(N2,s)
        cnt+=P
    
print(cnt)

Submission status: Runtime Error

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

    #6**6=46656, 6**7=279936
    #9**5=59049, 9**6=531441
    list = [1]
    list.extend([6 ** i for i in range(1, 7)])
    list.extend([9 ** i for i in range(1, 6)])

    dp = [float("inf")] * 100000
    dp[0] = 0

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

    print(dp[N])

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import math
# n進数の各位の和
def base_10_n(x,n):
    tmpx = x
    a = int(math.log(x,n))
    ans = 0
    for i in range(a,-1,-1):
        ans += tmpx // n**i
        tmpx %= n**i
    ans += tmpx
    return ans

def main():
    N = int(input())
    ans = base_10_n(N,6)
    for j in range(1, (N//9)+1):
        c = base_10_n(N-9*j,6)
        d = base_10_n(9*j,9)
        ans = min(ans, c+d)
    print(ans)
    # print(base_10_n(-1,6))
    # print([i for i in range(1,(26//9)+1)])

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import math
# n進数の各位の和
def base_10_n(x,n):
    a = int(math.log(x,n))
    ans = 0
    for i in range(a,-1,-1):
        ans += x // n**i
        x %= n**i
    ans += x
    return ans

def main():
    N = int(input())
    ans = base_10_n(N,6)
    for j in range(1, (N//9)+1):
        c = base_10_n(N-9*j,6)
        d = base_10_n(9*j,9)
        ans = min(ans, c+d)
    print(ans)
    # print(base_10_n(-1,6))
    # print([i for i in range(2,-1,-1)])

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import math
# n進数の各位の和
def base_10_n(x,n):
    a = int(math.log(x,n))
    ans = 0
    for i in range(a,-1,-1):
        ans += x // n**i
        x %= n**i
    ans += x
    return ans

def main():
    N = int(input())
    ans = base_10_n(N,6)
    for j in range(1,N//18 + 1):
        c = base_10_n(N-18*j,6)
        d = base_10_n(18*j,9)
        ans = min(ans, c+d)
    print(ans)
    # print(int(math.log(85,9)))
    # print([i for i in range(2,-1,-1)])

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import math
# n進数の各位の和
def base_10_n(x,n):
    a = int(math.log(x,n))
    ans = 0
    for i in range(a,-1,-1):
        ans += x // n**i
        x %= n**i
    ans += x
    return ans

def main():
    N = int(input())
    ans = N
    for j in range(1,N//18 + 1):
        a = base_10_n(N-18*j,6)
        b = base_10_n(18*j,9)
        ans = min(ans, a+b)
    print(ans)
    # print([i for i in range(2,-1,-1)])

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import math
# n進数の各位の和
def base_10_n(x,n):
    a = int(math.log(x,n))
    ans = 0
    for i in range(a+1,0,-1):
        ans += x // n**i
        x %= n**i
    ans += x
    return ans

def main():
    N = int(input())
    ans = N
    for j in range(1,N//18 + 1):
        a = base_10_n(N-18*j,6)
        b = base_10_n(18*j,9)
        # print(18*j,a,b)
        ans = min(ans, a+b)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from collections import deque
from math import log


def main():
  n = input()
  
  q = deque()
  q.append((n, 0))
  
  while len(q) > 0:
    node = q.popleft()
    amount = node[0]
    
    if amount == 0:
      print(node[1])
      return
    elif amount > 0:
      log9_fl = int(log(amount, 9))
      log6_fl = int(log(amount, 6))
      
      q.append((amount - 9 ** log9_fl, node[1] + 1))
      q.append((amount - 6 ** log6_fl, node[1] + 1))
      q.append((amount - 1, node[1] + 1))
      
  
if __name__ == "__main__":
  main()

Submission status: Runtime Error

Solution code:
from math import log


def count_time(amount):
  if log(amount, 9) >= 1:
    return 1 + count_time(amount - 9 ** int(log(amount, 9)))
  if log(amount, 6) >= 1:
    return 1 + count_time(amount - 6 ** int(log(amount, 6)))
  return amount


def main():
  n = int(input())
  print(count_time(n))


if __name__ == "__main__":
  main()

Submission status: Runtime Error

Solution code:
n = int(input())
count=0
while n>=5:
  temp=[]
  i=1
  while n>=6**i:
    temp.append(6**i)
    i=i+1
  i=1
  while n>=9**i:
    temp.append(9**i)
    i=i+1
  n=n-max(temp)
  count=count+1
print(count+n)

Submission status: Runtime Error

Solution code:
n=int(input())
dp=[float("inf")]*n
dp[0]=0
for i in range(n-1):
    for j in range(1,7):
        j=6**j
        if i+j<n:
            cost[i+j]=min(dp[i+j],dp[i]+1)
    for j in range(1,6):
        j=9**j
        if i+j<n:
            cost[i+j]=min(dp[i+j],dp[i]+1)
    dp[i+1]=min(dp[i+1],dp[i]+1)
    

print(dp[-1])