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: Wrong Answer

Solution code:
def sum_base10to(n, b):
    if n // b:
        return sum_base10to(n // b, b) + n % b
    return n % b


n = int(input())
i = 0
res = n
for i in range(n):
    cc = sum_base10to(i, 6) + sum_base10to(n - i, 9)
    if cc < res:
        res = cc
print(res)

Submission status: Wrong Answer

Solution code:
import itertools
import math
from collections import deque
from collections import defaultdict
from itertools import permutations
import heapq
import bisect
from scipy.sparse.csgraph import floyd_warshall as wf

N = int(input())
dp = [10**7]*(N+1)
dp[0]=0
for i in range(1,N+1):
    six = math.floor(math.log(i,6))
    nine = math.floor(math.log(i,9))
    for j in range(six+1):
        for k in range(nine+1):
            dp[i] = min(dp[i-6**j]+1,dp[i-9**k]+1)
print(dp[N])

Submission status: Wrong Answer

Solution code:
import itertools
import math
from collections import deque
from collections import defaultdict
from itertools import permutations
import heapq
import bisect
from scipy.sparse.csgraph import floyd_warshall as wf

N = int(input())
dp = [10**7]*(N+1)
dp[0]=0
for i in range(1,N+1):
    six = math.floor(math.log(i,6))
    nine = math.floor(math.log(i,9))
    dp[i] = min(dp[i-6**six]+1,dp[i-9**nine]+1,dp[i-1]+1)
print(dp[N])

Submission status: Wrong Answer

Solution code:
import itertools
import math
from collections import deque
from collections import defaultdict
from itertools import permutations
import heapq
import bisect
from scipy.sparse.csgraph import floyd_warshall as wf

N = int(input())
dp = [10**7]*(N+1)
dp[0]=0
for i in range(1,N+1):
    six = math.floor(math.log(i,6))
    nine = math.floor(math.log(i,9))
    dp[i] = min(dp[i-6**six]+1,dp[i-9**nine]+1)
print(dp[N])

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
dp = [10**7]*(N+1)
dp[0]=0
for i in range(1,N+1):
    six = int(math.log(i,6))
    nine = int(math.log(i,9))
    dp[i] = min(dp[i-6**six]+1,dp[i-9**nine]+1)
print(dp[N])

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
import math
from collections import defaultdict
 
N = int(input())
 
memo = defaultdict(lambda: -1)
memo[0] = 0
def recursive(n):
    if memo[n] != -1:
        return memo[n]
    
    min_num_operation = n
    
    index = 0
    temp_n = n
    while temp_n > 0:
        if temp_n % 9 == 0:
            index += 1
            temp_n /= 9
        else:
            break
    if index > 0:
        min_num_operation = min(min_num_operation, 1 + recursive(int(n - math.pow(9, index))))
        
    index = 0
    temp_n = n
    while temp_n > 0:
        if temp_n % 6 == 0:
            index += 1
            temp_n /= 6
        else:
            break
    if index > 0:
        min_num_operation = min(min_num_operation, 1 + recursive(int(n - math.pow(6, index))))
        
    memo[n] = min_num_operation
    
    return min_num_operation
 
print(recursive(N))

Submission status: Wrong Answer

Solution code:
N = int(input())

ms = set([1])
i = 1
while True:
    m = 6**i
    if m > N:
        break
    ms.add(m)
    i += 1
i = 1
while True:
    m = 9**i
    if m > N:
        break
    ms.add(m)
    i += 1

dp = [10**9] * N # i+1 円を引き出すための最小手数
dp[0] = 1
for i in range(1, N):
    dp[i] = min(dp[i], min(dp[i-m] for m in ms if i-m >= 0) + 1)
print(dp[-1])

Submission status: Wrong Answer

Solution code:
N = int(input())

ms = set([1])
i = 1
while True:
    m = 6**i
    if m > N:
        break
    ms.add(m)
    i += 1
i = 1
while True:
    m = 9**i
    if m > N:
        break
    ms.add(m)
    i += 1

dp = [0] * N # i+1 円を引き出すための最小手数
dp[0] = 1
for i in range(1, N):
    dp[i] = min(dp[i-m] for m in ms if i-m >= 0) + 1
print(dp[-1])

Submission status: Wrong Answer

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

N = int(input())

#memo = defaultdict(lambda: -1)
#memo[0] = 0
def recursive(n):
    #if memo[n] != -1:
    #    return memo[n]
    if n == 0:
        return 0
    
    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: Wrong Answer

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

N = int(input())

memo = defaultdict(lambda: -1)
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: Wrong Answer

Solution code:
import numpy as np
N = int(input())
ans = 0
while N != 0:
    for i in range(12):
        if np.power(9,i) > N:
            continue
        else:
            nine = np.power(9,i)
    for i in range(12):
        if np.power(6,i) > N:
            continue
        else:
            six = np.power(6,i)

    if nine > six:
        N = N - nine
        ans += 1
    elif six > nine:
        N = N - six
        ans += 1
    else:
        ans += N
        N = 0
        
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
if n<6:
  print(n)
  exit()
x=n%3
n-=x
print(x+n//9+n//6)

Submission status: Wrong Answer

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
	global minstacklen
	if stacks!=[]:
		return None
	else:
		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:
	if stacks!=[]:
		print(min([len(stack) for stack in stacks]))
		break
	else:
		stack=[m]
		dfs()

Submission status: Wrong Answer

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
	global minstacklen
	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:
	if stacks!=[]:
		print(min([len(stack) for stack in stacks]))
		break
	else:
		stack=[m]
		dfs()

Submission status: Wrong Answer

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=[]
minstacklen=10**7

def dfs():
	global stack
	global stacks
	global minstacklen
	if stack==[]:
		return None
	elif sum(stack)==N:
		final = stack.pop(0)
		return len(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:
					minstacklen = min(minstacklen, result)
		stack.pop(0)

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

print(minstacklen)

Submission status: Wrong Answer

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

for i in range(1,7):
  ls.append(6**i)
  ls.append(9**i)
dp = [float('inf') for i in range(n+2)]
dp[0] = 0

#円の総合計
for i in range(n+1):
  for j in ls:
    if i-j>=0:
      dp[i+1] = min(dp[i]+1, dp[i-j+1]+1,dp[i+1])
    else:
      dp[i+1] = min(dp[i]+1,dp[i+1])
print(dp[n])

Submission status: Wrong Answer

Solution code:
n = int(input())
coins = [1]
t = 6 
while t <= n:
    coins.append(t)
    t *= 6

t = 9
while t <= n:
    coins.append(t)
    t *= 9

coins.sort()

dp = [ float("inf") for _ in range(n+10) ]
dp[1] = 1

for i in range(1, n+1):
    for c in coins:
        if i + c > n:
            continue
        dp[i+c] = min(dp[i+c], dp[i]+1)

print(dp[n])

Submission status: Wrong Answer

Solution code:
n = int(input())
coins = [1]
t = 6 
while t < n:
    coins.append(t)
    t *= 6

t = 9
while t < n:
    coins.append(t)
    t *= 9

coins.sort()

dp = [ float("inf") for _ in range(n+10) ]
dp[1] = 1

for i in range(1, n+1):
    for c in coins:
        if i + c > n:
            continue
        dp[i+c] = min(dp[i+c], dp[i]+1)

print(dp[n])

Submission status: Wrong Answer

Solution code:
n=int(input())
table=[59049, 46656, 7776, 6561, 1296, 729, 216, 81, 36, 9, 6, 1]
ans=0
for i in table:
    if (n//i)!=0:
        tmp=n//i
        ans+=tmp
        n-=(tmp*i)
        #print(n)
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
ans=N
for i in range(1,N+1):
    count=0
    t=i
    while t>0:
        count+=t%6
        t//=6#last 0
    t=N-i
    while t>0:
        count+=t%9
        t//=9
    ans=min(ans,count)
print(ans)

Submission status: Wrong Answer

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

"""
N = 6**i + 9**j
とする。

"""

N = I()

smalls = []
bigs = []
for i in range(10**5):
    small = 6**i
    big = 9**i

    if small <= N:
        smalls.append(small)
    if big <= N:
        bigs.append(big)
    if small > N:
        break

smalls = sorted(smalls, reverse=True)
bigs = sorted(bigs, reverse=True)
#  print('smalls, bigs', smalls, bigs)

result = 10**13
for i in range(1, N+1):
    #  print('i', i)
    # i は6だけで払う分
    small_n = i
    big_n = N - i

    small_idx = 0
    big_idx = 0

    small_count, big_count = 0, 0
    while small_n != 0:
        if smalls[small_idx] > small_n:
            small_idx += 1
            continue
        small_n -= smalls[small_idx]
        small_count += 1

    while big_n != 0:
        if bigs[big_idx] > big_n:
            big_idx += 1
            continue
        big_n -= bigs[big_idx]
        big_count += 1
    #  print('small_count, big_count', small_count, big_count)
    result = min(result, small_count+big_count)

print(result)

Submission status: Wrong Answer

Solution code:
import math

def A():
    x, a, b = [int(x) for x in input().split()]
    if abs(x-a) < abs(x-b):
        print('A')
    else:
        print('B')
def B():
    S = input()
    alphabet = [False for x in range(26)]
    for char in S:
        i = ord(char) - ord('a')
        alphabet[i] = True
    printed = False
    for i in range(len(alphabet)):
        if alphabet[i] == False:
            print(chr(ord('a')+i))
            printed = True
            break
    if printed == False:
        print("None")
def C():
    n = int(input())
    kazu = sorted([1] + [pow(6, x+1) for x in range(6)]+ [pow(9, x+1) for x in range(5)])
    stack = [(n, 0)]
    m = 9999999999
    while len(stack) > 0:
        node = stack.pop()
        for x in kazu:
            if x <= node[0]:
                if node[0] % x == 0:
                    m = min(m, node[1] + node[0] // x)
                else:
                    stack.append((node[0] % x, node[1] + node[0] // x))
    print(m)
C()

Submission status: Wrong Answer

Solution code:
import math

def A():
    x, a, b = [int(x) for x in input().split()]
    if abs(x-a) < abs(x-b):
        print('A')
    else:
        print('B')
def B():
    S = input()
    alphabet = [False for x in range(26)]
    for char in S:
        i = ord(char) - ord('a')
        alphabet[i] = True
    printed = False
    for i in range(len(alphabet)):
        if alphabet[i] == False:
            print(chr(ord('a')+i))
            printed = True
            break
    if printed == False:
        print("None")
def C():
    n = int(input())
    kazu = sorted([1] + [pow(6, x+1) for x in range(6)]+ [pow(9, x+1) for x in range(5)])
    stack = [(n, 0)]
    m = 9999999999
    while len(stack) > 0:
        node = stack.pop()
        for x in kazu:
            if x <= node[0]:
                if node[0] % x == 0:
                    m = min(m, node[1] + node[0] // x)
                else:
                    stack.append((node[0] % x, node[1] + node[0] // x))
        print(stack)
        print(m)
    print(m)
C()

Submission status: Wrong Answer

Solution code:
n=int(input())
dp=[i for i in range(n+1)]
lw=[6,9]
for w in lw:
    k=1
    while w**k<=n:
        q=w**k
        for j in range(n+1-q):
            dp[j+q]=min(dp[j]+1,dp[j+q])
            if j==q*w:
                break
        k+=1
print(dp[n])

Submission status: Wrong Answer

Solution code:
n=int(input())
dp=[i for i in range(n+1)]
lw=[6,9]
for w in lw:
    k=0
    while w**k<=n:
        k+=1
        q=w**k
        for j in range(n+1-q):
            dp[j+q]=min(dp[j]+1,dp[j+q])
            if j==q*w:
                break
print(dp[n])

Submission status: Wrong Answer

Solution code:
n=int(input())
dp=[i for i in range(n+1)]
k=0
lw=[6,9]
for w in lw:
    while w**k<=n:
        k+=1
        q=w**k
        for j in range(n+1-q):
            dp[j+q]=min(dp[j]+1,dp[j+q])
            if j==q*w:
                break
print(dp[n])

Submission status: Wrong Answer

Solution code:
n=int(input())
dp=[i for i in range(n+1)]
k=0
lw=[6,9]
for w in lw:
    while w**k<=n:
        k+=1
        q=w**k
        for j in range(n+1-q):
            dp[j+q]=min(dp[j]+1,dp[j+q])
            if j==q*(w-1):
                break
print(dp[n])

Submission status: Wrong Answer

Solution code:
def min_num(x,n):
    num = 6
    while(num>0):
        if 9**num < n:
            n -= 9**num
            x += 1
        elif 6**num < n:
            n -= 6**num
            x += 1
        elif num==1:
            n -= 1
            x += 1
        num -= 1
    if n == 0:
        return x
    else:
        return min_num(x,n)

n=int(input())
result = min_num(0,n)
print(str(result))

Submission status: Wrong Answer

Solution code:
def read():
    return raw_input()


def write(message):
    import sys
    print message
    sys.stdout.flush()


if __name__ == '__main__':
    n = int(read())

    allowed = [1, ]
    spow = 6
    while spow < n:
        allowed.append(spow)
        spow *= 6
    npow = 9
    while npow < n:
        allowed.append(npow)
        npow *= 9

    allowed = allowed[::-1]
    res = {a: 1 for a in allowed}

    def min_ops(N):
        global res
        global allowed
        if N in res:
            return res[N]

        for a in allowed:
            if N - a > 0:
                if N not in res or min_ops(N-a) + 1 < res[N]:
                    res[N] = min_ops(N-a) + 1
        return res[N]

    write(min_ops(n))

Submission status: Wrong Answer

Solution code:
import math
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: Wrong Answer

Solution code:
import math
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))
        return min(dfs(cost+1, N-ret0), dfs(cost+1, N-ret1))

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

Submission status: Wrong Answer

Solution code:
import math
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))
        return min(dfs(cost+1, N-ret0), dfs(cost+1, N-ret1))

N = int(input())

Submission status: Wrong Answer

Solution code:
withdraw = [1]
for i in range(1, 8):
    withdraw.append(6**i)
    withdraw.append(9**i)
withdraw.sort()
choice = len(withdraw)

#withdrawには1回の操作で引き出しうる値が格納されている
#可能な限り大きな数にして失敗するのはいつか
#5:5 6:1 7:2 8:3 9:1 10:2 11:3 12:2 13:3 14:4 15:2 16:3 17:4 18:2...
smalls = [0, 1, 2, 3, 4, 5, 1, 2, 3, 1, 2, 3, 2, 3, 4, 2, 3, 4]
cnt = 0
N = int(input())
while N > 17:
    index = 0
    for i in range(choice):
        if withdraw[i+1] > N:
            index = i
            break
    cnt += 1
    N -= withdraw[index]
print(str(cnt + smalls[N]))

Submission status: Wrong Answer

Solution code:
n = int(input())

dp = [-1]*(n+1)
min_6 = 1
for i in range(1000):
    if n < 6**(i+1):
        min_6 = 6**i
        break
min_9 = 1
for i in range(1000):
    if n < 9**(i+1):
        min_9 = 9**i
        break

init_num = min([min_6, min_9])
dp[init_num] = 1

for i in range(init_num+1,n+1):
    a = []
    a.append(dp[i-1]+1)
    for j in range(1000):
        if i - 6**j >= init_num:
            a.append(dp[i-6**j]+1)
    for j in range(1000):
        if i - 9**j >= init_num:
            a.append(dp[i-9**j]+1)
    dp[i] = min(a)

print(dp[-1])

Submission status: Wrong Answer

Solution code:
n = int(input())

count = 0
while True:
    count += 1
    min_6 = 1
    for i in range(1000):
        if n < 6**(i+1):
            min_6 = 6**i
            break
    
    min_9 = 1
    for i in range(1000):
        if n < 9**(i+1):
            min_9 = 9**i
            break

    n = n - max([1, min_6, min_9])
    if n == 0:
        print(count)
        break

Submission status: Wrong Answer

Solution code:
import itertools as i
n=int(input())
count=[]
def f(x):
    if x==0:
        return count
    b=list(i.takewhile(lambda i:9**i<=x,(i for i in range(100))))[-1]
    c=list(i.takewhile(lambda i:6**i<=x,(i for i in range(100))))[-1]
    if 9**b>6**c:
        count.append(b)
        return f(x-9**b)
    else:
        count.append(c)
        return f(x-6**c)

print(len(f(n)))

Submission status: Wrong Answer

Solution code:
import itertools as i
n=int(input())
count=[]
def f(x):
    if x==0:
        return count
    b=list(i.takewhile(lambda i:9**i<=x,(i for i in range(100))))[-1]
    c=list(i.takewhile(lambda i:6**i<=x,(i for i in range(100))))[-1]
    if 9**b>6**c:
        count.append(b)
        return f(x-9**b)
    else:
        count.append(c)
        return f(x-6**c)

print(f(n))

Submission status: Wrong Answer

Solution code:
def strange_bank(N: int) -> int:
    prices = [1] + \
        [9 ** i for i in range(1, 6)] + \
        [6 ** i for i in range(1, 7)]
    dp = [float('inf')] * (N + 1)
    dp[N] = 0

    for n in range(N, 1, -1):
        for p in prices:
            if p <= N:
                dp[n-p] = min(dp[n] + 1, dp[n-p])

    return dp[0]


if __name__ == "__main__":
    N = int(input())
    ans = strange_bank(N)
    print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import count, takewhile
N = int(input())

def dfs(n, d={}):
  if(n <= 6):
    return n
  if(n in d):
    return d[n]
  mn = max(takewhile(lambda x: x<=n, (9**i for i in count())))
  ms = max(takewhile(lambda x: x<=n, (6**i for i in count())))
  d[n] = min(dfs(n-mn), dfs(n-ms))+1
  return d[n]

print(dfs(N))

Submission status: Wrong Answer

Solution code:
import numpy as np
import math
INF=10**9+7
 
N=int(input())
dp=np.full(N+1,INF)
dp[0]=0

use=[1]
for i in range(1,int(math.log(N,6))+1):
    use.append(6**i)
for i in range(1,int(math.log(N,9))+1):
    use.append(9**i)

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

Submission status: Wrong Answer

Solution code:
import numpy as np
import math
INF=10**9+7
 
N=int(input())
 
dp=np.full(N+1,INF)
dp[0]=0
 
use=[1]
for i in range(1,int(math.log(N,6))+1):
    use.append(6**i)
for i in range(1,int(math.log(N,9))+1):
    use.append(9**i)

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

Submission status: Wrong Answer

Solution code:
import numpy as np
import math
INF=10**9+7

N=int(input())

dp=np.full(N,INF)
dp[0]=1

use=[1]
for i in range(1,int(math.log(N,6))+1):
    use.append(6**i)
for i in range(1,int(math.log(N,9))+1):
    use.append(9**i)

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

Submission status: Wrong Answer

Solution code:
N = int(input())
dp = [0]*100001
L = [1,6,36,216,1296,7776,46656,9,81,729,6561,59049]
for i in range(100001):
    for j in range(len(L)):
        if 1 <= i+L[j] <= 100000:
            if dp[i+L[j]] == 0:
                dp[i+L[j]] = dp[i]+1
print(dp[N])

Submission status: Wrong Answer

Solution code:
n = int(input())
ws = [1]
ws += [6**i for i in range(1, 8)]
ws += [9**i for i in range(1, 6)]
ws = sorted(set(ws))

print(ws)
INF = 10**5
dp = [INF] * (n+1)
dp[0] = 0
for i in range(n+1):
    for w in ws:
        if i + w <= n:
            dp[i+w] = min(dp[i]+1, dp[i+w])
print(dp[-1])

Submission status: Wrong Answer

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

sixes=[6**(i) for i in range(1,7)]
nines=[9**(i) for i in range(1,6)]

for i in range(1,N):
  dp[i+1]=dp[i]+1
  
  for s in sixes:
    if i-s>=0:
      dp[i+1]=min(dp[i+1],dp[i+1-s]+1)
    else:
      break
      
  for n in nines:
    if i-n>=0:
      dp[i+1]=min(dp[i+1],dp[i+1-n]+1)
    else:
      break

print(dp[N])

Submission status: Wrong Answer

Solution code:
import itertools as i
n=int(input())
ans=0
while 1:
    a=list(i.takewhile(lambda i:9**i<=n,(i for i in range(100))))[-1]
    n-=9**a
    ans+=1
    if n==0:
        break
    b=list(i.takewhile(lambda i:9**i<=n,(i for i in range(100))))[-1]
    c=list(i.takewhile(lambda i:6**i<=n,(i for i in range(100))))[-1]
    nb=n-9**b
    nc=n-6**c
    if nb<nc:
        n=nb
    else:
        n=nc
    ans+=1
    if n==0:
        break
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
res = n

for i in range(n):
  cc = 0
  t = i  # 6^pでi円引き出し
  while t > 0:
    cc += t % 6
    t //= 6
  t = n - i  # 9^pで残り引き出し
  while t > 0:
    cc += t % 9
    t //= 9
  if res > cc:
    res = cc
print(res)

Submission status: Wrong Answer

Solution code:
N = int(input())

list_1 = [1]
list_6 = [6**(i+1) for i in range(6)]
list_9 = [9**(i+1) for i in range(5)]
list_169 = list_1+list_6+list_9

list_169 = sorted(list_169, reverse=True)


N_sub = N
d_count = 0
for i in range(len(list_169)):
    while list_169[i] <= N_sub:
        N_sub -= list_169[i]
        d_count += 1


dp = [[100000 for j in range(13)] for i in range(100001)]

def N_mai(N_sub, index, s_count):
    global d_count
    if s_count >= d_count:
        return 100000
    elif N_sub == 0:
        return 0
    elif dp[N_sub][index] != 100000:
        return dp[N_sub][index]
    else:
        if list_169[index] == 1:
            count = N_sub
        elif N_sub >= list_169[index]:
            count = min(N_mai(N_sub - list_169[index], index, s_count+1)+1,
                        N_mai(N_sub - list_169[index], index+1, s_count+1)+1, 
                        N_mai(N_sub, index+1, s_count))
        else:
            count = N_mai(N_sub, index+1, s_count)

        dp[N_sub][index] = count
        return count

print(min(d_count, N_mai(N, 0, 0)))

Submission status: Wrong Answer

Solution code:
N = int(input())

list_1 = [1]
list_6 = [6**(i+1) for i in range(6)]
list_9 = [9**(i+1) for i in range(5)]
list_169 = list_1+list_6+list_9

list_169 = sorted(list_169, reverse=True)


N_sub = N
d_count = 0
for i in range(len(list_169)):
    while list_169[i] <= N_sub:
        N_sub -= list_169[i]
        d_count += 1


dp = [[100000 for j in range(13)] for i in range(100001)]

def N_mai(N_sub, index, s_count):
    global d_count
    if s_count >= d_count:
        return 1000
    elif N_sub == 0:
        return 0
    elif dp[N_sub][index] != 100000:
        return dp[N_sub][index]
    else:
        if list_169[index] == 1:
            count = N_sub
        elif N_sub >= list_169[index]:
            count = min(N_mai(N_sub - list_169[index], index, s_count+1)+1,
                        N_mai(N_sub - list_169[index], index+1, s_count+1)+1, 
                        N_mai(N_sub, index+1, s_count))
        else:
            count = N_mai(N_sub, index+1, s_count)

        dp[N_sub][index] = count
        return count

print(min(d_count, N_mai(N, 0, 0)))

Submission status: Wrong Answer

Solution code:
divs = [9 ** 3, 6 ** 3, 9 ** 2, 6 ** 2, 9, 6, 1]
ans = 0
N = int(input())
for div in divs:
    if N < div:
        continue
    a, b = divmod(N, div)
    ans += a
    if b == 0:
        break
    N = b
print(ans)

Submission status: Wrong Answer

Solution code:
a=int(input())
l=[i for i in range(1,a+1)]
i=1
while 6**i<=a:
    q=6**i
    for x in range(q,a):
        l[x]=min(l[x-q]+1,l[x])
    i+=1
i=1
while 9**i<=a:
    q=9**i
    for x in range(q,a):
        l[x]=min(l[x-q]+1,l[x])
    i+=1
print(l[a-1])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys
from itertools import count, takewhile

def dfs(n, d={}):
  if n < 6:
    return n
  if n in d:
    return d[n]

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


def main():
  input = sys.stdin.readline
  N = int(input())
  print(dfs(N))
  
if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
import sys

def f(n):
  X6 = []
  X9 = []
  for i in range(1, 10):
    if n >= 6**i:
      X6.append(6**i)
    if n >= 9**i:
      X9.append(9**i)
  return X6, X9


def main():
  input = sys.stdin.readline
  N = int(input())
  X6, X9 = f(N)
  X = [1] + X6 + X9
  dp = [0 for _ in range(N+1)]
  for i in range(1, N+1):
    can = []
    for x in X:
      can.append(dp[i-x] + 1)
    dp[i] = min(can)
  print(dp[N])

if __name__ == '__main__':
  main()

Submission status: Wrong Answer

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

n = int(input())

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

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


withdraws.sort(reverse = True)
# print(withdraws)
money = 0
count = 0


# 幅優先探索
'''
que = queue.Queue()

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

            elif money+withdraw in memory:
                pass
            else:
                memory.append(money+withdraw)
                next = (money+withdraw,count+1)
                que.put(next)
'''

# 分割

ans = 10**10
# if n < 6:
#     ans = n
for i in range(n//2):
    t = i
    count = 0
    while t>0:
        count += t%6
        t = t//6
    t = n - i
    while t>0:
        count += t%9
        t = t//9
    # print(ans)
    ans =min(ans,count)

print(ans)

Submission status: Wrong Answer

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

n = int(input())

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

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


withdraws.sort(reverse = True)
# print(withdraws)
money = 0
count = 0


# 幅優先探索
'''
que = queue.Queue()

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

            elif money+withdraw in memory:
                pass
            else:
                memory.append(money+withdraw)
                next = (money+withdraw,count+1)
                que.put(next)
'''

# 分割

ans = 10**10
if n < 6:
    ans = n
for i in range(1,n//2):
    t = i
    count = 0
    while t>0:
        count += t%6
        t = t//6
    t = n - i
    while t>0:
        count += t%9
        t = t//9
    # print(ans)
    ans =min(ans,count)

print(ans)

Submission status: Wrong Answer

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

n = int(input())

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

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


withdraws.sort(reverse = True)
# print(withdraws)
money = 0
count = 0


# 幅優先探索
'''
que = queue.Queue()

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

            elif money+withdraw in memory:
                pass
            else:
                memory.append(money+withdraw)
                next = (money+withdraw,count+1)
                que.put(next)
'''

# 分割

ans = 10**10
for i in range(1,n//2):
    t = i
    count = 0
    while t>0:
        count += t%6
        t = t//6
    t = n - i
    while t>0:
        count += t%9
        t = t//9
    # print(ans)
    ans =min(ans,count)

print(ans)

Submission status: Wrong Answer

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