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:
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N = int(input())

dp = [N] * (N + 1)
dp[0] = 0
for i in range(N):
    dp[i + 1] = min(dp[i + 1], dp[i] + 1)
    six = 6
    nine = 9
    for p in range(20):
        if i + six <= N:
            dp[i + six] = min(dp[i + six], dp[i] + 1)
        if i + nine <= N:
            dp[i + nine] = min(dp[i + nine], dp[i] + 1)
        six *= six
        nine *= nine

print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N = int(input())

dp = [N] * (N + 1)
dp[0] = 0
for i in range(N):
    dp[i + 1] = min(dp[i + 1], dp[i] + 1)
    six = 6
    nine = 9
    for p in range(20):
        if i + six ** p <= N:
            dp[i + six ** p] = min(dp[i + six ** p], dp[i] + 1)
        if i + nine ** p <= N:
            dp[i + nine ** p] = min(dp[i + nine ** p], dp[i] + 1)

print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

import math

ans = float('inf')
def calc(x,cnt):
    if x<6:
        global ans
        ans = min(ans,x+cnt)
    else:
        c = 6**int(math.log(x,6))
        if c*6==x:c*=6
        calc(x-c,cnt+1)
        c = 9**int(math.log(x,9))
        if c*9==x:c*=9
        calc(x-c,cnt+1)

calc(n,0)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main(n):
  if n<6:
    print(n)
    exit()
  l=[6**i for i in range(7)]
  l[6:6]=[9**i for i in range(1,6)]
  l.sort()
  if n in l:
    print(1)
    exit()
  from collections import deque
  todo=deque([[1,li] for li in l[1:] if n>li])
  while len(todo)>0:
    d=todo.popleft()
    t0=d[0]
    t1=d[1]
    for li in [li for li in l if li<=n-d[1]]:
      if t1+li==n:
        print(t0+1)
        exit()
      else:
        todo.append([t0+1,t1+li])

if __name__=='__main__':
  import sys
  input = sys.stdin.readline
  n=int(input())
  main(n)

Submission status: Time Limit Exceeded

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

for i in range(5):
    s.append(9** (i + 1))
for i in range(6):
    s.append(6** (i + 1))
s.sort()

for i in range(1, N + 1):
    t_l = []
    for j in range(len(tmp[i - 1])):
        for k in range(12):
            a = tmp[i - 1][j] + s[k]
            if a <= N:
                t_l.append(a)
    tmp[i].extend(t_l)
    if N in tmp[i]:
        break
print(i)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
tmp = [[] for i in range(N + 1)]
tmp[0] = [0]
chk = []
s = [1]

for i in range(5):
    s.append(9** (i + 1))
for i in range(6):
    s.append(6** (i + 1))
s.sort()

for i in range(1, N + 1):
    t_l = []
    for j in range(len(tmp[i - 1])):
        for k in range(12):
            a = tmp[i - 1][j] + s[k]
            if a <= N and a not in chk:
                t_l.append(a)
                chk.extend(t_l)
    tmp[i].extend(t_l)
    if N in tmp[i]:
        break
print(i)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
ans = 0
tmp = [[] for i in range(N + 1)]
tmp[0] = [0]
chk = []
flag = 0
s = [1]
for i in range(5):
    s.append(9** (i + 1))
for i in range(6):
    s.append(6** (i + 1))
s.sort()

for i in range(1, N + 1):
    t_l = []
    for j in range(len(tmp[i - 1])):
        for k in range(12):
            if tmp[i - 1][j] + s[k] <= N and tmp[i - 1][j] + s[k] not in chk:
                t_l.append(tmp[i - 1][j] + s[k])
    t_l = list(set(t_l))
    tmp[i].extend(t_l)
    chk.extend(t_l)
    if N in tmp[i]:
        break
print(i)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
l = list(100 for _ in range(n+1))
l[0] = 0
for i in range(n+1):
  for j in range(i+1,n+1):
    l[j] = min(l[j],l[i]+(j-i))
#  print(l)
  for k in range(7):
    if i+6**k<=n:
      l[i+6**k] = min(l[i+6**k],l[i]+1)
 # print(l)
  for m in range(7):
    if i+9**m<=n:
      l[i+9**m] = min(l[i+9**m],l[i]+1)
  #print(l)
print(l[-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
from functools import lru_cache
def input(): return sys.stdin.readline().rstrip()

def main():
    N = int(input())
    yen = [6 ** i for i in range(1, 7)]
    yen += [9 ** i for i in range(1, 6)]
    yen = [i for i in yen if i <= N]
    yen.sort(reverse=True)

    def MIN(a, b):
        if a > b:
            return b
        else:
            return a

    @lru_cache(maxsize=None)
    def dfs(x, n, m):
        n += 1
        for y in yen:
            if n >= m:
                return n
            if y > x:
                continue
            if x - y < 6:
                return n + x - y
            m = MIN(dfs(x - y, n, m), m)
        return m

    print(dfs(N, 0, N))

if __name__ == '__main__':
    main()

Submission status: Time 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*2, es)
    print(reslut[n])
    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

def six(n):
  count = 0
  while n > 5:
    x = n
    a = 0
    while x >= 1:
      x = x / 6
      a += 1
    a -= 1
    n -= 6 ** a
    count += 1
  count += n
  return count

def nine(n):
  count = 0
  while n > 8:
    x = n
    a = 0
    while x >= 1:
      x = x / 9
      a += 1
    a -= 1
    n -= 9 ** a
    count += 1
    #print(n)
  count += n
  return count

#print(six(41), nine(41))
ans = 10 ** 7
for i in range(N + 1):
  x = six(i) + nine(N - i)
  ans = min(ans, x)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

inf=10**7
n=int(input())
coin=[6**x for x in range(10)]
coin+=[9**x for x in range(1,10)]

dp=np.zeros(n+1,dtype=np.int64)
dp+=inf
dp[0]=0

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

Submission status: Time Limit Exceeded

Solution code:
#pypyは内包表記使わない, rstrip注意
#提出前に見返すこと！
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    inf = 10**17
    #mod = 1000000007

    N = int(input())
    dp = [inf]*(N+1)
    dp[0] = 0
    money = [1, 6, 9, 36, 81, 216, 729, 6**4, 6561, 6**5, 6**6, 59049]
    while dp[N]==inf:
        for i in range(N, 0, -1):
            for j in money:
                if i<j:
                    continue
                dp[i] = min(dp[i-j]+1, dp[i])
    print(dp[N])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())

n9=9**5
n6=6**6

k9=5+1
k6=6+1
n9=9**k9
smin=n
for i9 in range(n9):
    ii9=i9
    s=0
    m=0
    astr=""
    for ii in range(1,k9+1):
        r9=ii9%9
        ii9=(ii9-r9)//9    
        s=s*9+r9
        m=m+r9
        astr=astr+str(r9)
#    print("i9",i9,"astr",astr,"s",s,"m",m)
    
    nr=n-s
    nr1=nr
#    print("nr",nr,"m",m)
    
    if nr==0:
        snra=m
#        print(nr,m)
    elif nr>0:
        snra=m
        for jj in range(k6,-1,-1):
            nra=nr1//(6**jj)
            nr1=nr1%(6**jj)
            snra=snra+nra
#        print("jj",jj,"nra",nra,"nr1",nr1)
    if smin>snra:
        smin=snra
print(smin)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
DP = [100000000] * (N+1)
DP[0] = 0
for i in range (N):
    DP[i + 1] = DP[i] + 1
    for j in range (100):
        if 6**j <= i + 1:
            DP[i + 1] = min(DP[i + 1],DP[i + 1 - 6**j] + 1)
    for j in range (100):
        if 9**j <= i + 1:
            DP[i + 1] = min(DP[i + 1],DP[i + 1 - 9**j] + 1)
print(DP[N])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

import numpy as np
def num_withdraw_dp(N):
    dp = np.full(N + 1, N, dtype='int')
    dp[0] = 0
    for n in range(1, N+1):
        dp[n] = min(dp[n], dp[n - 1] + 1)
        coin = 6
        while coin <= N:
            dp[n] = min(dp[n], dp[n - coin] + 1)
            coin *= 6
        coin = 9
        while coin <= N:
            dp[n] = min(dp[n], dp[n - coin] + 1)
            coin *= 9
    return dp[N]

print(num_withdraw_dp(N))

Submission status: Time Limit Exceeded

Solution code:
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(input()) #整数読み込み
def ifn(): return float(input()) #浮動小数点読み込み
def isn(): return input().split() #文字列読み込み
def imn(): return map(int, input().split()) #整数map取得
def fmn(): return map(float, input().split()) #浮動小数点map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, input().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD

MAX_N = 110000

memo = [-1 for _ in range(MAX_N)]
def rec(n):
    if n == 0: return 0
    if memo[n] != -1: return memo[n]

    res = n

    pow6 = 1
    while pow6 <= n:
        res = min(res, rec(n-pow6)+1)
        pow6 *= 6
    pow9 = 1
    while pow9 <= n:
        res = min(res, rec(n-pow9)+1)
        pow9 *= 9
    memo[n] = res
    return res


N = iin()
print(rec(N))

Submission status: Time Limit Exceeded

Solution code:
def fx(n):
  if n == 0:
    return 0
  if n == 1:
    return 1
  arr = []
  cnt = 0
  
  if n < 6:
    b = fx(n-1)+1
    arr.append(b)
  while n-6**cnt >= 0:
    cnt += 1
  if cnt > 1:
    
    x = n-(6**(cnt-1))
    b = fx(x)+1
    arr.append(b)

  cnt = 0
  while n-9**cnt >= 0:
    cnt += 1
  if cnt > 1:
    x = n-(9**(cnt-1))
    b = fx(x)+1
    arr.append(b)
  
  return min(arr)
  
N = int(input())
print(fx(N))

Submission status: Time Limit Exceeded

Solution code:
import os
import sys
from functools import lru_cache

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353


@lru_cache(maxsize=None)
def solve(n):
    if n == 0:
        return 0
    if n < 0:
        return INF
    d = 0
    ret = INF
    while 6 ** d <= n:
        if n - 6 ** d >= 0:
            ret = min(ret, solve(n - 6 ** d) + 1)
        if n - 9 ** d >= 0:
            ret = min(ret, solve(n - 9 ** d) + 1)
        d += 1
    return ret


n = int(sys.stdin.buffer.readline())
ans = solve(n)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
MAXN = 110000

f_inf = float('inf')
dp = [f_inf] * (MAXN+n)

dp[0] = 0

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

    for k in range(1, n+1):
        if i >= power9:
            dp[i] = min(dp[i], dp[i-power9]+1)
            power9 *= 9

print(dp[n])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
MAXN = 110000

f_inf = float('inf')
dp = [f_inf] * (MAXN+n)

dp[0] = 0

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

    for k in range(1, n+1):
        if i >= power9:
            dp[i] = min(dp[i], dp[i-power9]+1)
            power9 *= 9

print(dp[n])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
List9 = [9 ** i for i in range(6) if 9 ** i <= N]
List6 = [6 ** i for i in range(6) if 6 ** i <= N]

def recur(n,con):
  if n == 0:
    return con


  else:
    max9 = max([i for i in List9 if i <= n])
    max6 = max([i for i in List6 if i <= n])
    
    return min(recur(n - max9,con + 1),recur(n - max6,con + 1))
    
print(recur(N,0))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = int(input())
dp = [float("inf")]*(N + 1)
dp[0] = 0
pull_list_9 = [9**i for i in range(1, 6)]
pull_list_6 = [6**i for i in range(1, 7)]
pull_list = np.array(pull_list_9 + pull_list_6 + [1])
p_s = sorted(pull_list)
for i in range(1, N + 1):
  for j in p_s:
    if i - j < 0:
      break
    dp[i] = min(dp[i], dp[i-j] + 1)
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import numpy as np

def solve(N: int):
    #9 ** 5 == 59049 < 10 ** 5
    #6 ** 6 == 46656 < 10 ** 5
    dp = [float("inf")]*(N + 1)
    dp[0] = 0
    pull_list_9 = [9**i for i in range(1, 6)]
    pull_list_6 = [6**i for i in range(1, 7)]
    pull_list = np.array(pull_list_9 + pull_list_6 + [1])
    p_s = sorted(pull_list)
    for i in range(1, N + 1):
        for j in p_s:
            if i - j < 0:
                break
            dp[i] = min(dp[i], dp[i-j] + 1)
    print(dp[-1])

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
d = tuple([1] + [6**i for i in range(1, 7)] + [9**i for i in range(1, 6)])
M = 10**6+1
B = [float("inf")]*M
B[0] = 0
for i in range(M):
  for j in d:
    if i+j < M:
      B[i+j] = min(B[i+j], B[i]+1)
n = int(input())
print(B[n])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
L6 = []
L9 = []
for i in range(1, 100):
  num = 6 ** i
  if num <= n:
    L6.append(num)
  else:
    break
for i in range(1, 100):
  num = 9 ** i
  if num <= n:
    L9.append(num)
  else:
    break

from itertools import product
iter6 = product(range(0, 6), repeat=len(L6))
Res6 = []
for iter in iter6:
  total = 0
  counter = 0
  for num, l in zip(iter, L6):
    total += num * l
    counter += num
  if n - total >= 0:
    Res6.append([n - total, counter])
#print(Res6)

iter9 = product(range(0, 9), repeat=len(L9))
Res9 = []
for iter in iter9:
  total = 0
  counter = 0
  for num, l in zip(iter, L9):
    total += num * l
    counter += num
  if n - total >= 0:
    Res9.append([total, counter])

#print(list(product(Res6, Res9)))
Res9.sort(key = lambda x:x[0])

min_x = n
for cand6 in Res6:
  for cand9 in Res9:
    if cand6[0] - cand9[0] >= 0:
      x = cand6[0] - cand9[0] + cand6[1] + cand9[1]
      min_x = min(min_x, x)
    else:
      break
print(min_x)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
L6 = []
L9 = []
for i in range(1, 100):
  num = 6 ** i
  if num <= n:
    L6.append(num)
  else:
    break
for i in range(1, 100):
  num = 9 ** i
  if num <= n:
    L9.append(num)
  else:
    break

from itertools import product
iter6 = product(range(0, 6), repeat=len(L6))
Res6 = []
for iter in iter6:
  total = 0
  counter = 0
  for num, l in zip(iter, L6):
    total += num * l
    counter += num
  if n - total >= 0:
    Res6.append([n - total, counter])
#print(Res6)

iter9 = product(range(0, 9), repeat=len(L9))
Res9 = []
for iter in iter9:
  total = 0
  counter = 0
  for num, l in zip(iter, L9):
    total += num * l
    counter += num
  Res9.append([total, counter])

#print(list(product(Res6, Res9)))

min_x = n
for pairs in product(Res6, Res9):
  if pairs[0][0] - pairs[1][0] >= 0:
    x = pairs[0][0] - pairs[1][0] + pairs[0][1] + pairs[1][1]
    min_x = min(min_x, x)
print(min_x)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
import math 
m = math.floor(math.log(N,6)) #max 8
n = math.floor(math.log(N,9)) #max 7
s = [1]
for i in range(1,m+1):
    s.append(6**i)
for j in range(1,n+1):
    s.append(9**j)
s.sort()
l = len(s)
dp = [ i for i in range(N+1)]
for i in range(1,N+1):
    for j in range(1,6):
        m = 9**j
        
        K = min(i//m,8)
        for k in range(K+1):
            dp[i] = min(dp[i],dp[i-m*k]+k)
    for j in range(1,7):
        m = 6**j
        
        K = min(i//m,5)
        for k in range(K+1):
            dp[i] = min(dp[i],dp[i-m*k]+k)
print(dp[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]
        m = min(six_nine(n - six) , six_nine(n - nine))
        return 1 + m

print(six_nine(n))

Submission status: Time Limit Exceeded

Solution code:
n= int(input())
ninesix = [9**i for i in range(1,6) if 9**i <= n]+[6**i for i in range(1,7) if 6**i <= n]
ninesix.sort(reverse=True)

def coin(ns,max_res):
  if not ns:
    return max_res
  remainder = max_res//ns[0]
  if remainder > 0:
    count = 0
    c = 10000
    for i in range(1,remainder+1):
      nnss = ns[1:]
      c = min(coin(nnss,max_res-ns[0]*i)+i,c)
    count += c
    return count
  else:
    nnss = ns[1:]
    return coin(nnss,max_res)
  return count
   
print(coin(ninesix,n))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
li=[1,6,9,36,81,216,729,1296,6561,7776,46656,59049]
dp=[[10**6 for i in range(N+1)] for j in range(12)]

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

#dp[i][j]:=i番目(0--)までを使ってjを取り出す時の最小回数
for i in range(1,12):
  for j in range(N+1):
    for a in range((N-j)//li[i]+1):
      dp[i][j+li[i]*a]=min(dp[i][j+li[i]*a],min(dp[i-1][j+li[i]*a],dp[i-1][j]+a))

print(dp[11][N])

Submission status: Time Limit Exceeded

Solution code:
s=input()
a=int(s)
list=[]
list.append(1)
list.append(6)
list.append(9)
list.append(36)
list.append(81)
list.append(216)
list.append(729)
list.append(1296)
list.append(6561)
list.append(7776)
list.append(59049)
list.append(46656)
pp=[50 for l in range(50)]
def money(x,y):
  for i in range(12):
    b=x//list[i]
    if b==0:
      continue
    if i%2==1:
      if 0<b<6:
        if x%list[i]==0:
          pp[y+b]=y+b
        else:
          money(x-list[i],y+1)
    elif i%2==0:
      if i!=0:
        if 0<b<9:
          if x%list[i]==0:
            pp[y+b]=y+b
          else:
            money(x-list[i],y+1)
      else:
        if 0<b<6:
          pp[y+b]=y+b
money(a,0)
print(min(pp))

Submission status: Time Limit Exceeded

Solution code:
s=input()
a=int(s)
list=[]
list.append(1)
list.append(6)
list.append(9)
list.append(36)
list.append(81)
list.append(216)
list.append(729)
list.append(1296)
list.append(6561)
list.append(7776)
list.append(59049)
list.append(46656)
pp=[]
def money(x,y):
  for i in range(12):
    b=x//list[i]
    if b==0:
      continue
    if i%2==1:
      if 0<b<6:
        if x%list[i]==0:
          pp.append(y+b)
        else:
          money(x-list[i],y+1)
    elif i%2==0 and i!=0:
      if 0<b<9:
        if x%list[i]==0:
          pp.append(y+b)
        else:
          money(x-list[i],y+1)
    else:
      if 0<b<6:
        pp.append(y+b)
money(a,0)
print(min(pp))

Submission status: Time Limit Exceeded

Solution code:
s=input()
a=int(s)
list=[]
list.append(1)
list.append(6)
list.append(9)
list.append(36)
list.append(81)
list.append(216)
list.append(729)
list.append(1296)
list.append(6561)
list.append(7776)
list.append(59049)
list.append(46656)
pp=[]
def money(x,y):
  for i in range(12):
    b=x//list[i]
    if x//list[i]==0:
      continue
    if i%2==1 and 0<b<6:
      if x%list[i]==0:
        pp.append(y+b)
      else:
        money(x-list[i],y+1)
    elif i%2==0 and i!=0 and 0<b<9:
      if x%list[i]==0:
        pp.append(y+b)
      else:
        money(x-list[i],y+1)
    else:
      if 0<b<6:
        pp.append(y+b)
money(a,0)
print(min(pp))

Submission status: Time Limit Exceeded

Solution code:
s=input()
a=int(s)
list=[]
list.append(1)
list.append(6)
list.append(9)
list.append(36)
list.append(81)
list.append(216)
list.append(729)
list.append(1296)
list.append(6561)
list.append(7776)
list.append(59049)
list.append(46656)
pp=[]
def money(x,y):
  for i in range(12):
    if i%2==1:
      if 0<x//list[i]<6:
        if x%list[i]==0:
          pp.append(y+x//list[i])
        else:
          money(x-list[i],y+1)
    elif i%2==0 and i!=0:
      if 0<x//list[i]<9:
        if x%list[i]==0:
          pp.append(y+x//list[i])
        else:
          money(x-list[i],y+1)
    elif i==0:
      if 0<x//list[i]<6:
        pp.append(y+x//list[i])
money(a,0)
print(min(pp))

Submission status: Time Limit Exceeded

Solution code:
lists=[]
n=int(input())
nums=0
while nums<=n+1:
    
    
    if nums<6:
        lists.append(nums)
        nums=+1
    elif nums==6 or nums==36 or nums==216 or nums==1296 or nums==7726 or nums==46656:
        lists.append(1)
        nums+=1
    elif nums==9 or nums==81 or nums==729 or nums==6561 or nums==59049:
        lists.append(1)
        nums+=1
    else:
        order6=0
        order9=0
        for k in range(6):
            if 6**(k+1)< nums <6**(k+2):
                order6=k+1
                # nums は6のκ＋1乗までならば考慮に入れても良い
                break
                
            else:
                continue
                
        for j in range(5):
            if 9**(j+1) <nums< 9**(j+2):
                order9=j+1
                #numsは9のｊ＋1乗までならば考慮に入れてもいい
                break
            else:
                continue
                
        add=min(min(lists[n-6**(k)] for k in range(0,order6+1)),min(lists[n-9**(j)] for j in range(0,order9+1)))
        lists.append(add)
        nums+=1
print(lists)

Submission status: Time Limit Exceeded

Solution code:
lists=[0 for j in range(1000)]
n=int(input())
nums=0
while nums!=n+1:
    
    
    if nums<6:
        lists[nums]==nums
        nums=+1
    elif nums==6 or nums==36 or nums==216 or nums==1296 or nums==7726 or nums==46656:
        lists[nums]==1
        nums+=1
    elif nums==9 or nums==81 or nums==729 or nums==6561 or nums==59049:
        lists[nums]==1
        nums+=1
    else:
        order6=0
        order9=0
        for k in range(6):
            if 6**(k+1)< nums <6**(k+2):
                order6=k+1
                # nums は6のκ＋1乗までならば考慮に入れても良い
                
                break
            else:
                continue
        for j in range(5):
            if 9**(j+1) <nums< 9**(j+2):
                order9=j+1
                #numsは9のｊ＋1乗までならば考慮に入れてもいい
                
                break
            else:
                continue
        lists[nums]=min(min(lists[nums-6**(k)] for k in range(0,order6+1)),min(lists[nums-9**(j)] for j in range(0,order9+1)))
        nums+=1
        
print(lists[n])

Submission status: Time Limit Exceeded

Solution code:
def jyou(n, maxNum):
    i = 1
    result = 0

    if n == 1:
        return 1

    while True:
        val = n ** i
        if val > maxNum:
            break

        i += 1
        result = val

    return result


N = int(input())
dp = [[0 for _ in range(3)] for _ in range(10000000)]

nums = [9,6,1]

index = 0
isMatch = False
while True:
    for i,e in enumerate(nums):
        for k in range(3):
            maxNum = N - dp[index][k] 
            result = jyou(e, maxNum)
            nextVal = dp[index][k] + result

            dp[index + 1][i] = max(dp[index + 1][i], nextVal) 

            if nextVal == N:
                isMatch = True
                break
        if isMatch:
            break

    if isMatch:
        break
    index += 1
        
print(index + 1)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
 
arr6 = []
for i in range(10):
    arr6.append(6**i)

arr9 = []
for i in range(10):
    arr9.append(9**i)

ans = float("inf")
for i in range(n+1):
    count = 0
    tmp = i
    while tmp > 0:
        t = 0
        while arr6[t] <= tmp:
            t+=1

        tmp -= arr6[t-1]
        count += 1

    tmp = n-i
    while tmp > 0:
        t = 0
        while arr9[t] <= tmp:
            t += 1
        tmp -= arr9[t-1]
        count += 1

    ans = min(ans,count)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy  as np

N = int(input())

# log_6 10^5 < 7
# log_9 10^5 < 6
# 15 = 1 + 6 + 5
memo = np.zeros((15, N + 1))
memo[:, :] = N * 2
memo[0][0] = 0

values = []

i = 1
while i <= N:
    values.append(i)
    i *= 6
i = 9
while i <= N:
    values.append(i)
    i *= 9

for i in range(len(values)):
    v = values[i]
    for w in range(N+1):
        if v > w:
            memo[i + 1][w] = memo[i][w]
        else:
            memo[i + 1][w] = min(memo[i][w], memo[i+1][w - v] + 1)
print(int(memo[len(values)][N]))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

d_list = [1]

a = 1
while True:
  if 6**a <= N:
    d_list.append(6**a)
    a += 1
  else:
    break
a = 1
while True:
  if 9**a <= N:
    d_list.append(9**a)
    a += 1
  else:
    break
d_list.sort(key=lambda x:-x)

rest = N
cnt = 0
while True:
  if rest < 6:
    cnt = rest
    print(cnt)
  else:
    for num in d_list:
      if rest >= num:
        cnt += 1
        rest -= num
        break

Submission status: Time Limit Exceeded

Solution code:
# 引き出したいお金の額を入力する
N = int(input())

# 整数aの累乗のうち、整数N以下かつ最も大きいものを返す関数を定義
def func(N, a):
    index = 0
    while True:
        if a ** (index + 1) <= N:
            index += 1
        else:
            break
    return a ** index

# 引き出し回数を再帰的に求める関数を定義
def search_times_re(N):
    times = 0
    if N < 6:
        times = N
        return times
    elif N < 9:
        times = 1 + (N - 6)
        return times
    else:
        N1 = search_times_re(N - func(N, 6))
        N2 = search_times_re(N - func(N, 9))
        if N1 < N2:
            return 1 + N1
        else:
            return 1 + N2

print(search_times_re(N))

Submission status: Time Limit Exceeded

Solution code:
def rec(n):
        if n == 0:
                return 0
        if memo[n] != -1:
                return memo[n]
        res = n
        pow6 = [6**x for x in range(0,n+1) if 6**x <= n]
        pow9 = [9**x for x in range(0,n+1) if 9**x <= n]
        for i in pow6:
                res = min(res,rec(n-i)+1)
        for i in pow9:
                res = min(res,rec(n-i)+1)
        memo[n] = res
        return res



n = int(input())
memo = [-1 for i in range(110000)]
print(rec(n))

Submission status: Time Limit Exceeded

Solution code:
from itertools import*
from math import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

memo = [-1]*(110000)
def rec(n):
    if n==0:
        return 0
    if memo[n] != -1:
        return memo[n]
    res = n
    pow6,pow9 = 1,1
    while pow6 <=n:
        res = min(res,rec(n-pow6)+1)
        pow6 *= 6
    while pow9 <= n:
        res = min(res,rec(n-pow9)+1)
        pow9 *= 9
    memo[n] = res
    return memo[n]

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

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
N = int(stdin.readline().rstrip())
six_pows = [6**i for i in range(10)]
nine_pows = [9**i for i in range(10)]

ans = float("inf")

for i in range(N+1):
    count = 0
    tmp = i
    while tmp > 0:
        j = 0
        while six_pows[j] <= tmp:
            j += 1
        tmp -= six_pows[j-1]
        count += 1 

    tmp = N - i
    while tmp > 0:
        j = 0
        while nine_pows[j] <= tmp:
            j += 1
        tmp -= nine_pows[j-1]
        count += 1
    
    ans = min(ans, count)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
## TLEなのはわかっておる...

import numpy as np
from collections import deque

N = int(input())

# 6^6 < 1e5 < 6^7
# 9^5 < 1e5 < 9^6
# に注目すると大きい金額から引き出してみる全探索で良さそう


drawable = [6, 6**2, 6**3, 6**4, 6**5, 6**6, 9, 9**2, 9**3, 9**4, 9**5, 9**6]
drawable = sorted(drawable, reverse=True)
solver = []

def main():
    dq = deque()
    dq.append((N,0))
    while dq:
        rest, cnt = dq.popleft()
        for draw in drawable:
          rest_afterdraw = rest - draw
          if rest_afterdraw < 0:
            continue
          else:
            if rest_afterdraw < 6:
              solver.append(cnt + rest_afterdraw + 1) 
            else:
              dq.append((rest_afterdraw,cnt+1))

if N < 6:
  print(N)
  exit()
              
main()
print(min(solver))