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: Time Limit Exceeded

Solution code:
N = int(input())

def Base10toN(X, n):
    if (int(X / n)):
        return Base10toN(int(X / n), n) + str(X % n)
    else:
        return str(X % n)

def f(amount):
    if amount <= 5:
        return amount
    s = Base10toN(amount, 6)
    fs = f(amount - 6 ** (len(s) - 1))
    n = Base10toN(amount, 9)
    fn = f(amount - 9 ** (len(n) - 1))
    if (fs < fn):
        return fs + 1
    else:
        return fn + 1

print(f(N))

Submission status: Time Limit Exceeded

Solution code:

N=int(input())
number_of_withdrawal=[]

def floor(float_number):
    integer = 0
    while integer < float_number:
        integer+=1
    if integer == float_number:
        return integer
    else:
        integer-=1
        return integer

for money_6 in range(0, N+1):
    money_9 = N-money_6

    i=0
    count_6_pow_number=0
    while pow(6,i)<=money_6:
        count_6_pow_number += (floor(money_6/pow(6,i)))%6
        i+=1
    j=0
    count_9_pow_number=0
    while pow(9,j)<=money_9:
        count_9_pow_number += (floor(money_9/pow(9,j)))%9
        j+=1

    # print(money_6, money_9, sum(count_6_pow_number), sum(count_9_pow_number))
    number_of_withdrawal.append(count_6_pow_number+count_9_pow_number)


print(min(number_of_withdrawal))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
number_of_withdrawal=[]

def floor(float_number):
    integer = 0
    while integer < float_number:
        integer+=1
    if integer == float_number:
        return integer
    else:
        integer-=1
        return integer

for money_6 in range(0, N+1):
    money_9 = N-money_6

    i=0
    count_6_pow_number=[]
    while pow(6,i)<=money_6:
        count_6_pow_number.append((floor(money_6/pow(6,i)))%6)
        i+=1
    j=0
    count_9_pow_number=[]
    while pow(9,j)<=money_9:
        count_9_pow_number.append((floor(money_9/pow(9,j)))%9)
        j+=1

    # print(money_6, money_9, sum(count_6_pow_number), sum(count_9_pow_number))
    number_of_withdrawal.append(sum(count_6_pow_number)+sum(count_9_pow_number))


print(min(number_of_withdrawal))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n=int(input())
s=np.zeros((100001,12),dtype='int16')
a=[1,6,9,36,81,216,729,1296,6561,7776,46656,59049]

for i in range(n+1):
    s[i][0]=i
for i in range(1,12):
    for j in range(n+1):
        s[j][i]=s[j][i-1]
        if a[i]<=j:
            if s[j][i]>s[j-a[i]][i]+1:
                s[j][i]=s[j-a[i]][i]+1
print(s[n][11])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n=int(input())
s=np.zeros((100001,12),dtype='int32')
a=[1,6,9,36,81,216,729,1296,6561,7776,46656,59049]

for i in range(n+1):
    s[i][0]=i
for i in range(1,12):
    for j in range(n+1):
        s[j][i]=s[j][i-1]
        if a[i]<=j:
            if s[j][i]>s[j-a[i]][i]+1:
                s[j][i]=s[j-a[i]][i]+1
print(s[n][11])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
count = 0
ans = []
for i in range(N+1):
    count1 = 0
    count2 = 0
    N1 = N - i
    x = i
    for j in reversed(range(7)):
        while x >= 6**j:
            x -= 6**j
            count1 += 1
    for j in reversed(range(6)):
        while N1 >= 9**j:
            N1 -= 9**j
            count2 += 1
    count = count1 + count2
    ans.append(count)
print(min(ans))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
#a = [1,6,36,216,1296,7776,46656]
#b = [1,9,81,729,6561,59049]
c = [0]
n = 1
while n <= N:
  if n == 1:
    c.append(1)
    n += 1
  elif n < 6:
    c.append(1+c[n-1])
    n += 1
  elif n < 9:
    c.append(1+min(c[n-1],c[n-6]))
    n += 1
  elif n < 36:
    c.append(1+min(c[n-1],c[n-6],c[n-9]))
    n += 1
  elif n < 81:
    c.append(1+min(c[n-1],c[n-6],c[n-9],c[n-36]))
    n += 1
  elif n < 216:
    c.append(1+min(c[n-1],c[n-6],c[n-9],c[n-36],c[n-81]))
    n += 1
  elif n < 729:
    c.append(1+min(c[n-1],c[n-6],c[n-9],c[n-36],c[n-81],c[n-216]))
  elif n < 1296:
    c.append(1+min(c[n-1],c[n-6],c[n-9],c[n-36],c[n-81],c[n-216],c[n-729]))
  elif n < 6561:
    c.append(1+min(c[n-1],c[n-6],c[n-9],c[n-36],c[n-81],c[n-216],c[n-729],c[n-1296]))
  elif n < 7776:
    c.append(1+min(c[n-1],c[n-6],c[n-9],c[n-36],c[n-81],c[n-216],c[n-729],c[n-1296],c[n-6561]))
  elif n < 46656:
    c.append(1+min(c[n-1],c[n-6],c[n-9],c[n-36],c[n-81],c[n-216],c[n-729],c[n-1296],c[n-6561],c[n-7776]))
  elif n < 59049:
    c.append(1+min(c[n-1],c[n-6],c[n-9],c[n-36],c[n-81],c[n-216],c[n-729],c[n-1296],c[n-6561],c[n-7776],c[n-46656]))
  else:
    c.append(1+min(c[n-1],c[n-6],c[n-9],c[n-36],c[n-81],c[n-216],c[n-729],c[n-1296],c[n-6561],c[n-7776],c[n-46656],c[n-59049]))
print(c[N])

Submission status: Time Limit Exceeded

Solution code:
def g(n, a):
    for i in range(1, 100):
        if a**i > n:
            return a**(i-1)
    return -1

def solve(n):
    if n < 6:
        return n
    a = g(n, 6)
    b = g(n, 9)
    return min(solve(n-a)+1, solve(n-b)+1)

# assert solve(127) == 4
# assert solve(3) == 3
# assert solve(44852) == 16

print solve(input())

Submission status: Time Limit Exceeded

Solution code:
from itertools import count, takewhile

def dfs(n):
  if n < 6:
    return n
  max9 = max(takewhile(lambda x: x<=n, (9**i for i in count())))
  max6 = max(takewhile(lambda x: x<=n, (6**i for i in count())))
  return min(dfs(n-max9), dfs(n-max6))+1

print(dfs(int(input())))

Submission status: Time Limit Exceeded

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



i=6



for i_0 in range(max(N//X[0]-i,0),N//X[0]+1):
    N_0=N-X[0]*i_0
    for i_1 in range(max(N_0//X[1]-i,0),N_0//X[1]+1):
        N_1=N_0-X[1]*i_1
        for i_2 in range(max(N_1//X[2]-i,0),N_1//X[2]+1):
            N_2=N_1-X[2]*i_2
            for i_3 in range(max(N_2//X[3]-i,0),N_2//X[3]+1):
                N_3=N_2-X[3]*i_3
                for i_4 in range(max(N_3//X[4]-i,0),N_3//X[4]+1):
                    N_4=N_3-X[4]*i_4
                    for i_5 in range(max(N_4//X[5]-i,0),N_4//X[5]+1):
                        N_5=N_4-X[5]*i_5
                        for i_6 in range(max(N_5//X[6]-i,0),N_5//X[6]+1):
                            N_6=N_5-X[6]*i_6
                            for i_7 in range(max(N_6//X[7]-i,0),N_6//X[7]+1):
                                N_7=N_6-X[7]*i_7
                                for i_8 in range(max(N_7//X[8]-i,0),N_7//X[8]+1):
                                    N_8=N_7-X[8]*i_8
                                    for i_9 in range(max(N_8//X[9]-i,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: Time Limit Exceeded

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



i=7



for i_0 in range(max(N//X[0]-i,0),N//X[0]+1):
    N_0=N-X[0]*i_0
    for i_1 in range(max(N_0//X[1]-i,0),N_0//X[1]+1):
        N_1=N_0-X[1]*i_1
        for i_2 in range(max(N_1//X[2]-i,0),N_1//X[2]+1):
            N_2=N_1-X[2]*i_2
            for i_3 in range(max(N_2//X[3]-i,0),N_2//X[3]+1):
                N_3=N_2-X[3]*i_3
                for i_4 in range(max(N_3//X[4]-i,0),N_3//X[4]+1):
                    N_4=N_3-X[4]*i_4
                    for i_5 in range(max(N_4//X[5]-i,0),N_4//X[5]+1):
                        N_5=N_4-X[5]*i_5
                        for i_6 in range(max(N_5//X[6]-i,0),N_5//X[6]+1):
                            N_6=N_5-X[6]*i_6
                            for i_7 in range(max(N_6//X[7]-i,0),N_6//X[7]+1):
                                N_7=N_6-X[7]*i_7
                                for i_8 in range(max(N_7//X[8]-i,0),N_7//X[8]+1):
                                    N_8=N_7-X[8]*i_8
                                    for i_9 in range(max(N_8//X[9]-i,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: Time Limit Exceeded

Solution code:
n_max = 100000

bs = [(6 ** i, 6) for i in range (1, 10)]
bs.extend([(9 ** i, 9) for i in range (1, 10)])
bs = list(sorted(filter(lambda x: x[0] <= n_max, bs)))
bms = []
s = 5
for b, i in bs:
    s += b * (i - 1)
    bms.append((b, i, s))

#print(bs)
#print(bms, len(bms))

#m = 44852
m = int(input())

stack = [(m, 0, len(bms) - 1)]
#print("search start!")
result = 10000
while stack:
    m, n, bms_i = stack.pop()
    b, i, s = bms[bms_i]
    #print(m, n, bms_i, b, i, s)

    if n > result:
        #print("skip!", m, n, bms_i)
        continue
    if bms_i < 0:
        if m <= 6 and m + n < result:
            result = m + n
        #    print('get result!', result)
        continue

    for j in range(i):
        next_m = m - b * j
        if next_m >= 0 and n + j < result:
            stack.append((next_m, n + j, bms_i - 1))

print(result)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = [1,6,36,216,1296,7776,46656]
b = [1,9,81,729,6561,59049]
def ans(n):
  if n<=0:
    return 1000
  elif n in a or n in b:
    return 1
  else:
    return(min(ans(n-1),ans(n-6),ans(n-36),ans(n-216),ans(n-1296),ans(n-7776),ans(n-46656),ans(n-9),ans(n-81),ans(n-729),ans(n-6561),ans(n-59049))+1)
m = 1
while m <= N:
  ans(m)
print(ans(N))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
def six(n):
  i = 0
  while n%6 == 0:
    n = n//6
    i += 1
  return i

def nine(n):
  i = 0
  while n%9 == 0:
    n = n//9
    i += 1
  return i

def ans(n):
  if n-6**six(n)==0:
    return 1
  elif n-9**nine(n)==0:
    return 1
  else:
    return max(six(n)+ans(n-6**six(n)),nine(n)+ans(n-9**nine(n)))

ans(44852)

Submission status: Time Limit Exceeded

Solution code:
num = [i for i in range(0,100001)]

for j in range(1,100001):
        num[j] = j//6 + num[j%6]

for j in range(1,100001):
        num[j] = min(num[j],j//9+num[j%9])

for j in range(1,100001):
        num[j] = min(num[j],j//36+num[j%36])

for j in range(81,324):
        num[j] = min(num[j],1+num[j-81])
for j in range(162,324):
        num[j] = min(num[j],2+num[j-162])
for j in range(243,324):
        num[j] = min(num[j],3+num[j-243])
for j in range(324,100001):
        num[j] = (j//324)*4 + num[j%234]

for j in range(216,648):
        num[j] = min(num[j],1+num[j-216])
for j in range(432,648):
        num[j] = min(num[j],2+num[j-216*2])
for j in range(648,100001):
        num[j] = (j//648)*3 + num[j%648]

for i in range(1,8):
        for j in range(729*i,729*8):
                num[j] = min(num[j],i+num[j-729*i])
for j in range(729*8,100001):
        num[j] = (j//(729*8))*8+num[j%(729*8)]

MoneyYouCanGet = [6**4,9**4,6**5,6**6,9**5]

for i in MoneyYouCanGet:
        for j in range(1,100001):
                k = 1
                while k*i<j:
                        num[j] = min(num[j],k+num[j-k*i])
                        k += 1

N = int(input())
print(num[N])

Submission status: Time Limit Exceeded

Solution code:
def calc(x, y, r_list, tmp_result):
    j = y
    while j <= x:
        tmp_result = min(tmp_result, r_list[x - y] + 1)
        j = j * y

    return tmp_result


n = int(input())
result = [0]

i = 1
while i <= n:
    tmp = result[i-1] + 1
    tmp = calc(i, 6, result, tmp)
    tmp = calc(i, 9, result, tmp)
    result.append(tmp)

print(result[n])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

ans = 10**10
for a in range(6):
    for b in range(3):
        for c in range(6):
            for d in range(6):
                for e in range(6):
                    for f in range(6):
                        for g in range(2):
                            for h in range(4):
                                for i in range(8):
                                    for k in range(9):
                                        for l in range(9):
                                            for m in range(2):
                                                if 1*a + 6*b + 36*c + 6**3*d + 6**4*e + 6**5*f + 6**6*g + 9*h + 9**2*i + 9**3*k + 9**4*l + 9**5*m == n:
                                                    ans = min(ans, a+b+c+d+e+f+g+h+i+k+l+m)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
n=int(input())
nine_li=[]
six_li=[]
for i in range(math.ceil(math.sqrt(n))+1):
    nine_li.append(9**i)
for i in range(math.ceil(math.sqrt(n)+1)):
    six_li.append(6**i)
nine_li.extend(six_li)
nine_li.sort(reverse=True)
cnt=0
while n!=0:
    for i in nine_li:
        if i<n:
            n-=i
            cnt+=1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import queue


class Edge:
    def __init__(self, from_v, to_v, cost):
        self.from_v = from_v
        self.to_v = to_v
        self.cost = cost

    def __lt__(self, other):
        return self.cost < other.cost

    def get_from_v(self):
        return self.from_v

    def get_to_v(self):
        return self.to_v

    def get_cost(self):
        return self.cost


class Vertex:
    def __init__(self, cost, id):
        self.cost = cost
        self.id = id

    def __lt__(self, other):
        return self.cost < other.cost

    def get_cost(self):
        return self.cost

    def get_id(self):
        return self.id


class Dijkstra:
    def __init__(self, number_of_vertex):
        # self.edges = []
        self.graf = [[] for _ in range(number_of_vertex)]
        self.number_of_vertex = number_of_vertex
        self.distance = []  # 最短距離
        self.INF = 5000000000000000

    def add_edge(self, from_v, to_v, cost):
        self.graf[from_v].append(Edge(from_v, to_v, cost))

    def compute_shortest_distance(self, start):
        self.distance = [self.INF] * self.number_of_vertex
        self.distance[start] = 0
        que = queue.PriorityQueue()

        que.put(Vertex(0, start))

        while not que.empty():
            top = que.get()
            cost = top.get_cost()
            id = top.get_id()
            if self.distance[id] < cost: continue
            for a_edge in self.graf[id]:
                to_v = a_edge.get_to_v()
                from_v = a_edge.get_from_v()
                prev_cost = self.distance[from_v]
                next_cost = self.distance[to_v]
                if next_cost > prev_cost + a_edge.get_cost():
                    next_cost = prev_cost + a_edge.get_cost()
                    self.distance[to_v] = next_cost
                    que.put(Vertex(next_cost, to_v))


if __name__ == '__main__':
    N = int(input())
    dij = Dijkstra(N + 1)
    for i in range(1, N + 1):
        dij.add_edge(i, i - 1, 1)
        j = 6
        while j <= i:
            dij.add_edge(i, i - j, 1)
            j *= 6
        j = 9
        while j <= i:
            dij.add_edge(i, i - j, 1)
            j *= 9
    dij.compute_shortest_distance(N)
    print(dij.distance[0])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

M = 100000

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


cache = {}


def solve(x, l):
    if len(l) == 0:
        return 10000000000

    if x in cache:
        if len(l) in cache[x]:
            return cache[x][len(l)]

    t = l[0]
    if x // t > 0:
        res = []
        for i in range(x // t + 1):
            count = i
            rest = x - (t * i)
            if rest == 0:
                return count

            val = solve(rest, l[1:])
            if rest not in cache:
                cache[rest] = {}
            cache[rest][len(l[1:])] = val
            res.append(count + val)
        return min(res)
    else:
        val = solve(x, l[1:])
        if x not in cache:
            cache[x] = {}
        cache[x][len(l[1:])] = val
        return val


# for i in range(10):
#     val = 9 ** i
#     if val <= M:
#         print(val)
#         c.append(val)
#
# for i in range(10):
#     val = 6 ** i
#     if val <= M:
#         print(val)
#         c.append(val)

# count = 0

result = solve(N, c)
# for i in c:
#     if rest // i > 0:
#         count += rest // i
#         print(str(i) + ', ' + str(rest // i) + ' times, rest = ' + str(rest % i))
#         rest = rest % i
#
#     if rest == 0:
#         break

print(result)

Submission status: Time Limit Exceeded

Solution code:
from math import log

def exp(n, base):
    e = int(log(n, base))
    if base ** (e + 1) <= n:
        return e + 1
    else:
        return e

def min_withdraw(n):
    if n < 6:
        return n
    else:
        exp_nine = exp(n, 9)
        exp_six = exp(n, 6)
        return 1 + min(min_withdraw(n - (6 ** exp_six)), min_withdraw(n - (9 ** exp_nine)))
    
    
if __name__ == '__main__':
    n = int(input())
    print(min_withdraw(n))

Submission status: Time Limit Exceeded

Solution code:
# for j in range(1, 11):

n = int(input())
# n = j
ans = n
pay = []
for i in range(1, 10):
    if 6 ** i <= 100000:
        pay.append(6 ** i)
    if 9 ** i <= 100000:
        pay.append(9 ** i)
pay.sort(reverse=True)


def func(n, times):
    for i in pay:
        n2 = n
        times2 = times
        if i <= n:
            global ans
            n2 -= i
            times2 += 1
            if ans > times2 + n2:
                ans = times2 + n2
            if n2 >= 6 and times2 < ans:
                func(n2, times2)


func(n, 0)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

M = 100000

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


cache = {}

def solve(count, x, l):
    if len(l) == 0:
        return 10000000000

    t = l[0]
    if x // t > 0:
        res = []
        for i in range(x // t + 1):
            if i > 0:
                count += x // (t * i)
                rest = x % (t * i)
                if rest == 0:
                    return count
                res.append(solve(count, rest, l[1:]))
            else:
                res.append(solve(count, x, l[1:]))
        return min(res)
    else:
        return solve(count, x, l[1:])


# for i in range(10):
#     val = 9 ** i
#     if val <= M:
#         print(val)
#         c.append(val)
#
# for i in range(10):
#     val = 6 ** i
#     if val <= M:
#         print(val)
#         c.append(val)

# count = 0
rest = N

result = solve(0, rest, c)
# for i in c:
#     if rest // i > 0:
#         count += rest // i
#         print(str(i) + ', ' + str(rest // i) + ' times, rest = ' + str(rest % i))
#         rest = rest % i
#
#     if rest == 0:
#         break

print(result)

Submission status: Time Limit Exceeded

Solution code:
key=[531441, 279936, 59049, 46656, 7776, 6561, 1296, 729, 216, 81, 36, 9, 6, 1]
n=int(input())


def solver(nNum,keyNum):
    r=nNum%key[keyNum]
    if r==0:
        return nNum//key[keyNum]
    else:
        ans=1000
        for i in range(nNum//key[keyNum]+1):
            ans=min(ans,i+solver(nNum-key[keyNum]*i,keyNum+1))
        return ans
print(solver(n,0))

Submission status: Time Limit Exceeded

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

def strbank(N):
    if N == 0:
        return 0
    else:
        m = math.floor(math.log(N, 6))
        n = math.floor(math.log(N, 9))
        a = 6**m
        b = 9**n
        ans = 1 + min(strbank(N - a), strbank(N - b))
        return ans

h = strbank(N)
print(h)

Submission status: Time Limit Exceeded

Solution code:
import math

N = int(input())

def calc(n, i):
    if n == 0:
        return i
    else:
        return min(
            calc(n - 6**int(math.log(n,6)), i+1),
            calc(n - 9**int(math.log(n,9)), i+1)
        )
    
print(calc(N, 0))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

def N_dev6(N):
    ans = 0
    while True:
        N = N/6
        if N >= 1:
            ans += 1
        else:
            break
    return ans

def N_dev9(N):
    ans = 0
    while True:
        N = N/9
        if N >= 1:
            ans += 1
        else:
            break
    return ans

def deep(N):
    if N <= 5:
        result = N
    else:
        N_sub6 = N - 6**N_dev6(N)
        N_sub9 = N - 9**N_dev9(N)
        result = 1 + min(deep(N_sub6),deep(N_sub9))
    return result

print(deep(N))

Submission status: Time Limit Exceeded

Solution code:
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 = 1
table = set(possible)
while True:
  if n in table:
    print(ans)
    break
  ans+=1
  nexttable = set()
  for num in table:
    for p in possible:
      if num + p <100000:
        nexttable.add(num+p)
  table = table | nexttable

Submission status: Time Limit Exceeded

Solution code:
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 = 1
table = set(possible)
while True:
  if n in table:
    print(ans)
    break
  ans+=1
  nexttable = set()
  for num in table:
    for p in possible:
      nexttable.add(num+p)
  table = table | nexttable

Submission status: Memory Limit Exceeded

Solution code:
import sys
import heapq
from math import ceil, floor
from collections import deque, Counter, defaultdict
from fractions import gcd
input = lambda: sys.stdin.readline().rstrip()

def eprint(s):
    sys.stderr.write('DEBUG: {}'.format(s))
    return

def shortest_path(s, n, w, es):
    d = [float("inf")]*n
    d[s] = 0
    while True:
        update = False
        for p,q,r in es:
            if d[p] != float("inf") and d[q] > d[p] + r:
                d[q] = d[p] + r
                update = True
        if not update:
            break
    return d

def main():
    n = int(input())
    es = list()
    cnt = 0
    ps = [1,6,36,216,1296,7776,46656,9,81,729,6561,590491,6,36,216,1296,7776,46656,9,81,729,6561,59049]
    ps.sort()
    for i in range(n+1):
        for j in ps:
            if i + j <= n:
                es.append([i, i+j, 1])
                cnt += 1
            else:
                break

    reslut = shortest_path(0,n+1, cnt, es)
    print(reslut[n])
    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
    
    
def main():
    N = I()
    L = [1]
    temp = 1
    while temp <= N:
        temp *= 6
        L.append(temp)
    temp = 1
    while temp <= N:
        temp *= 9
        L.append(temp)
    L.sort()
    D = [i for i in range(N+1)]
    for i in L[1:]:
        for j in range(i, N+1):
            D[j] = min(D[j], D[j-i]+1)
    print(D[N])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def solve():
    n = int(input())
    dp = [True] + [False]*(n+1)
    way = [1] + [6**i for i in range(1,9) if 6**i <= n] + [9**i for i in range(1,7) if 9**i <= n]
    loop_counter = 0
    while True:
        loop_counter += 1
        newdp = [False] * (n+1)
        for w in way:
            for i in range(w, n+1):
                if newdp[i]: continue
                if dp[i-w]: newdp[i] = True
                if newdp[n]: 
                    return loop_counter
        dp = [x for x in newdp]

print(solve())

Submission status: Accepted

Solution code:
n = int(input())
index6, index9, num6, num9 = 0, 0, 0, 0
INF = float('inf')    
a = [INF for _ in range(n+1)]
a[n] = 0

for i in range(n, -1, -1):
    if a[i] == INF:
        continue
    j = 1
    while i-9**j >= 0:
        a[i-9**j] = min(a[i]+1, a[i-9**j])
        j += 1
    j = 1
    while i-6**j >= 0:
        a[i-6**j] = min(a[i]+1, a[i-6**j])
        j += 1
    if i-1 >= 0:
        a[i-1] = min(a[i]+1, a[i-1])
print(a[0])

Submission status: Accepted

Solution code:
n=int(input())
dp=[0]*(n+1)
for i in range(n+1):
  t=i
  count=0
  while t>0:
    count+=t%6
    t//=6
  t=n-i
  while t>0:
    count+=t%9
    t//=9
  dp[i]=count
print(min(dp))

Submission status: Accepted

Solution code:
N = int(input())

dp = [N for i in range(N+1)]

pow6 = [6**i for i in range(1,8)]
pow9 = [9**i for i in range(1,7)]

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

#print(dp)
print(dp[-1])

Submission status: Accepted

Solution code:
import sys
# sys.setrecursionlimit(100000)


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


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


def main():
    n = input_int()
    dp = [0] * (n + 1)  # dp[n] :: n円を引き出す最小の手数

    for i in range(1, n + 1):
        # 1円引き出す
        dp[i] = dp[i - 1] + 1
        # 6**n円引き出す
        j = 6
        while j <= i:
            dp[i] = min(dp[i], dp[i - j] + 1)
            j *= 6
        # 9**n円引き出す
        j = 9
        while j <= i:
            dp[i] = min(dp[i], dp[i - j] + 1)
            j *= 9
    print(dp[n])
    return


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
dp = [i for i in range(N+1)]
 
for i in range(1, 7):
    for j in range(9**i, N+1):
        dp[j] = min(dp[j], dp[j-9**i]+1)
for i in range(1, 7):
    for j in range(6**i, N+1):
        dp[j] = min(dp[j], dp[j-6**i]+1)
print(dp[N])

Submission status: Accepted

Solution code:
import numpy as np

n = int(input())

dp = np.full((n + 1), n + 1, dtype = int)
dp[0] = 0

loop = 0
while dp[n] > n:
    tmp1 = np.full(n + 1, n + 1, dtype = int)
    tmp6 = np.full(n + 1, n + 1, dtype = int)
    tmp9 = np.full(n + 1, n + 1, dtype = int)    
    tmp1[1:] = dp[: -1] + 1
    j = 1
    while 6 ** j <= n:
        tmp6_pre = tmp6
        tmp6[6 ** j:] = dp[:-6 ** j] + 1
        tmp6 = np.minimum(tmp6_pre, tmp6)
        j += 1
    k = 1
    while 9 ** k <= n:
        tmp9_pre = tmp9
        tmp9[9 ** k:] = dp[: -9 ** k] + 1
        tmp9 = np.minimum(tmp9_pre, tmp9)
        k += 1
    tmp1 = np.minimum(tmp1, tmp6)
    tmp1 = np.minimum(tmp1, tmp9)
    dp = np.minimum(dp, tmp1)
    loop += 1
print(dp[n])

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    INF = float('inf')
    dp = [INF] * (N+1)
    dp[0] = 0
    for n in range(1, N+1):
        dp[n] = 1 + dp[n-1]
        for k in range(1, 8):
            p = 6**k
            if n-p >= 0:
                dp[n] = min(dp[n], dp[n-p] + 1)
            p = 9**k
            if n-p >= 0:
                dp[n] = min(dp[n], dp[n-p] + 1)
    
    ans = dp[N]
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())

A = [1]

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

for i in range (1, 6):
	A.append(9**i)
    
A = sorted(A)
import math
DP = [math.inf]*1000001
DP[0] = 0

for i in range (0, 1000001):
	for j in range (0, 12):
		if i+A[j] < 1000001:
			if  DP[i]+1 < DP[i+A[j]]:
				DP[i+A[j]] = DP[i]+1
print(DP[N])

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
units = set()
i = 0
while 6 ** i <= N:
    units.add(6 ** i)
    i += 1
i = 0
while 9 ** i <= N:
    units.add(9 ** i)
    i += 1
units = sorted(units)

mins = list(range(N + 1))
for i in range(1, len(units)):
    unit = units[i]
    for j in range(N):
        if j + unit < len(mins) and mins[j] + 1 < mins[j + unit]:
            mins[j + unit] = mins[j] + 1
print(mins[N])

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    dp = [N] * (N+1)
    dp[0] = 0

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



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
dp = [0] * (10**6+5)
for i in range(1, n+1):
  dp[i] = float("inf")
  power = 1
  while True:
    if i - power < 0:
      break
    dp[i] = min(dp[i], dp[i-power] + 1)
    power *= 6
  power = 1
  while True:
    if i - power < 0:
      break
    dp[i] = min(dp[i], dp[i-power] + 1)
    power *= 9
print(dp[n])

Submission status: Accepted

Solution code:
N=int(input())
INF=10**10
dp=[INF]*(N+1)
dp[0]=0
for i in range(N+1):
    if i+1<=N: 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
    j=1
    while i+9**j<=N:
        dp[i+9**j]=min(dp[i+9**j],dp[i]+1)
        j+=1
print(dp[N])

Submission status: Accepted

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

# In[1]:


N = int(input())


# In[12]:


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


# In[ ]:

Submission status: Accepted

Solution code:
n = int(input())

dp = [1000000 for _ in range(n+1)]
dp[0] = 0

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

print(dp[n])