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: Runtime Error

Solution code:
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <cmath>
#include <iomanip>
#include <bitset>
#include <string>
#include <stdlib.h>
using namespace std;
//cout <<  << endl;
typedef long long int ll;
typedef long double ld;

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

#define MAX_N 1000
#define MAX_M 100

const long long INF = 1LL << 60;

//境界値に注意！！！

// DP テーブル
ll dp[100010];

int main (){
    ll N;
    cin >> N;
    ll res=N;
    for(ll i=0;i<=N;i++) {
        ll cc =0;
        ll t=i;
        while(t>0){
            cc+=t%6;
            t/=6;
        }
        t=N-i;
        while(t>0){
            cc+=t%9;
            t/=9;
        }
        if(res>cc)res=cc;
    }
    cout << res<< endl;
}

Submission status: Runtime Error

Solution code:
def resolve():
    N=int(input())
    print(f(N))

memo = [-1]*110000

def f(n):
    if n==0: return 0
    
    global memo
    if memo[n]!=-1:
        return memo[n]
    
    minc=n
    minc=min(minc,f(n-1)+1)
    i=1
    while 6**i<=n:
        j=6**i
        minc=min(minc,f(n-j)+1)
        i+=1
    
    i=1
    while 9**i<=n:
        j=9**i
        minc=min(minc,f(n-j)+1)
        i+=1

    memo[n]=minc
    return minc

resolve()

Submission status: Runtime Error

Solution code:
n=int(input())
dp=list(range(100000))
for i in range(n+1):
    pow6=1
    while pow6<=i:
        dp[i]=min(dp[i],dp[i-pow6]+1)
        pow6 *=6
    pow9=1
    while pow9<=i:
        dp[i]=min(dp[i],dp[i-pow9]+1)
        pow9 *=9    
print(dp[n])

Submission status: Runtime Error

Solution code:
n = int(input())
memo = [-1] * (n+1)
import sys
sys.setrecursionlimit(10000)
def f(n):
    if n == 0:
        return 0
    if memo[n] != -1:
        return memo[n]
    res = n
    pow6 = 1
    pow9 = 1
    res = min(res, f(n - 1) + 1)
    while pow6*6 <= n:
        pow6 *= 6
        res = min(res, f(n - pow6) + 1)
        
    while pow9*9 <= n:
        pow9 *= 9
        res = min(res, f(n - pow9) + 1)
        
    memo[n] = res
    return res
print(f(n))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
from typing import List, Dict


def get_all_values(N: int, v: int) -> List[int]:
    all_values = []

    current = v
    while current < N:
        all_values.append(current)
        current *= v

    return all_values


def get_min_number(memo: Dict[int, int], all_values: List[int], N: int) -> int:
    if N in memo:
        return memo[N]

    if N in all_values:
        return 1
    elif N < 6:
        return N
    else:
        min_number: int = min(
            [get_min_number(memo, all_values, N - v) + 1 for v in all_values if N - v >= 0]
        )
        memo[N] = min_number
        return min_number


def solve(N: int) -> int:
    # Get all values and sort in descent order
    all_values: List[int] = [1] + get_all_values(N, 6) + get_all_values(N, 9)
    sorted_all_values: List[int] = list(reversed(sorted(all_values)))

    # Recursively get minimum number
    memo: Dict[int, int] = {}
    ans = get_min_number(memo, sorted_all_values, N)

    return ans


def main():
    # Input
    N = int(input())

    # Solve
    ans = solve(N)

    # Answer
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(100000)

N = int(input())

memo = [None for _ in range(N + 1)]


def f(n):
    if n == 0:
        return 0
    if memo[n] is not None:
        return memo[n]
    ans = n
    pow = 1
    while pow <= n:
        ans = min(ans, f(n - pow) + 1)
        pow *= 6
    pow = 1
    while pow <= n:
        ans = min(ans, f(n - pow) + 1)
        pow *= 9
    memo[n] = ans
    return ans


print(f(N))

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(60000)

N = int(input())

memo = [None for _ in range(N + 1)]


def f(n):
    if n == 0:
        return 0
    if memo[n] is not None:
        return memo[n]
    ans = n
    pow = 1
    while pow <= n:
        ans = min(ans, f(n - pow) + 1)
        pow *= 6
    pow = 1
    while pow <= n:
        ans = min(ans, f(n - pow) + 1)
        pow *= 9
    memo[n] = ans
    return ans


print(f(N))

Submission status: Runtime Error

Solution code:
n = int(input())
dp = [100000] * 100010
dp[0] = 0
pow6 = [6**i for i in range(10) if 6**i <= n]
pow9 = [9**i for i in range(10) if 9**i <= n]

for i in range(n):
    for p6 in pow6:
        dp[i+p6] = min(dp[i+p6],dp[i]+1)
    for p9 in pow9:
        dp[i+p9] = min(dp[i+p9],dp[i]+1)
print(dp[n])

Submission status: Runtime Error

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: Runtime Error

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

# 整数aの累乗のうち、整数N以下かつ最も大きいものを返す関数を定義
def func(N, a):
    index = int(log(N) / log(a))
    return a ** index

# 引き出し回数を再帰的に求める関数を定義
def search_times_re(N):
    times = 0
    if N < 6:
        times = N
        return times
    elif N < 9:
        times = 1 + (N - 6)
    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: Runtime Error

Solution code:
N=int(input())
dp=[10**7]*110000
dp[0]=0

pow6=[6**j for j in range(10) if 6**j <= N]
pow9=[9**j for j in range(10) if 9**j <= N]

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

    for p9 in pow9:
        dp[i+p9]=min(dp[i+p9], dp[i]+1)

print(dp[N])

Submission status: Runtime Error

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)

N = int(input())
dp=[inf]*(110000)
for i in range(110000):
    dp[i] = N 
dp[0]=0
for n in range(N):
    pow6,pow9 = 1,1
    while pow6<=N:
        dp[n+pow6] = min(dp[n+pow6],dp[n]+1)
        pow6 *= 6
    while pow9 <=N:
        dp[n+pow9] = min(dp[n+pow9],dp[n]+1)
        pow9 *= 9
print(dp[N])

Submission status: Runtime Error

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化再帰
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))
"""
"""
#もらうDP
N = int(input())
dp=[inf]*110000
dp[0] = 0
for n in range(1,N+1):
    pow6,pow9 = 1,1
    while pow6<=n:
        dp[n] = min(dp[n],dp[n-pow6]+1)
        pow6 *= 6
    while pow9 <= n:
        dp[n] = min(dp[n],dp[n-pow9]+1)
        pow9 *= 9
print(dp[N])
"""
#配るDP
N = int(input())
dp=[inf]*(110000)
for i in range(110000):
    dp[i] = N 
dp[0]=0
for n in range(N):
    pow6,pow9 = 1,1
    while pow6<=N:
        dp[n+pow6] = min(dp[n+pow6],dp[n]+1)
        pow6 *= 6
    while pow9 <=N:
        dp[n+pow9] = min(dp[n+pow9],dp[n]+1)
        pow9 *= 9
print(dp[N])

Submission status: Runtime Error

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化再帰
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))
"""
"""
#もらうDP
N = int(input())
dp=[inf]*110000
dp[0] = 0
for n in range(1,N+1):
    pow6,pow9 = 1,1
    while pow6<=n:
        dp[n] = min(dp[n],dp[n-pow6]+1)
        pow6 *= 6
    while pow9 <= n:
        dp[n] = min(dp[n],dp[n-pow9]+1)
        pow9 *= 9
print(dp[N])
"""
#配るDP
N = int(input())
dp=[inf]*(110000)
dp[0]=0
for n in range(N):
    pow6,pow9 = 1,1
    while pow6<=N:
        dp[n+pow6] = min(dp[n+pow6],dp[n]+1)
        pow6 *= 6
    while pow9 <=N:
        dp[n+pow9] = min(dp[n+pow9],dp[n]+1)
        pow9 *= 9
print(dp[N])

Submission status: Runtime Error

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化再帰
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))
"""
"""
#もらうDP
N = int(input())
dp=[inf]*110000
dp[0] = 0
for n in range(1,N+1):
    pow6,pow9 = 1,1
    while pow6<=n:
        dp[n] = min(dp[n],dp[n-pow6]+1)
        pow6 *= 6
    while pow9 <= n:
        dp[n] = min(dp[n],dp[n-pow9]+1)
        pow9 *= 9
print(dp[N])
"""
#配るDP
N = int(input())
dp=[inf]*(110000)
dp[0]=0
for n in range(N):
    pow6,pow9 = 1,1
    while pow6<=n:
        dp[n+po6] = min(dp[n+pow6],dp[n]+1)
        pow6 *= 6
    while pow9 <=n:
        dp[n+pow9] = min(dp[n+pow9],dp[n]+1)
        pow9 *= 9
print(dp[N])

Submission status: Runtime Error

Solution code:
N = int(input())
memo = [-1] * 200000

def search(i): 
    if i == 0:
        return 0
    if memo[i] != -1:
        return memo[i]
    
    tmp = i
    cnt = 0
    while True: 
        n = 6 ** cnt
        if n > i:
            break       
        tmp = min(tmp, search(i-n)+1)
        cnt += 1
    cnt = 0
    while True:
        n = 9 ** cnt
        if n > i:
            break       
        tmp = min(tmp, search(i-n)+1)
        cnt += 1
    
    memo[i] = tmp
    return tmp

print(search(N))

Submission status: Runtime Error

Solution code:
N = int(input())
memo = [-1] * 100000

def search(i): 
    if i == 0:
        return 0
    if memo[i] != -1:
        return memo[i]
    
    tmp = i
    cnt = 0
    while True: 
        n = 6 ** cnt
        if n > i:
            break       
        tmp = min(tmp, search(i-n)+1)
        cnt += 1
    cnt = 0
    while True:
        n = 9 ** cnt
        if n > i:
            break       
        tmp = min(tmp, search(i-n)+1)
        cnt += 1
    
    memo[i] = tmp
    return tmp

print(search(N))

Submission status: Runtime Error

Solution code:
import math
from functools import lru_cache

MOD = 1000000007
N = 100001

fibo = [1, 1] + [0] * N
for i in range(2, N):
    fibo[i] = (fibo[i-1] + fibo[i-2]) % MOD


n, m = list(map(int, input().split(" ")))
a_list = [int(input()) for _ in range(m)]
ngs = [i in a_list for i in range(n)]
ngs.append(False)
for i in range(n):
    if ngs[i] and ngs[i + 1]:
        print(0)
        exit()
cnts = []
cnt = 0

for ng in ngs:
    if ng:
        cnts.append(cnt)
        cnt = 0
        continue
    cnt += 1
cnts.append(cnt)
ans = 1
for c in cnts:
    if c != 0:
        ans *= fibo[c - 1]
# print(ngs)
# print(cnts)
print(ans % MOD)

Submission status: Runtime Error

Solution code:
import sys


sys.setrecursionlimit(100000)


MAX_N = 100001

memo = [-1] * MAX_N


def f(n):
    # 残り金額が0なら引き出す必要がないので0(再帰の終端条件)
    if n == 0:
        return 0
    # すでに探索済みならメモを参照する
    if memo[n] != -1:
        return memo[n]

    res = sys.maxsize

    pow9 = 1
    while pow9 <= N:
        if n - pow9 < 0:
            break
        # print(n)
        # print(pow9)
        res = min(res, f(n-pow9)+1)
        pow9 *= 9

    pow6 = 1
    while pow6 <= N:
        if n - pow6 < 0:
            break
        res = min(res, f(n-pow6)+1)
        pow6 *= 6

    # メモ
    memo[n] = res

    return res


if __name__ == '__main__':
    N = int(input())

    print(f(N))

Submission status: Runtime Error

Solution code:
import sys


sys.setrecursionlimit(1000000)


MAX_N = 100000

memo = [-1] * MAX_N


def f(n):
    # 残り金額が0なら引き出す必要がないので0(再帰の終端条件)
    if n == 0:
        return 0
    # すでに探索済みならメモを参照する
    if memo[n] != -1:
        return memo[n]

    res = sys.maxsize

    pow9 = 1
    while pow9 <= N:
        if n - pow9 < 0:
            break
        res = min(res, f(n-pow9)+1)
        pow9 *= 9


    pow6 = 1
    while pow6 <= N:
        if n - pow6 < 0:
            break
        res = min(res, f(n-pow6)+1)
        pow6 *= 6

    # メモ
    memo[n] = res

    return res


if __name__ == '__main__':
    N = int(input())

    print(f(N))

Submission status: Runtime Error

Solution code:
import sys


sys.setrecursionlimit(100000)


MAX_N = 100000

memo = [-1] * MAX_N


def f(n):
    # 残り金額が0なら引き出す必要がないので0(再帰の終端条件)
    if n == 0:
        return 0
    # すでに探索済みならメモを参照する
    if memo[n] != -1:
        return memo[n]

    res = sys.maxsize

    pow9 = 1
    while pow9 <= N:
        if n - pow9 < 0:
            break
        # print(n)
        # print(pow9)
        res = min(res, f(n-pow9)+1)
        pow9 *= 9

    pow6 = 1
    while pow6 <= N:
        if n - pow6 < 0:
            break
        res = min(res, f(n-pow6)+1)
        pow6 *= 6

    # メモ
    memo[n] = res

    return res


if __name__ == '__main__':
    N = int(input())

    print(f(N))

Submission status: Runtime Error

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

from functools import lru_cache


def solve(N: int):
    print(dp(N))
    return


@lru_cache(None)
def dp(n):
    coins = [1, 6, 9, 36, 81, 216, 729, 1296, 6561, 7776, 46656, 59049]
    if n in coins:
        return 1
    if n == 0:
        return 0
    if n < 0:
        return 1000000
    cs = sorted([c for c in coins if c < n])
    return min([1 + dp(n - c) for c in cs[len(cs) // 2 :]])


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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: Runtime Error

Solution code:
N=int(input())
def cou(n,x):
    i=0
    while(n>0):
        i+=n%x
        n//=x
    return i
ans=N
for i in range(N+1):
    ans=min(ans,cou(j,6)+cou(N-j,9))
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
ans = n
l9 = [9**i for i in range(6,0,-1)]
l6 = [6**i for i in range(7,-1,-1)]
for i in range(n//9+1):
  x9 = i*9
  x61= n-x9
  csum = 0
  for x in l9:
    csum += x9//x
    x9 %= x
  for x in x61:
    csum += x61//x
    x61 %= x
  if ans > csum:
    ans = csum
print(ans)

Submission status: Runtime Error

Solution code:
def log(x, y):
    i = 0
    while(y ** i < x):
        i += 1
    return i - 1

N = int(input())
if N < 6:
    ans = N
else:
    a = log(N, 6)
    b = log(N, 9)
    print(a)
    print(b)
    m = [6**i for i in range(1, a + 1)] + [9**j for j in range(1, b + 1)]
    m.sort(reverse=True)
    nn = N
    i = 0
    ans = 0
    while(True):
        print(nn, m[i], nn // m[i])
        ans += nn // m[i]
        nn = nn % m[i]
        i += 1
        if i == len(m):
            ans += nn
            break
print(ans)

Submission status: Runtime Error

Solution code:
#反例　459 = 216 * 1 + 81 * 3
N = int(input())

count = 0

flag = True
a = N
while flag:
    if a//6 != 0:
        count += 1
        a = a//6
    else:
        flag = not flag

lst = []
for i in range(count+1):
    if (6 ** i)<= N:
        lst += [6 ** i]
        if   (9 ** i)<=N:
            lst += [9 ** i]

lst.sort(reverse = True)
#print (lst)

def hikidashi(j, n): #j番目より小さい数でnまで引き出すときの最小
    if j == len(lst):
        return n #残りをすべて1で埋める場合
    elif lst[j] > n: #引き出したい数 > 残額の時
        return hikidashi(j+1, n)
    else:
        a = hikidashi(j+1, n) #使わずに次の番目に行く
        b = hikidashi(j, n-lst[j]) + 1 #一つ使う
        return min (a, b)

print (hikidashi(0, N))

Submission status: Runtime Error

Solution code:
%%timeit
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: Runtime Error

Solution code:
N = int(input())
count = 0
i = 1
while True:
    i = 1
    j = 1
    while True:
        k = N - (9**i)
        if(k < 0):
            N = t
            if(i !=1):
                count+=1
            break;
        t = k
        i +=1
    while True:
        l = N - (6**j)
        if(l < 0):
            N = t
            if(j !=1):
                count+=1
            break;
        t = l
        j +=1
    if(N < 6):break
if (N != 0):
    count+=N
print(count)

Submission status: Runtime Error

Solution code:
N = int(input())

l1 = 2 ** 30
p6 = [1] * 6
p9 = [1] * 5
for i in range(1,7):
    p6[i] = p6[i-1] * 6
    if i < 6 : p9[i] = p9[i-1] * 9

dp = [l1] * (N+1)
dp[0] = 0

for i in range(1,N+1):
    for j in p6:
        if j>i: break
        dp[i] = min(dp[i],dp[i-j]+1)
        
    for j in p9:
        if j>i: break
        dp[i] = min(dp[i],dp[i-j]+1)
        
print(dp[N])

Submission status: Runtime Error

Solution code:
n=int(input())
ans=1000000000
for i in range(0,n+1,6):
  j=n-i
  while j:
    a=j%9
    j//=9
  while i:
    a+=i%6
    i//=6
  ans=min(a,ans)
prgnt(ans)

Submission status: Runtime Error

Solution code:
s=lambda a,b:a*(a<b)or s(a//b,b)+a%b;n=int(input());print(min(s(i,6)+s(n-i,9)for i in range(n+1)))

Submission status: Runtime Error

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

N = int(input())

memo = [-1] * int(1e5)
memo[0] = 0
def recursive(n):
    if memo[n] != -1:
        return memo[n]
    
    min_num_operation = int(1e9)
    
    index = int(math.log(n, 9))
    if index > 0:
        min_num_operation = min(min_num_operation, 1 + recursive(int(n - math.pow(9, index))))
        
    index = int(math.log(n, 6))
    if index > 0:
        min_num_operation = min(min_num_operation, 1 + recursive(int(n - math.pow(6, index))))
        
    min_num_operation = min(min_num_operation, n)
    
    memo[n] = min_num_operation
    
    return min_num_operation

print(recursive(N))

Submission status: Runtime Error

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

N = int(input())

memo = [-1] * int(1e5)
def recursive(n):
    if memo[n] != -1:
        return memo[n]
    
    min_num_operation = int(1e9)
    
    index = int(math.log(n, 9))
    if index > 0:
        min_num_operation = min(min_num_operation, 1 + recursive(int(n - math.pow(9, index))))
        
    index = int(math.log(n, 6))
    if index > 0:
        min_num_operation = min(min_num_operation, 1 + recursive(int(n - math.pow(6, index))))
        
    min_num_operation = min(min_num_operation, n)
    
    memo[n] = min_num_operation
    
    return min_num_operation
    
 
print(recursive(N))

Submission status: Runtime Error

Solution code:
N=int(input())
M=sorted([1]+[6**i for i in range(1,7)]+[9**i for i in range(1,6)])[::-1]

stack=[]
stacks=[]

def dfs():
	global stack
	global stacks
	if stack==[]:
		return None
	elif sum(stack)==N:
		final = stack.pop(0)
		return stack+[final]
	elif sum(stack)>N:
		stack.pop(0)
	else:
		for m in M:
			if m <= stack[0]:
				stack = [m] + stack
				result = dfs()
				if result != None:
					stacks.append(result)
		stack.pop(0)

for m in M:
	stack=[m]
	dfs()

print(min([len(stack) for stack in stacks]))

Submission status: Runtime Error

Solution code:
def f(car,n):
  if(n<6):
    return n+car
  else:
    si=0
    ni=0
    while(n<6**(si+1)):
      si+=1
    while(n<9**(ni+1)):
      ni+1
    return min(f(car+1,n-6**si),f(car+1,n-9**ni))
print(f(0,int(input())))

Submission status: Runtime Error

Solution code:
n = int(input())

get = []
for i in range(10):
  npow6 = 6**(i+1)
  npow9 = 9**(i+1)
  if npow6 <= 100000:
    get.append(npow6)
  if npow9 <= 100000:
    get.append(npow9)
  
get = sorted(get)

memo = [-1] * 110000
for i in range(6):
  memo[i] = i
  
def dfs(money):
  if memo[money] != -1:
    return memo[money]
  if money == 0:
    return 0
  
  ret = 110000
  for g in get:
    if g > money:
      continue
    ret0 = dfs(money-g) + 1
    ret = min(ret, ret0)
  memo[money] = ret
  return ret

print(dfs(n))

Submission status: Runtime Error

Solution code:
def calc(money, count):
    if money == n:
        return count
    if money > n:
        return inf
    a = [calc(money+i, count+1) for i in num]
    return min(a)
import bisect
inf = 10 ** 10
num = [6 ** i for i in range(7)] + [9 ** i for i in range(1, 6)]
n = int(input())
num = num[:bisect.bisect_left(num, n)]
calc(0, 0)

Submission status: Runtime Error

Solution code:
n = int(input())

dp = [0]*100001
for i in range(1, n+1):
    candi = []
    for j in lst:
        if i >= j:
            candi.append(dp[i-j]+1)
    dp[i] = min(candi)
print(dp[i])

Submission status: Runtime Error

Solution code:
def rec(n):
    if n == 0:
        memo[n] = 0
        return memo[n]
    if memo[n] != -1:
        return memo[n]
    res = n
    pow6 = [1]
    pow9 = [1]
    for i in range(1, n):
        if 6 ** i > n:
            break
        pow6.append(6 ** i)
    
    for j in range(1, n):
        if 9 ** j > n:
            break
        pow9.append(9 ** j)
    L = set(pow6 + pow9)
    
    for k in L:
        res = min(res, rec(n - k)+1)
        
    memo[n] = res
    return memo[n]
    

N = int(input())
memo = [-1] * (N+1)
print(rec(N))

Submission status: Runtime Error

Solution code:
def dfs(cost, N):
    if N<6 :
        return cost+N
    else:
        ret0 = 6 ** math.floor(math.log(N, 6))
        ret1 = 9 ** math.floor(math.log(N, 9))
        if (ret0>1) and (ret1>1):
            return min(dfs(cost+1, N-ret0), dfs(cost+1, N-ret1))
        else:
            ret = max(ret0, ret1)
            return dfs(cost+1, N-ret)

N = int(input())
print(dfs(0, N))

Submission status: Runtime Error

Solution code:
dpの基本形
#漸化式を立てる
#nを与えられて求めるので、求める物をdp[n]とおいてみる
#dp[1]は１円払うのに必要な回数、dp[2]は...dp[n-1]まで知っている状態で、dp[n]はn円払うのに必要な回数を調べていくと考える


#場合１：dp[n]は、dp[n-1]にさらに1円を払う回数１回を足した回数である
#場合２：dp[n]は、dp[n-6]にさらに6円を払う回数１回を足した回数
#場合３：...

#これら全部の最小値を取れば良い！なるほど。
#でも参照できない物もあるから、参照できるやつだけ取り出すと良いだろう。



n = int(input())
pre_list = [1,6,9,36,81,216,729,1296,6561,7776,46656,59049]

#nをn+1個並べたリストを作る
dp = [n]*(n+1)
#0を初期化する
dp[0] = 0


#dp[i]について一つずつ考える
for i in range(1,n+1):
#dp[i]のそれぞれの場合分けについて考える。場合はpre_listの中身の分だけ回せばいい
	for j in pre_list:
		if i - j >= 0:
			dp[i] = min(dp[i],dp[i-j]+1)

print(dp[n])

Submission status: Runtime Error

Solution code:
n = int(input())
memo = [-1] * (n + 1)
def dp(n):
    if n == 0:
        return 0
    if memo[n] != -1:
        return memo[n]
    res = n
    for i in range(7):
        if n >= 6 ** i:
            res = min(res, dp(n - 6 ** i) + 1)
    for j in range(6):
        if n >= 9 ** j:
            res = min(res, dp(n - 9 ** j) + 1)
    memo[n] = res
    return memo[n]

print(dp(n))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)

N=int(input())

memo=[-1]*(N+1)
memo[0]=0

def f(n):
    global memo
    if memo[n]!=-1:
        return memo[n]
    cnt=n
    pow6=1
    while pow6<=n:
        cnt=min(cnt,f(n-pow6)+1)
        pow6*=6
    pow9=1
    while pow9<=n:
        cnt=min(cnt,f(n-pow9)+1)
        pow9*=9
    memo[n]=cnt
    return cnt

print(f(N))

Submission status: Runtime Error

Solution code:
N = int(input())

nine = [9**i for i in range(7, 0, -1)]
six = [6**i for i in range(8, 0, -1)]
tmp = {}

def f(n):
  if(n < 6):
    return n
  if(n in tmp):
    return tmp[n]
  
  m = 1e9+7
  if(n >= 9):
    mn = max(x for x in nine if x <= n)
    if(n%mn == 0):
      m = min(m, n//max_nine)
    else:
      m = min(m, f(n-mn)+1)
  ms = max(x for x in six if x <= n)
  if(n%ms == 0):
    m = min(m, n//ms)
  tmp[n] = min(m, f(n-ms)+1)
  return tmp[n]
print(f(N))

Submission status: Runtime Error

Solution code:
n = int(input())
c = [6**i for i in range(1,7)]
c.extend([9**i for i in range(1, 6)])
c = sorted(c)[::-1]
dp = [0]*100000
for i in range(1,n+1):
    dp[i]=dp[i-1]+1
    for c_ in c:
        if i>=c_:
            dp[i]=min(dp[i],dp[i-c_]+1)
print(dp[n])

Submission status: Runtime Error

Solution code:
n = int(input())

max_range = 10 ** 5
dp = [int(i) for i in range(max_range + 1)]

for i in [6,9]:
    check = i
    while check < max_range:
        for j in range(max_range + 1):
            if j - check >= 0:
                dp[j] = min(dp[j],dp[j-check] + 1)

        check =  check *
        
print(dp[n])

Submission status: Runtime Error

Solution code:
from typing import Callable


class DynamicProgramming(object):

    table: list
    obj_coef: list
    sbj_coef: list

    def __init__(self, item_n: int, border: int, initializer: int = 0):
        self.item_n = item_n
        self.border = border
        self.table = [[initializer for _ in range(self.item_n + 1)] for _ in range(self.border + 1)]

    def __str__(self):
        return "\n".join(list(map(lambda l:
                                  " ".join(list(map(str, l)))
                                  , self.table)))

    def __repr__(self):
        return "DynamicProgramming object:\n" + \
               "item_n: " + str(self.item_n) + ", border: " + str(self.border) + "\n" +\
               "table:\n" + self.__str__()

    def solve(self, obj_coef: list, sbj_coef: list, expr: Callable[[int, int], int]) -> list:
        if len(obj_coef) == self.item_n:  # to 1-base
            obj_coef = [None] + obj_coef
        self.obj_coef = obj_coef

        if len(sbj_coef) == self.item_n:
            sbj_coef = [None] + sbj_coef
        self.sbj_coef = sbj_coef

        for weight_lim in range(1, self.border + 1):
            for item_idx in range(1, self.item_n + 1):
                self.table[weight_lim][item_idx] = expr(weight_lim, item_idx)

        return self.table

    def knapsack_expr(self, weight_lim: int, item_idx: int) -> int:
        res = self.table[weight_lim][item_idx - 1]
        if weight_lim - self.sbj_coef[item_idx] >= 0:
            res = max(res, self.table[weight_lim - self.sbj_coef[item_idx]][item_idx - 1] + self.obj_coef[item_idx])
        return res

    def coin_expr(self, target, coin_idx) -> int:
        if self.sbj_coef[coin_idx] == 1:
            res = target
        else:
            res = self.table[target][coin_idx - 1]
            if target - self.sbj_coef[coin_idx] >= 0:
                res = min(res, self.table[target - self.sbj_coef[coin_idx]][coin_idx] + self.obj_coef[coin_idx])
        return res

    def fill_0_idx_with(self, value: int) -> "DynamicProgramming":
        self.table[0] = [value for _ in range(self.item_n + 1)]
        for i in range(1, self.border + 1):
            self.table[i][0] = value
        return self


if __name__ == '__main__':
    N = int(input())
    values = sorted(list(set([6 ** i for i in range(7)] + [9 ** i for i in range(6)])))
    values_len = len(values)
    dp = DynamicProgramming(values_len, N, initializer=int(10e5))
    print(dp.solve([1 for _ in range(values_len)], values, dp.coin_expr)[N][values_len])

Submission status: Runtime Error

Solution code:
# ABC 099 解4 
import math
def getInt(): return int(input())
def zeros(n): return [0]*n
def db(x): 
    global debug
    if debug: print(x)
def atmUnit(base, req):
    if req<=0: return 0
    else: 
        unit = base ** int(math.log10(req)/math.log10(base))
        return unit # 引き出せる最大の単位量
def atm9(req): return atmUnit(9, req)
def atm6(req): return atmUnit(6, req)
def atm(req):
    db(('req',req))
    if req<=0: return 0
    u9 = atm9(req)
    c9 = req // u9
    db (('unit9,count9',u9,c9))
    u6 = atm6(req)
    c6 = req // u6
    db (('unit6,count6',u6,c6))
    c6 = c6 + atm(req-c6*u6)
    remainMax = min(u9,u6)
    #db(('remainMax:',remainMax))
    minCount = 999999
    for i in range(c9+1):
        for j in range(c6+1):
            #if req-i*u9-j*u6>=remainMax: continue
            if req-i*u9-j*u6<0: continue
            minCount = min(minCount, i+j+atm(req-i*u9-j*u6))
    #db(minCount)
    return minCount
    
debug = False
N = getInt()
print(atm(N))

Submission status: Runtime Error

Solution code:
import math
N = int(input())
def greed(N, a):
    num = 0
    while True:
        if N == 0:
            return num
        p = int(math.log2(N) / math.log2(a))
        N -= a**p
        num += 1
A = []
for n in range(N+1):
    A.append(greed(n, 6) + greed(N-n, 9))
print(min(A))