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:
n = int(input())
num_list = [1]
dp = [0] * (n+1)
dp[1] = 1
dp[2] = 2
dp[3] = 3
dp[4] = 4
dp[5] = 5
dp[6] = 1


def recursion(n, li):
    min_n = 10**9
    for i in li:
        if n - i < 0:
            break
        num = dp[n - i]
        if min_n > num:
            min_n = num
    return min_n + 1


for i in range(1, 7):
    a = 6 ** i
    b = 9 ** i
    if a <= n:
        num_list.append(a)
    if b <= n:
        num_list.append(b)

for i in range(7, n+1):
    dp[i] = recursion(i, num_list)

print(dp[n])

Submission status: Runtime Error

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

Solution code:
n = int(input())

def f(i):
    if i<=5:
        return i
    else:
        lst = [float("INF") for i in range(10)]
        for j in range(1,6):
            if i-9**j>=0:
                lst[j] = f(i-9**j)+1
            if i-6**j>=0:
                lst[j+5] = f(i-6**j)+1
        return min(lst)

print(f(n))

Submission status: Runtime Error

Solution code:
n = int(input())
num = [1]

x = 6
while x < 100000:
    num.append(x)
    x *= 6

x = 9
while x < 100000:
    num.append(x)
    x *= 9

dp = [n] * 110000
dp[0] = 0

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

print(dp[n])

Submission status: Runtime Error

Solution code:
N = int(input())

A = []
for i in range(20):
    if 6**i<=N:
        A.append(6**i)
for i in range(1,20):
    if 9**i<=N:
        A.append(9**i)
AA = sorted(A,reverse=True)
        
INF = float("inf")
dp=[INF]*(N)
dp[0]=1

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

Submission status: Runtime Error

Solution code:
import math, sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from copy import deepcopy
from functools import lru_cache
from heapq import heapify, heappop, heappush
from itertools import accumulate, combinations, permutations
input = sys.stdin.readline
mod = 10**9 + 7
ns = lambda: input().strip()
ni = lambda: int(input().strip())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

n = ni()

res = n
for i in range(n+1):
    cash = 0
    t = i
    while t > 0: # 0 ~ iを6で表す
        cash += t % 6
        t //= 6
    t = n - i
    while t > 0: # n-i ~ nを9で表す
        cc += t % 9
        t //= 9
    if res > cash: # cash最小値
        res = cash

print(res)

Submission status: Runtime Error

Solution code:
n = input().split()
cand = [1]
for i in range(1,6):
  for j in range(1,7):
    cand.append(6**j)
    cand.append(9**i)
import bisect  
count = 0
cand.sort()
while n > 0:
	index = bisect.bisect_left(cand, n)
    if index != 0
      n = n - cand[index-1]
      count += 1
    else:
      n -= 1
      count += 1
print(count)

Submission status: Runtime Error

Solution code:
A=[1,6,36,216,1296,7776,46656,9,81,729,6561,59049]
N=int(input())
ans=0
while N!=0:
  N-=max([a for _ in A if A<=N])
  ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque


max_n = 11000
dp = [-1] * max_n  # -1を未探索とする
dp[0] = 0  # 初期条件の設定
n = int(input())
que = deque([])
que.append(dp[0])
while que:
    v = que.popleft()
    pow = 1
    while v + pow <= n:
        if dp[v + pow] == -1:
            dp[v + pow] = dp[v] + 1
            que.append(v + pow)
        pow *= 6
    pow = 1
    while v + pow <= n:
        if dp[v + pow] == -1:
            dp[v + pow] = dp[v] + 1
            que.append(v + pow)
        pow *= 9
# print(dp)
print(dp[n])

Submission status: Runtime Error

Solution code:
N=int(input())
dp=[10**9 for i in range(N)]
dp[0]=0
for i in range(N+1):
    p=1
    while(1<=i):
        dp[i]=min(dp[i],dp[i-p]+1)
        p*=6
    p=1
    while(1<=i):
        dp[i]=min(dp[i],dp[i-p]+1)
        p*=9

print(dp[-1])

Submission status: Runtime Error

Solution code:
import math

dp = [float('inf') for _ in range(110000)]
withdraw = []

N = int(input())

#引き出し可能な金額の配列にする
withdraw.append(1)

for i in range( math.floor(math.log(N,6)) + 1):
    withdraw.append(6**i)

for i in range( math.floor(math.log(N,9)) + 1):
    withdraw.append(9**i)

withdraw = sorted(list(set(withdraw)))

dp[0] = 0

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

Submission status: Runtime Error

Solution code:
import numpy as np
from functools import reduce
from operator import add,sub,mul,truediv
from fractions import gcd


MAX_N = 110000

memo = [-1]*MAX_N

def rec(n):
    if n == 0: return 0
    if memo[n] != -1:return memo[n]

    res = n

    pow6  =  1
    while pow6 <= n:
       # print(pow6)
        res = min(res,rec(n-pow6)+1)
        pow6 = pow6*6

    pow9 = 1
    while pow9 <= n:
        res = min(res,rec(n-pow9)+1)
        pow9 = pow9*9

    memo[n] = res
    return res



N = int(input())

print(rec(N))



#print(int(math.log(n,6)))
#print(int(math.log(n,9)))
#
#n6  = int(math.log(n,6))+1
#n9  = int(math.log(n,9))+1
#
#ans = 1000000000000000000
#for bits6 in range(1 << n6):
#    print(bin(bits6))
#    cnt = 0
#    x= 0
#    for bits9 in range(1 << n9):
#        for bits1 in range(1 << 1):
#            for d6 in range(0,n6):
#                if (bits6>>d6)&1:
#                    cnt = cnt + 1
#                    x = x + 6**d6
#                else:
#                    pass
#            for d9 in range(0,n9):
#                if (bits9>>d9)&1:
#                    cnt = cnt + 1
#                    x = x + 9**d9
#                else:
#                    pass
#            for d1 in range(0,1 << 1):
#                if (bits6>>d6)&1:
#                    cnt = cnt + 1
#                    x = x + 6**d6
#                else:
#                    pass
#
#                if( x == n) and (ans > cnt):
#                    ans = cnt
#
#
#print(ans)
#

Submission status: Runtime Error

Solution code:
import numpy as np
from functools import reduce
from operator import add,sub,mul,truediv
from fractions import gcd
import math


MAX_N = 110000

memo = [-1]*MAX_N

def rec(n):
    if n == 0: return 0
    if memo[n] != -1:return memo[n]

    res = n

    pow6  =  1
    while pow6 <= n:
       # print(pow6)
        res = min(res,rec(n-pow6)+1)
        pow6 = pow6*6

    pow9 = 1
    while pow9 <= n:
        res = min(res,rec(n-pow9)+1)
        pow9 = pow9*9

    memo[n] = res
    return res



N = int(input())

print(rec(N))

Submission status: Runtime Error

Solution code:
import copy
import itertools

N = int(input())
six_nines = set()

#6,9の乗数を列挙する
for i in range(1,6):
  a = 6**i
  if a <= N and a not in six_nines:
    six_nines.add(a)
    for j in range(1,N//a):
      six_nines.add(a*j)
  a = 9**i
  if a <= N and a not in six_nines:
    six_nines.add(a)
    for j in range(1,N//a):
      six_nines.add(a*j)

comb_six_nines = copy.copy(six_nines)

#6,9の乗数の和を列挙する
for comb in itertools.combinations(six_nines,2):
  if comb[0]+comb[1] <= N and comb[0]+comb[1] not in comb_six_nines:
    comb_six_nines.add(comb[0]+comb[1])

#comb_six_nines = list(comb_six_nines)
#comb_six_nines.sort(reverse=True)
#comb_six_nines.append(1)
six_nines = list(six_nines)
six_nines.sort(reverse=True)
six_nines.append(1)

#print(comb_six_nines)
print(six_nines)

#Nを列挙した中の大きい方から引いていく
ans = 0
while N != 0:
  for comb in six_nines:
    if N >= comb:
      print(N,comb)
      if N 
      N -= comb
      ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())

dp = [100000] * (10**5)
dp[0] = 0

for n in range(N):
  count = 1
  while(True):
    if count > N:
      break

    dp[n+count] = min(dp[n+count], dp[n]+1)
    count *= 6

  count = 1
  while(True):
    if count > N:
      break

    dp[n+count] = min(dp[n+count], dp[n]+1)
    count *= 9

print(dp[N])

Submission status: Runtime Error

Solution code:
INF = 10 ** 20
 
N = int(input())
coin_list = [1] + [6**i for i in range(1, 7)] + [9**i for i in range(1, 6)]
dp = [INF]*(N+1)
dp[0] = 0
 
for i in range(1,N+1):
	for coin in coin_list:
    	if i-coin >= 0: dp[i] = min(dp[i], dp[i-coin]+1)
 
print(dp[N])

Submission status: Runtime Error

Solution code:
INF = 10 ** 20
 
N = int(input())
coin_list = [1] + [6**i for i in range(1, 7)] + [9**i for i in range(1, 6)]
dp = [INF]*(N+1)
dp[0] = 0

for i in range(coin,N+1):
	for coin in coin_list:
    	if i-coin >= 0: dp[i] = min(dp[i], dp[i-coin]+1)
 
print(dp[N])

Submission status: Runtime Error

Solution code:
INF = 10 ** 20
 
N = int(input())
coin_list = [1] + [6**i for i in range(1, 7)] + [9**i for i in range(1, 6)]
dp = [INF]*(N+1)
dp[0] = 0

for i in range(coin,N+1):
    for coin in coin_list:
        dp[i] = min(dp[i], dp[i-coin]+1)
 
print(dp[N])

Submission status: Runtime Error

Solution code:
INF = 10 ** 20

N = int(input())
coin_list = [1] + [6**i for i in range(1, 7)] + [9**i for i in range(1, 6)]
dp = [INF]*(W+1)
dp[0] = 0
 
for coin in coin_list:
    for i in range(coin,W+1):
        dp[i] = min(dp[i], dp[i-coin]+1)
 
print(dp[W])

Submission status: Runtime Error

Solution code:
INF = 10 ** 20

W,N = map(int,input().split())
coin_list = [1] + [6**i for i in range(1, 7)] + [9**i for i in range(1, 6)]
dp = [INF]*(W+1)
dp[0] = 0
 
for coin in coin_list:
    for i in range(coin,W+1):
        dp[i] = min(dp[i], dp[i-coin]+1)
 
print(dp[W])

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(999999999)
from functools import lru_cache
@lru_cache(maxsize=32)
def solve(cnt,nokori):
    if nokori<6:
        return cnt+nokori

    for six in range(10,-1,-1):
        if 6**six <= nokori:
            break
    for nine in range(10,-1,-1):
        if 9**nine <= nokori:
            break

    res1 = solve(cnt+1,nokori-6**six)
    if nine != 0:
        res2 = solve(cnt+1,nokori-9**nine)
    else:
        res2=10**9

    return min([res1,res2])

print(solve(0,n))

Submission status: Runtime Error

Solution code:
def saiki_dp(price):
    if price==0:
        return 0
    if memo[price]!=-1:
        return memo[price]
    res=100100100
    pow6=1
    while pow6<=price:
        res=min(res,saiki_dp(price-pow6)+1)
        pow6*=6
    pow9=1
    while pow9<=price:
        res=min(res,saiki_dp(price-pow9)+1)
        pow9*=9
    memo[price]=res
    return memo[price]
n=int(input())
memo=[-1]*(n+1)
roku=kata(6)
kyuu=kata(9)
print(saiki_dp(n))

Submission status: Runtime Error

Solution code:
N = int(input())

ef num_withdraw_ll(N):
    dp = [N] * (N + 1)
    dp[0] = 0
    for n in range(0, N):
        dp[n + 1] = min(dp[n + 1], dp[n] + 1)
        coin = 6
        while n + coin <= N:
            dp[n + coin] = min(dp[n + coin], dp[n] + 1)
            coin *= 6
        coin = 9
        while n + coin <= N:
            dp[n + coin] = min(dp[n + coin], dp[n] + 1)
            coin *= 9
    return dp[N]

print(num_withdraw_ll(N))

Submission status: Runtime Error

Solution code:
N = int(input())

def num_withdraw_ll(N):
    dp = [N] * (N + 1)
    dp[0] = 0
    for n in range(1, N):
        dp[n + 1] = min(dp[n + 1], dp[n] + 1)
        coin = 6
        while coin <= N:
            dp[n + coin] = min(dp[n + coin], dp[n] + 1)
            coin *= 6
        coin = 9
        while coin <= N:
            dp[n + coin] = min(dp[n + coin], dp[n] + 1)
            coin *= 9
    return dp[N]    

print(num_withdraw_ll(N))

Submission status: Runtime Error

Solution code:
li6 = [6 ** i for i in range(7)]
li9 = [9 ** i for i in range(6)]

def s69(n):
    if n < 6:
        return n
    else:
        s6 = li6[bi.bisect(li6, n) - 1]
        s9 = li9[bi.bisect(li9, n) - 1]
        return min(n // s6 + s69(n % s6), 1 + s69(n - s9))


print(s69(int(input())))

Submission status: Runtime Error

Solution code:
from functools import lru_cache

@lru_cache(maxsize=1000)
def fx(n):
  if n == 0:
    return 0
  if n == 1:
    return 1
  arr = []
  a = n
  cnt = 1
  b = fx(n-1)+1
  arr.append(b)
  while n-6**cnt >= 0:
    x = n-(6**cnt)
    b = fx(x)+1
    arr.append(b)
    cnt += 1
  cnt = 1
  while n-9**cnt >= 0:
    x = n-(9**cnt)
    b = fx(x)+1
    arr.append(b)
    cnt += 1
  return min(arr)
  
N = int(input())
print(fx(N))

Submission status: Runtime Error

Solution code:
n = int(input())
c9 = 0
m = n
while(m>1):
  m = m//9
  if m !== 0: 
  	pass
  else:
    c9 += 1
m = n - 9**c9

c6 = 0
while(m>1):
  m = m//9
  if m !== 0: 
  	pass
  else:
    c6 += 1
    
c1 = n - (9**c9+c6**c6)
print(c9+c6+c1)

Submission status: Runtime Error

Solution code:
import numpy as np
n = int(input())
dp = [np.inf for _ in range(100000)]
dp[0] = 0
num = [1,6,9]
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())
dp = [[float('inf') for i in range(N+1)] for j in range(4)]
dp[0][0] = 0
dp[3] = [i for i in range(N+1)]
def below_power(n,a):
    "n以下になるa**xのxの最大値を求める"
    x = 0
    while n >= a**x:
        x += 1
    return x-1
nine = below_power(N,9)
six = below_power(N,6)
for i in range(nine,0,-1):
    dp[1][9**i] = 1
    x= (9**i)
    for j in range(x,N+1):
        dp[1][j] = min(dp[1][j],dp[1][j-x]+1)
for i in range(1,six+1):
    dp[2][6**i] = 1
    x= (6**i)
    for j in range(N+1):
        if j >= 9:
            dp[2][j] = min(dp[2][j],dp[2][j-x]+1)
        if j >= x:
            dp[2][j] = min(dp[2][j],dp[1][j-x]+1)
for i in range(1,6):
    dp[3][-1] = min(dp[3][-1],dp[2][N-i]+i)
print(dp[-1][-1])

Submission status: Runtime Error

Solution code:
list=[1, 1, 1, 1, 1]
for i in range(1, 7):
  list.append(6**i)
for j in range(1, 7):
  list.append(9**i)
sorted(list, reverse=True)
N=int(input())
count=0
for i in list:
  if i <= N:
    N=N-i
    count+=1
      if N==0:
        break
print(count)

Submission status: Runtime Error

Solution code:
list=[1, 1, 1, 1, 1]
for i in range(1, 7):
  list.append(6**i)
for j in range(1, 7):
  list.append(9**i)
sorted(list, reverse=True)
N=int(input())
count=0
for i in list:
  if i <= N:
    N=N-i
    count+=1
      if N==0:
        break
        print(count)

Submission status: Runtime Error

Solution code:
list=[1, 1, 1, 1, 1]
for i in range(1, 7):
  list.append(6**i)
for j in range(1, 7):
  list.append(9**i)
sorted(list, reverse=True)
N=int(input())
count=0
for i in list:
  if i <= N:
    N=N-i
    count+=1
      if N==0:
        print(count)
      else:
        continue

Submission status: Runtime Error

Solution code:
list=[1, 1, 1, 1, 1]
for i in range(1, 7):
  list.append(6**i)
for j in range(1, 7):
  list.append(9**i)
sorted(list, reverse=True)
N=int(input())
count=0
for i in list:
  if i <= N:
    N=N-i
    count+=1
      if N==0:
        print(count)

Submission status: Runtime Error

Solution code:
list=[1, 1, 1, 1, 1]
for i in range(1, 7):
  list.append(6**i)
for j in range(1, 7):
  list.append(9**i)
sorted(list, reverse=True)
N=int(input())
count=0
for i in list:
  if N <= i:
    N=N-i
    count+=1
      if N==0:
        print(count)

Submission status: Runtime Error

Solution code:
list=[1, 1, 1, 1, 1]
for i in range(1, 7):
  list.append(6**i)
for j in range(1, 7):
  list.append(9**i)
sorted(list, reverse=True)
N=int(input())
count=0
for i in list:
  if N <= i:
    N=N-i
    count=+1
      if N==0:
        print(count)

Submission status: Runtime Error

Solution code:
list=[1, 1, 1, 1, 1]
for i in range(1, 7):
  list.append(6**i)
for j in range(1, 7):
  list.append(9**i)
sorted(list, reverse=True)
N=int(input())
count=0
for i in range(19):
  if N <= i:
    N=N-i
    count=+1
      if N==0:
        print(count)

Submission status: Runtime Error

Solution code:
list=[1, 1, 1, 1, 1]
for i in range(1, 7):
  list.append(6**i)
for j in range(1, 7):
  list.append(9**i)
sort(list, reverse=True)

Submission status: Runtime Error

Solution code:
list=[1, 1, 1, 1, 1]
for i in range(1, 7):
  list.append(6**i)
for j in range(1, 7):
  list.append(9**i)
sort(list, reverse=True)
N=int(input())
count=0
for i in range(19):
  if N <= i:
    N=N-i
    count=+1
      if N==0:
        print(count)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define rep(i,n) for(int i=0; i<(n); i++)
#define all(v) (v).begin(),(v).end()
int main() {
  int n;
  cin >> n;
  int ans=1000000;
  int A=pow(9,5);
  int B=pow(6,6);
  int C=pow(6,5);
  int D=pow(9,4);
  int E=pow(6,4);
  int F=pow(9,3);
  int G=pow(6,3);
  int H=pow(9,2);
  int I=pow(6,2);
  int J=9;
  int K=6;
  int L=1;
  rep(a,2)rep(b,2)rep(c,6)rep(d,2)rep(e,6)rep(f,2)rep(g,4)rep(h,3)rep(i,3)rep(j,4)rep(k,2)rep(l,6){
    if(n==A*a+B*b+C*c+D*d+E*e+F*f+G*g+H*h+I*i+J*j+K*k+L*l){
      if(ans>=a+b+c+d+e+f+g+h+i+j+k+l) cout << a << b << c << d << e << f << g << h << i << j << k << l << endl; 
      ans = min(ans,a+b+c+d+e+f+g+h+i+j+k+l);
    }
  }
  cout << ans << endl;
  return 0;
}

Submission status: Runtime Error

Solution code:
//  Created by conan1024hao in 2019.
//  Copyright © 2019 conan1024hao. All rights reserved.
//  専用ライブラリです、自由にコピーして構いません。
//  感谢看我的代码！Wechat:conan1024hao QQ:810396815
#pragma GCC optimize ("O3")
#include <iostream>
#include <iomanip>
#include <istream>
#include <ostream>
#include <sstream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <utility>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <ctime>
#include <cctype>
#include <cstdlib>
#define IINF 10e8
#define INF 10e16
#define MOD 1000000007
#define mod 1000000007
#define rep(i, a, n) for (ll i = a; i < (ll)(n); i++)
#define Endl endl
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define mmax(x,y)(x>y?x:y)
#define mmin(x,y)(x<y?x:y)
#define chmax(x,y) x=mmax(x,y)
#define chmin(x,y) x=mmin(x,y)
#define all(x) (x).begin(),(x).end()
#define siz(x) (ll)(x).size()
#define PI acos(-1.0)
using namespace std;
//using Int=int_fast64_t;
typedef long long int ll;
typedef pair<ll,ll>Pll;
typedef pair<int,int>Pin;
long long GCD(long long a, long long b) { return b ? GCD(b, a%b) : a; }
long long LCM(long long a, long long b)  {return a/GCD(a,b)*b;}
int dx[8]={-1,0,1,0,1,1,-1,-1};
int dy[8]={0,-1,0,1,1,-1,1,-1};
char dir[4]={'u','l','d','r'};
ll cmp1(pair<ll,string>a,pair<ll,string> b){
        if(a.fi!=b.fi)
        return a.fi<b.fi;
        else
        return a.se<b.se;
}
//--------------------------------------------------------------------------

//---------------------------------------------------------------------------
int main(){//問題をちゃんと見ろ!!!!!!!!!!!!!!!!!      llか??????????        memset()!!!!!!!!!!!!       ペナを減らせ!!!!!!!!!!!!!
    cin.tie(0);
    ios::sync_with_stdio(false);
    //-------------------------------
    ll n;
    cin>>n;
    vector<ll>use;
    use.pb(1);
    
    for(ll i=1;i<1000;i++){
        ll tmp=pow(6,i);
        if(tmp>n)break;
        use.pb(tmp);
    }
    for(ll i=1;i<1000;i++){
        ll tmp=pow(9,i);
        if(tmp>n)break;
        use.pb(tmp);
    }
    sort(all(use));
    reverse(all(use));
    ll cnt=0;
    ll nn=n;
    ll dp[100005];
    memset(dp,0,sizeof(dp));
    for(ll i=1;i<=n;i++){
        ll min=INF;
        for(ll j=0;j<siz(use);j++){
            if(i>=use[j]){
                chmin(min,mmin(dp[i-1]+1,dp[i-use[j]]+1));
            }
        }
        dp[i]=min;
    }
    cout<<dp[n]<<endl;
    //-------------------------------
    return 0;
}
//---------------------------------------------------------------------------

Submission status: Runtime Error

Solution code:
import java.util.*;

class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		
		int n = sc.nextInt();
		int[] ar = {1,6,9,36,81,216,729,1296,6561,7776,46656,59049};
		
		int[] dp = new int[100005];
		dp[0] = 0;
		
		for (int i=1; i<=n; i++) {
			
			int min = Integer.MAX_VALUE;
			for (int j=0; j<ar.length; j++) {
				if (i >= ar[j]) {
					min = Math.min(min, Math.min(dp[i-1]+1, dp[i-ar[j]]+1));
				}
			}
			dp[i] = min;
			
		}
		
		System.out.println(dp[n]);
	}
}

Submission status: Runtime Error

Solution code:
import math
n=int(input())
dp=[math.inf for _ in range(n+1)]
dp[0]=0
for i in range(n):
    power=1
    while i+power <= n:
        dp[i+power] = min(dp[i+power],dp[i]+1)
        power*=6
    power=1
    while i+power <= n:
        dp[i+power] = min(dp[i+power],dp[i]+1)
        power*=9
print(dp[n])

Submission status: Runtime Error

Solution code:
import math
n=int(input())
dp=[math.inf]*(n+1)
dp[0]=0
for i in range(n):
    power=1
    while i+power <= n:
        dp[i+power] = min(dp[i+power],dp[i]+1)
        power*=6
    power=1
    while i+power <= n:
        dp[i+power] = min(dp[i+power],dp[i]+1)
        power*=9
print(dp[n])

Submission status: Runtime Error

Solution code:
import math
n = int(input())
count = 0
while n != 0:
  max_value = 1
  for i in range(1, n+1):
    if math.log(i, 6) == int(math.log(i, 6)) or math.log(i, 9) == int(math.log(i, 9)):
    	max_value = max(max_value, i)
  n = n - max_value
  lst.add(max_value)
  count += 1
print(count)

Submission status: Runtime Error

Solution code:
import math
n = int(input())
count = 0
lst = []
while n != 0:
  max_value = 1
  for i in range(1, n):
    if i in max_value:
      continue
    if math.log(i, 6) == int(math.log(i, 6)) or math.log(i, 9) == int(math.log(i, 9)):
    	max_value = max(max_value, i)
  n = n - max_value
  lst.add(max_value)
  count += 1
print(count)

Submission status: Runtime Error

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
    
"""
  elif n < 6:
    return con + n
    
  elif n < 9:
    return con + (n - 5)
"""    

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

Solution code:
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

int main(){
 LL N;
 cin >> N;
 LL num_nine=0;
 LL num_six=0;
 LL num_one=0;
 LL num=0;
LL para_nine=0;
LL para_six=0;
 while(N>5)
 {
     para_nine=9;
     para_six=6;
     while(para_nine*9<=N){
                 para_nine=para_nine*9;
     }
     while(para_six*6<=N){
                 para_six=para_six*6;
     }
     if(N-max(para_six,para_nine)>=0){
         N=N-max(para_six,para_nine);
     }
     else{
         N=N-min(para_six,para_nine);
     }
     
     ++num;
     }
     
     num=N+num;
 cout << num;
    }

Submission status: Runtime Error

Solution code:
N = int(input())
dp = [N] * 200
dp[0] = 0
for i in range(0,N+1):
    m = 1
    while m <= N:
        dp[i] = min(dp[i],dp[i-m]+1)
        m *= 6
    m = 1
    while m <= N:
        dp[i] = min(dp[i],dp[i-m]+1)
        m *= 9
print(dp[N])

Submission status: Runtime Error

Solution code:
import math
N=int(input())
l=[1]
for i in range(1,int(math.log(N,6))+1):
    l.append(6**i)
for i in range(1,int(math.log(N,9))+1):
    l.append(9**i)
l.sort()
dp=[math.inf for _ in range(N+1)]
dp[0] = 0
for i in range(len(l)):
    for j in range(l[i],N+1):
        dp[j] = min(dp[j],dp[j-l[i]]+1)
print(dp[-1])

Submission status: Runtime Error

Solution code:
import math

if __name__ == '__main__':
    N=int(input())
    power_nine=int(math.log(N,9)+1)
    power_six=int(math.log(N,6)+1)

    dp=[math.inf]*(N+1)
    for i in range(min(6,N+1)):
        dp[i]=i
    for i in range(N+1):
        for j in range(1,power_six):
            if i+6**j<=N:
                dp[i+6**j]=min(dp[i+6**j],dp[i]+1)
        for j in range(1, power_nine):
            if i + 9 ** j <= N:
                dp[i + 9 ** j] = min(dp[i + 9 ** j], dp[i] + 1)


    print(dp[N])

Submission status: Runtime Error

Solution code:
N=int(input())
dstb=[1]+[6**i for i in range(1,7)]+[9**j for j in range(1,6)]
DP=[10**5]*(N*2)
DP[0]=0
for i in range(N+1):
  for j in dstb:
    DP[i+j]=min(DP[i+j], DP[i]+1)

print(DP[N])

Submission status: Runtime Error

Solution code:
n = int(input())

max_N = 1000000
memo = [False]*max_N

# 貰う DPではなく、再帰を使ったメモ化再帰
def f(n):
	if n < 6:
		return n
	if memo[n]:
		return memo[n]
	
	ans = n
	# メモ化
	x = 6
	while x <= n:
		ans = min(ans, f(n-x)+1)
		x *= 6
	
	x = 9
	while x <= n:
		ans = min(ans, f(n-x)+1)
		x *= 9
	
	return ans
		
	
print(f(n))

Submission status: Runtime Error

Solution code:
n=int(input())
dp=[10**5]*n
dp[0]=0
for i in range(n+1):
    pow=1
    while pow<=n:
        dp[i]=min(dp[i],dp[i-pow]+1)
        pow*=6
    pow=1
    while pow<=n:
        dp[i]=min(dp[i],dp[i-pow]+1)
        pow*=9
print(dp[n])

Submission status: Runtime Error

Solution code:
n=int(input())
dp=[10**5]*n
dp[0]=0
for i in range(n+1):
    pow=1
    while pow<=n:
        dp[i]=min(dp[i],dp[i-pow]+1)
        pow*=6
    pow=1
    while pow<=n:
        dp[i]=min(dp[i],dp[i-pow]+1)
        pow*=9
print(dp[n+1])

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
h=list(map(int,input().split()))
dp=[10**5]*n
dp[0]=0
for i in range(n):
    pow=1
    while pow<=n:
        dp[i]=min(dp[i],dp[i-pow]+1)
        pow*=6
    pow=1
    while pow<=n:
        dp[i]=min(dp[i],dp[i-pow]+1)
        pow*=9
print(dp[n-1])

Submission status: Runtime Error

Solution code:
n=int(input())
num6=6
num9=9
while num6<=n:
  l.append(num6)
  num6*=6
while num9<=n:
  l.append(num9)
  num9*=9
count=[0,1,2,3,4,5,1,2,3,1,2,3]
for i in range(12,n+1):
  min=100000
  for j in l:
    if i-j<0:
      pass
    else:
      if min>count[i-j]+1:
        min=count[i-j]+1
  count.append(min)
print(count[n])

Submission status: Runtime Error

Solution code:
n = int(input())

import math
def bank2(n):
    ans = 1
    list_six = [6**i for i in range(math.floor(math.log(n, 6)+1))]
    list_nine = [9**i for i in range(math.floor(math.log(n, 9)+1))]
    
    if n in list_six or n in list_nine:
        pass
    elif n == 12 or n == 13 or n == 14:
        ans += bank(n-6)
    elif n > 1:
        ans += min(bank(n - list_six[-1]), bank(n - list_nine[-1]))
        
    return ans

print(bank2(n))

Submission status: Runtime Error

Solution code:
n = int(input())
import math
def bank(n):
    ans = 1
    list_six = [6**i for i in range(math.floor(math.log(n, 6)+1))]
    list_nine = [9**i for i in range(math.floor(math.log(n, 9)+1))]
    
    if n == 6 or n== 9:
        pass
    elif n == 12 or n == 13 or n == 14:
        ans += bank(n-6)
    elif n > 1:
        ans += bank(n - max(list_six[-1], list_nine[-1]))
        
    return ans
  
print(bank(n))

Submission status: Runtime Error

Solution code:
#なんか考えはある。時間ある時にやっとけ

import copy
import heapq
import math
import fractions

def j(n):
    if n:print("Yes")
    else:print("No")
    exit(0)
rem = 10 ** 9 + 7

"""
def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")
"""

def ip():
    return int(input())
def iprow():
    return [int(i) for i in input().split()]
def ips():
    return (int(i) for i in input().split())
def ipmultiplerow(n):
    a = []
    for i in range(n):
        a.append(ip())
    return a
def printmultiplerow(a):
    for i in a:
        print(i)
def printrow(a):
    for i in range(len(a)-1):
        print(a[i],end = " ")
    print(a[-1])


n = ip()
l = [1]
l.extend([6**i for i in range(10) if 6**i <= 100000])
l.extend([9**i for i in range(10) if 9**i <= 100000])
l = list(set(l))
l.sort()
printrow(l)
ans = [1 for i in range(n)]

total = 0
s = []
s = [0 for i in range(12)]
while n - total > 3:
    total+=3
    if


print(s,n-total)

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(2000000)

def re(r,k,l):
    if k==0:return r
    while(k<l[0]):
        l=l[1:]
    return re(r+1,k-l[0],l)





n=int(input())
i=1
l6=[]
ans=10**5
while(i<n):
    l6.append(i)
    i*=6
i=1
l9=[]
while(i<n):
    l9.append(i)
    i*=9
l6.sort(reverse=True)
l9.sort(reverse=True)
for i in range(n+1):
    ans=min(ans,re(0,n-i,l6)+re(0,i,l9))
print(ans)