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:
###############################################################################

from sys import stdout
from bisect import bisect_left as binl
from copy import copy, deepcopy
from collections import defaultdict


mod = 1


def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return tuple(map(int, input_tuple))


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


def intinl(count):
    return [intin() for _ in range(count)]


def modadd(x, y):
    global mod
    return (x + y) % mod


def modmlt(x, y):
    global mod
    return (x * y) % mod


def lcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


def combination(x, y):
    assert(x >= y)

    if y > x // 2:
        y = x - y

    ret = 1

    for i in range(0, y):
        j = x - i
        i = i + 1

        ret = ret * j
        ret = ret // i

    return ret


def get_divisors(x):
    retlist = []
    for i in range(1, int(x**0.5) + 3):
        if x % i == 0:
            retlist.append(i)
            retlist.append(x // i)
    return retlist


def get_factors(x):
    retlist = []
    for i in range(2, int(x**0.5) + 3):
        while x % i == 0:
            retlist.append(i)
            x = x // i
    retlist.append(x)
    return retlist


def make_linklist(xylist):
    linklist = {}
    for a, b in xylist:
        linklist.setdefault(a, [])
        linklist.setdefault(b, [])
        linklist[a].append(b)
        linklist[b].append(a)
    return linklist


def calc_longest_distance(linklist, v=1):
    distance_list = {}
    distance_count = 0
    distance = 0
    vlist_previous = []
    vlist = [v]
    nodecount = len(linklist)

    while distance_count < nodecount:
        vlist_next = []
        for v in vlist:
            distance_list[v] = distance
            distance_count += 1
            vlist_next.extend(linklist[v])
        distance += 1
        vlist_to_del = vlist_previous
        vlist_previous = vlist
        vlist = list(set(vlist_next) - set(vlist_to_del))

    max_distance = -1
    max_v = None
    for v, distance in distance_list.items():
        if distance > max_distance:
            max_distance = distance
            max_v = v

    return (max_distance, max_v)


def calc_tree_diameter(linklist, v=1):
    _, u = calc_longest_distance(linklist, v)
    distance, _ = calc_longest_distance(linklist, u)
    return distance


###############################################################################


def f(n, ceil, clist, acum):
    if not clist and n:
        return float('inf')
    if not clist:
        return acum
    ans = float('inf')
    for i in range(min(ceil, n // clist[0]) + 1):
        ans = min(ans, f(n - i * clist[0], ceil - i, clist[1:], acum + i))
    return ans


def main():
    n = intin()

    clist = [1]
    clist.extend([6, 6**2, 6**3, 6**4, 6**5, 6**6, 6**7])
    clist.extend([9, 9**2, 9**3, 9**4, 9**5, 9**6])
    clist.sort()
    clist.reverse()

    nn = n
    ceil = 0
    for c in clist:
        k = nn // c
        ceil += k
        nn -= k * c
        if nn == 0:
            break

    print(f(n, ceil, clist, 0))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

def f9(a,i):
    if a < 9**i:
        return i-1
    return f9(a,i+1)

def f6(a,i):
    if a < 6**i:
        return i-1
    return f6(a,i+1)

def func(a,ans):
    if a < 6:
        return ans+a
    elif a < 9:
        return ans+1+(a-6)
    return min(func(a-6**f6(a,0),ans+1),func(a-9**f9(a,0),ans+1))

print(func(N,0))

Submission status: Time Limit Exceeded

Solution code:
import functools

N = int(input())
coins = [1]
MAX_MONEY = N
for n in [6, 9]:
    exp = 1
    while MAX_MONEY >= n ** exp:
        coins.append(n ** exp)
        exp += 1
coins = sorted(coins)


@functools.lru_cache(None)
def bank(ci, n):
    if ci == 0:
        return n
    if n == 1:
        return 1
    if n >= coins[ci]:
        return min(bank(ci-1, n), bank(ci, n-coins[ci]) + 1)
    else:
        return bank(ci-1, n)


for ci in range(len(coins)):
    for n in range(1, MAX_MONEY):
        bank(ci, n)

res = bank(len(coins)-1, N)
print(res)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
ans=0
while n:
  a,b=1,1
  while a*6>n:
    a*=6
  while b*9>n:
    b*=9
  n-=max(a,b)
  ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
list6 = [6, 36, 216, 1296, 7776, 46656, 279936]
list9 = [9, 81, 729, 6561, 59049, 531441]

def f(N,ans):
    if N < 6:
        return ans + N
    if N < 9:
        return ans + (N-6)+1
 
    max6 = max(y for y in list6 if N >= y)
    max9 = max(y for y in list9 if N >= y)
    return min(f(N-max6,ans+1),f(N-max9,ans+1))

print(f(int(input()),0))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
list6,list9 = [6],[9]
i = 2
while list6[-1] <= 100000:
    list6.append(6**i)
    i += 1
i = 2
while list9[-1] <= 100000:
    list9.append(9**i)
    i += 1
ans = 0
def f(N,ans):
    if N < 6:
        return ans + N
    if N < 9:
        return ans + (N-6)+1
 
    max6 = max(y for y in list6 if N >= y)
    max9 = max(z for z in list9 if N >= z)
 
    a6 = N-max6
    a9 = N-max9
    return min(f(a6,ans+1),f(a9,ans+1))
print(f(N,0))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

def f(n):
    if n<6:
        return n
    i,j = 0,0
    a,b = n,n
    while a >= 6:
        i += 1
        a //= 6
    while b >= 9:
        j += 1
        b //= 9
    return min(1+f(n-6**i),1+f(n-9**j))

print(f(N))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

six_list = [6 ** i for i in range(7)]
nine_list = [9 ** i for i in range(6)]

import bisect

def six_nine(n):
  if n == 0:
    return 0
  else:
    six = six_list[bisect.bisect_right(six_list, n) - 1]
    nine = nine_list[bisect.bisect_right(nine_list, n) - 1]
    return 1 + min(six_nine(n - six), six_nine(n - nine))


print(six_nine(n))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
dp=[100000]*(N+1)
dp[0]=0
que=[(0,0)]
while len(que)!=0:
    que.sort(key=lambda x:x[0])
    c=que[0][0]
    v=que[0][1]
    que=que[1:]
    if c>dp[v]:
        continue
    pow6=1
    while v+pow6<=N:
        if dp[v]+1<dp[v+pow6]:
            dp[v+pow6]=dp[v]+1
            que.append((dp[v+pow6],v+pow6))
        pow6*=6
    pow9=1
    while v+pow9<=N:
        if dp[v]+1<dp[v+pow9]:
            dp[v+pow9]=dp[v]+1
            que.append((dp[v+pow9],v+pow9))
        pow9*=9
print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
dp=[-1]*(N+1)
dp[0]=0
que=[0]
while len(que)!=0:
    v=que[0]
    que=que[1:]
    pow6=1
    while v+pow6<=N:
        if dp[v+pow6]==-1:
            dp[v+pow6]=dp[v]+1
            que.append(v+pow6)
        pow6*=6
    pow9=1
    while v+pow9<=N:
        if dp[v+pow9]==-1:
            dp[v+pow9]=dp[v]+1
            que.append(v+pow9)
        pow9*=9
print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np 
N=int(input())
dp=np.full(N+1,10**9+7)
dp[0]=0
for i in range(N+1):
    for j in [1,6,36,216,1296,7776,46656,9,81,729,6561,59049]:
        if i+j<=N:
            dp[i+j]=min(dp[i]+1,dp[i+j]) 
print(int(dp[N]))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
cnt=0
for i in range(6):
    fi=9**i
    if n%fi==0:
        n-=fi
        cnt+=1
    else:
        for j in range(7):
            fj=6**j
            if n%fj==0:
                n-=fj
                cnt+=1
            else:
                while n!=0:
                    n-=1
                    cnt+=1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
# encoding:utf-8
import copy
import numpy as np
import random
import queue

n = int(input())

withdraws = [1]
price = 1
while True:
    price *= 6
    if price <= 10**5 and price <= n:
        withdraws.append(price)
    else:
        break

price = 1
while True:
    price *= 9
    if price <= 10**5 and price <= n:
        withdraws.append(price)
    else:
        break

money = 0
count = 0

que = queue.Queue()

que.put((0,0))
while not(que.empty()):
    money,count = que.get()
    # print(money,count)
    if money > n:
        pass
    else:
        for withdraw in withdraws:
            if money+withdraw == n:
                print(count+1)
                exit()
            else:
                next = (money+withdraw,count+1)
                que.put(next)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
list6 = [6**x for x in range(0,7) ]
list9 = [9**x for x in range(0,6) ]

def f(x):
    if x < 6:
        return x
    else:
        max6 = max(y for y in list6 if y <= x)
        max9 = max(y for y in list9 if y <= x)
        x6 = x - max6
        x9 = x - max9
        return min(f(x6)+ 1,f(x9)+ 1)

print(f(N))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

def f(x,n):
    if x == 0:
        return n
    else:
        i = 0
        j = 0
        while 6**i <= x:
            i += 1
        while 9**j <= x:
            j += 1
        n6 = n + 1
        n9 = n + 1
        x6 = x - (6**(i-1))
        x9 = x - (9**(j-1))
        return min(f(x6,n6),f(x9,n9))

print(f(N,0))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

from copy import deepcopy
from functools import lru_cache
import sys

POSS = sorted([1, 6, 36, 216, 1296, 7776, 46656, 9, 81, 729, 6561, 59049])
NMAX = 10 ** 5
# sys.setrecursionlimit(NMAX + 1)

@lru_cache(maxsize=NMAX + 1)
def dfs(n):
    assert 0 <= n <= NMAX
    res = n
    for p in reversed(POSS):
        if n - p >= 0:
            res = min(res, dfs(n - p) + 1)
    return res

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

main()

Submission status: Time Limit Exceeded

Solution code:
# ABC 099 解3 not yet
import math
def getInt(): return int(input())
def zeros(n): return [0]*n
def db(x): 
    global debug
    if debug: print(x)
debug = False
N = getInt()
a9 = [9**i for i in range(int(math.log10(N)/math.log10(9)), 0, -1)]
a6 = [6**i for i in range(int(math.log10(N)/math.log10(6)), 0, -1)]
db((a9,a6))
def genVal(n, p): # n個のリスト0からp-1のリストを生成　[0]から変化
    blist = zeros(n)
    for i in range(p**n):
        for k in range(n):
            blist[k] = i%p
            i //= p
        yield blist
count = 99999999
for n9 in genVal(len(a9),9):
    for n6 in genVal(len(a6),6):
        mon = 0
        for i in range(len(a9)):
            mon += a9[i]*n9[i]
            if mon>N: break
        for i in range(len(a6)):
            mon += a6[i]*n6[i]
            if mon>N: break
        c1 = N - mon
        if c1<0 or c1>5: continue
        else:
            c1 += sum(n9)+sum(n6)
            if c1<count: 
                count = c1
                db((n9,n6,c1))
print(count)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from math import *
import sys
sys.setrecursionlimit(1145141919)
N = int(input())

def find_n(x):
    n6 = int(floor(log(x, 6)))
    n9 = int(floor(log(x, 9)))
    return n6, n9

memo = np.ones(N + 1) * -1

def dp(n):
    if memo[n] != -1:
        return memo[n]
    if n == 0:
        return 0
    n6, n9 = find_n(n)
    n6s = np.zeros(n6 + 1)
    for i in range(0, n6 + 1):
        n6s[i] = 1 + dp(n - 6**i)
    n9s = np.zeros(n9 + 1)
    for i in range(0, n9 + 1):
        n9s[i] = 1 + dp(n - 9**i)
    dp6 = np.min(n6s)
    dp9 = np.min(n9s)
    memo[n] = min(dp6, dp9)
    return memo[n]

print(int(dp(N)))

Submission status: Time Limit Exceeded

Solution code:
import math
import sys
sys.setrecursionlimit(10000000)

N = int(input())
POW6 = [6**i for i in range(6, 0, -1)]
POW9 = [9**i for i in range(5, 0, -1)]

def rec(N, num, A):
    if N <= 5:
        num += N
        A.append(num)
        return A
    if N <= 8:
        num += N - 5
        A.append(num)
        return A
    for p6 in POW6:
        if p6 <= N:
            rec(N - p6, num+1, A)
    for p9 in POW9:
        if p9 <= N:
            rec(N - p9, num+1, A)
    return A

A = rec(N, 0, [])
print(min(A))

Submission status: Time Limit Exceeded

Solution code:

n = int(input())

ark = float("INF")

for l in range(2):  # 59049
    abc = (n - (59049*l))
    if abc < 0:
        break
    for k in range(3):  # 46656
        abc = (n - (46656 * k+59049*l))
        if abc < 0:
            break
        for j in range(6):  # 7776
            abc = (n - (776 * j + 46656 * k+59049*l))
            if abc < 0:
                break
            for h in range(4):  # 1296,6
                abc = (n - (1296 * h+ 7776 * j + 46656 * k+59049*l))
                if abc < 0:
                    break
                for g in range(6):  # 729,9
                    abc = (n - (729 * g + 1296 * h+ 7776 * j + 46656 * k+59049*l))
                    if abc < 0:
                        break
                    for f in range(4):#216,5(4)
                        abc = (n - (216 * f+ 729 * g + 1296 * h+ 7776 * j + 46656 * k+59049*l))
                        if abc < 0:
                            break
                        for e in range(4):  # 81
                            abc = (n - (81 * e + 216 * f + 729 * g + 1296 * h+ 7776 * j + 46656 * k+59049*l))
                            if abc < 0:
                                break
                            for d in range(5):  # 36
                                abc = (n - (36 * d + 81 * e + 216 * f + 729 * g + 1296 * h+ 7776 * j + 46656 * k+59049*l))
                                if abc < 0:
                                    break
                                for c in range(4):  # 9
                                    abc = (n - (9 * c + 36 * d + 81 * e + 216 * f + 729 * g + 1296 * h + 7776 * j + 46656 * k+59049*l))
                                    if abc < 0:
                                        break
                                    for b in range(3):  # 6
                                        abc = (n - (6 * b + 9 * c + 36 * d + 81 * e + 216 * f + 729 * g + 1296 * h + 7776 * j + 46656 * k+59049*l))
                                        if abc < 0:
                                            break
                                        for a in range(6):  # 1
                                            abc = (n - (1*a+6*b+9*c+36*d+81*e+216*f+729*g+1296*h+7776*j+46656*k+59049*l))
                                            if abc < 0:
                                                break
                                            if abc % 6561 == 0 and abc >= 0:
                                                i = abc//6561
                                                if ark > a+b+c+d+e+f+g+h+i+j+k+l:
                                                    ark = a+b+c+d+e+f+g+h+i+j+k+l
print(ark)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import sys
N = int(input())
l = [pow(9,(i+1)) for i in range(5)]

for i in range(7):
  l.append(pow(6,i))
ans = 0

for i in range(20):
  for j in itertools.combinations_with_replacement(l,i):
    if sum(j) == N:
      print(len(j))
      sys.exit()

Submission status: Time Limit Exceeded

Solution code:
x=int(input())
a=[]
b=0
for i in range(1,7):
    a.append(6**i)
    a.append(9**i)
c=sorted(a,reverse=True)
while x>0:
    for j in c:
        if x>=15:
            if j<=x:
                x-=j
                b+=1
                break
        elif x==14:
            b+=4
            x=0
        elif x==13:
            b+=3
            x=0
        elif x==12:
            b+=2
            x=0
        elif 0<=x<6:
            b+=x
            x-=x
print(b)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

ar = []
for a in range(6):#1
    abc = (n - (1 * a))
    if abc < 0:
        break
    for b in range(3):#6
        abc = (n - (1 * a + 6 * b))
        if abc < 0:
            break
        for c in range(4):#9
            abc = (n - (1 * a + 6 * b + 9 * c))
            if abc < 0:
                break
            for d in range(5):#36
                abc = (n - (1 * a + 6 * b + 9 * c + 36 * d))
                if abc < 0:
                    break
                for e in range(4):#81
                    abc = (n - (1 * a + 6 * b + 9 * c + 36 * d + 81 * e))
                    if abc < 0:
                        break
                    for f in range(5):#216
                        abc = (n - (1 * a + 6 * b + 9 * c + 36 * d + 81 * e + 216 * f))
                        if abc < 0:
                            break
                        for g in range(9):#729
                            abc = (n - (1 * a + 6 * b + 9 * c + 36 * d + 81 * e + 216 * f + 729 * g))
                            if abc < 0:
                                break
                            for h in range(6):#1296
                                abc = (n - (1 * a + 6 * b + 9 * c + 36 * d + 81 * e + 216 * f + 729 * g + 1296 * h))
                                if abc < 0:
                                    break
                                for j in range(6):#7776
                                    abc = (n - (1 * a + 6 * b + 9 * c + 36 * d + 81 * e + 216 * f + 729 * g + 1296 * h + 7776 * j))
                                    if abc < 0:
                                        break
                                    for k in range(3):#46656
                                        abc = (n - (1 * a + 6 * b + 9 * c + 36 * d + 81 * e + 216 * f + 729 * g + 1296 * h + 7776 * j + 46656 * k))
                                        if abc < 0:
                                            break
                                        for l in range(2):#59049
                                            abc = (n - (1*a+6*b+9*c+36*d+81*e+216*f+729*g+1296*h+7776*j+46656*k+59049*l))
                                            if abc < 0:
                                                break
                                            if abc % 6561 == 0 and abc >= 0:
                                                i = abc//6561
                                                ar.append(a+b+c+d+e+f+g+h+i+j+k+l)
print(min(ar))

Submission status: Time Limit Exceeded

Solution code:
#ABC099C
N=int(input())
#1:6 2:36 3:216 4:1296 5:7776 6:46656 7:9 8:81 9:729 10:6561 11:59049
#dv9=[59049, 6561, 729, 81, 9]
#dv6=[46656, 7776, 1926, 216, 36, 6]
#dv=[6,36,216,1296,7776,46656,9,81,729,6561,59049]
lm9=[2, 9, 9, 9, 9]
lm6=[3, 6, 6, 6, 6, 6]
#ans=[0]*11
ans=N
sums=0
for i in range(lm9[0]):
    sumsi=i*59049
    if sumsi>N:
        break
    else:
        for j in range(lm6[0]):
            sumsj=j*46656
            if sumsj+sumsi>N:
                break
            else:
                for k in range(lm6[1]):
                    sumsk=k*7776
                    if sumsk+sumsj+sumsi>N:
                        break
                    else:
                        for l in range(lm9[1]):
                            sumsl=l*6561
                            if sumsl+sumsk+sumsj+sumsi>N:
                                break
                            else:
                                for m in range(lm6[2]):
                                    sumsm=m*1296
                                    if sumsm+sumsl+sumsk+sumsj+sumsi>N:
                                        break
                                    else:
                                        for n in range(lm9[2]):
                                            sumsn=n*729
                                            if sumsn+sumsm+sumsl+sumsk+sumsj+sumsi>N:
                                                break
                                            else:
                                                for o in range(lm6[3]):
                                                    sumso=o*216
                                                    if sumso + sumsn + sumsm + sumsl + sumsk + sumsj + sumsi>N:
                                                        break
                                                    else:
                                                        for p in range(lm9[3]):
                                                            sumsp=p*81
                                                            if sumsp + sumso + sumsn + sumsm + sumsl + sumsk + sumsj + sumsi>N:
                                                                break
                                                            else:
                                                                for q in range(lm6[4]):
                                                                    sumsq=q*36
                                                                    if sumsq + sumsp + sumso + sumsn + sumsm + sumsl + sumsk + sumsj + sumsi>N:
                                                                        break
                                                                    else:
                                                                        for r in range(lm9[4]):
                                                                            sumsr=r*9
                                                                            if sumsr + sumsq + sumsp + sumso + sumsn + sumsm + sumsl + sumsk + sumsj + sumsi>N:
                                                                                break
                                                                            else:
                                                                                for s in range(lm6[5]):
                                                                                    sumss=s*6
                                                                                    sums = sumss + sumsr + sumsq + sumsp + sumso + sumsn + sumsm + sumsl + sumsk + sumsj + sumsi
                                                                                    if sums>N:
                                                                                        break
                                                                                    else:
                                                                                        ans_tmp=N-sums+i+j+k+l+m+n+o+p+q+r+s
                                                                                    if ans_tmp<ans:
                                                                                        ans=ans_tmp
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#ABC099C
N=int(input())
#1:6 2:36 3:216 4:1296 5:7776 6:46656 7:9 8:81 9:729 10:6561 11:59049
#dv=[6,36,216,1296,7776,46656,9,81,729,6561,59049]
lm=[6, 6, 6, 6, 6, 3, 9, 9, 9, 9, 2]
#ans=[0]*11
ans=0
sums=0
for i in range(lm[0]):
    for j in range(lm[1]):
        for k in range(lm[2]):
            for l in range(lm[3]):
                for m in range(lm[4]):
                    for n in range(lm[5]):
                        for o in range(lm[6]):
                            for p in range(lm[7]):
                                for q in range(lm[8]):
                                    for r in range(lm[9]):
                                        for s in range(lm[10]):
                                            sums=i*6+j*36+k*216+l*1296+m*7776+n*46656+o*9+p*81+q*729+r*6561+s*59049
                                            if N-sums>=0:
                                                ans_tmp=N-sums+i+j+k+l+m+n+o+p+q+r+s
                                                if ans_tmp<ans:
                                                    ans=ans_tmp
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# C 
import numpy as np

# n = 127
n = int(input())

max_n = 100000
memo = np.full(max_n,999999,dtype=np.int64)
memo[0] = 0

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


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

Submission status: Time Limit Exceeded

Solution code:
# C 
import numpy as np

# n = 127
n = int(input())

max_n = 100000
memo = np.full(max_n,999999,dtype=np.int64)
memo[0] = 0

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


for i in range(1,n+1):
    memo[i] = memo[i-1]+1
    for i6 in nl6:
        if(i-i6 >= 0):
            memo[i] = min(memo[i], memo[i-i6]+1)
        
    for i9 in nl9:
        if(i-i9 >= 0):
            memo[i] = min(memo[i], memo[i-i9]+1)
            
print(memo[n])

Submission status: Time Limit Exceeded

Solution code:
# C 
import numpy as np

# n = 127
n = int(input())

max_n = 100000
memo = np.full(max_n,999999,dtype=np.int64)
memo[0] = 0

nl = [1]
nl6 = nl+[6**i for i in range(1,1000) if 6**i <= 100000]
nl9 = nl+[9**i for i in range(1,1000) if 9**i <= 100000]
nl.sort(reverse=True)


for i in range(1,n+1):
    memo[i] = memo[i-1]+1
    for i6 in nl6:
        if(i-i6 >= 0):
            memo[i] = min(memo[i], memo[i-i6]+1)
        
    for i9 in nl9:
        if(i-i9 >= 0):
            memo[i] = min(memo[i], memo[i-i9]+1)
            
print(memo[n])

Submission status: Time Limit Exceeded

Solution code:
lis = [1]
cou = 1
n = int(input())
while 6 ** cou <= n:
  lis.append(6**cou)
  cou += 1
cou = 1
while 9 ** cou <= n:
  lis.append(9**cou)
  cou += 1
lis.sort(reverse = True)

now = {0}

for i in range(n):
  gone = set()
  for num in now:
    for k in range(len(lis)):
      gone.add(num + lis[k])
  if n in gone:
    print(i+1)
    exit()
  now = gone

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(101000)

N=input()

memo={}
def dp(n):
	ret=float("inf")
	if n==0: return 0
	if n<0: return float("inf")
	if n in memo: return memo[n]

	for k in range(1,8):
		t=min(dp(n-6**k)+1,dp(n-9**k)+1,dp(n-1)+1)
		ret=min(ret,t)
	
	memo[n]=ret
	return ret

#print dp(8)
#print dp(12)
#print dp(83)
#print dp(N)
dp(N)
print memo[N]

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
o=99999
for a in range(0,n+1,59049):
    if n-a>=0:
        na=n-a
        for b in range(0,na+1,46656):
            if na-b>=0:
                nb=na-b
                for c in range(0,nb+1,7776):
                    if nb-c>=0:
                        nc=nb-c
                        for d in range(0,nc+1,6561):
                            if nc-d>=0:
                                nd=nc-d
                                for e in range(0,nd+1,1296):
                                    if nd-e>=0:
                                        ne=nd-e
                                        for f in range(0,ne+1,729):
                                            if ne-f>=0:
                                                nf=ne-f
                                                for g in range(0,nf+1,216):
                                                    if nf-g>=0:
                                                        ng=nf-g
                                                        for h in range(0,ng+1,81):
                                                            if ng-h>=0:
                                                                nh=ng-h
                                                                for i in range(0,nh+1,36):
                                                                    if nh-i>=0:
                                                                        ni=nh-i
                                                                        for j in range(0,ni+1,9):
                                                                            if ni-j>=0:
                                                                                nj=ni-j
                                                                                for k in range(0,nj+1,6):
                                                                                    if nj-k>=0:
                                                                                        nk=nj-k
                                                                                        for l in range(0,nk+1,1):
                                                                                            if nk-l==0:
                                                                                                m=((a/59049)+(b/46656)+(c/7776)+(d/6561)+(e/1296)+(f/729)+(g/216)+(h/81)+(i/36)+(j/9)+(k/6)+l)
                                                                                                o=min(o,m)
print(int(o))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n=int(input())
s=np.zeros(100001,dtype='int32')
a=[1,6,9,36,81,216,729,1296,6561,7776,46656,59049]
for i in range(n+1):
    s[i]=i
for i in range(1,12):
    if a[i]<=n :
        k=a[i]
        for j in range(k,n+1):
            if s[j]>s[j-k]+1:
                s[j]=s[j-k]+1
print(s[n])

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=[]
t=[]
p=0
def f9(n,p):
    while n>=9:
        n//=9
        p+=1
        f9(n,p)
    return p
def f6(n,p):
    while n>=6:
        n//=6
        p+=1
        f6(n,p)
    return p    
s.append((n,0))
while s:
    a=s[0][0]
    b=s[0][1]
    if a<6:
        t.append(b+a)
    else:
        p=0
        s.append((a-9**f9(a,p),b+1))
        p=0
        s.append((a-6**f6(a,p),b+1))
    s.pop(0)    
print(min(t))

Submission status: Time Limit Exceeded

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

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

N = int(input())

wlevel = 0

def withdraw_amount(amount, wlevel):
    #print("withdraw_amount({}, {}) {}".format(amount, wlevel, withdraw[wlevel]))

    min_times = 100000


    # 終了条件は、引き出す額が1のとき、その額(=回数)を返す
    if wlevel == 11:
        return amount

    for i in range(0, (amount // withdraw[wlevel])+1):
        #print("i:{}".format(i))
        withdraw_times = withdraw_amount(amount-withdraw[wlevel]*i, wlevel+1)
        min_times = min(min_times, withdraw_times + i)

    #print("min_times:{}".format(min_times))
    return min_times

print(withdraw_amount(N, wlevel))