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:
n=int(input())

def solve():
    inf=10**7
    dp=[inf]*(n+1)
    dp[0]=0
    #まず6だけでDP
    for i in range(1,n+1):
        power=1
        while power<=n:
            dp[i]=min(dp[i],dp[i-power]+1)
            power*=6
    #print(dp)

    #次に9だけでDPして良ければ更新される
    for i in range(1,n+1):
        power2=1
        while power2<=n:
            dp[i]=min(dp[i],dp[i-power2]+1)
            power2*=9
    #print(dp)
    return dp[n]

print(solve())

Submission status: Wrong Answer

Solution code:
# import math
# import itertools
# from collections import deque
# from collections import defaultdict
# import heapq
# import sys
# import numpy as np
# from scipy.special import comb

INF = 100100100


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

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

    for i in range(0, N + 1):
        for nine in range(1, i + 1):
            if i + 9**nine > N:
                break
            memo[i + 9**nine] = min(memo[i + 9**nine], memo[i] + 1)
        for six in range(0, i + 1):
            if i + 6**six > N:
                break
            memo[i + 6**six] = min(memo[i + 6**six], memo[i] + 1)

    print(memo[N])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())

    #6**6=46656, 6**7=279936
    #9**5=59049, 9**6=531441
    list = [1]
    list.extend([6 ** i for i in range(1, 7)])
    list.extend([9 ** i for i in range(1, 6)])

    dp = [float("inf")] * 100001
    dp[0] = 0

    for i in range(N+1):
        for j in list:
            if i + j >= 100000:
                continue
            else:
                dp[i+j] = min(dp[i+j], dp[i]+1)

    print(dp[N])

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())
N = I()
dp = [float('INF')]*(N+1)
for i in range(1,N+1):
    dp[i] = i
    num6,num9 = 6,9
    while 0<=i-num6<=N:
        dp[i] = min(dp[i],dp[i-num6]+1)
        num6 *= 6
    while 0<=i-num9<=N:
        dp[i] = min(dp[i],dp[i-num9]+1)
        num9 *= 9
print(dp[-1])

Submission status: Wrong Answer

Solution code:
import math,numpy, collections

n = int(input())
ans = n
cnt = 0
for i in range(n):
    cnt = 0
    x = i
    while x >0:
        cnt += x%6
        x = x//6
    y = n-i
    while y >0:
        cnt += y%9
        y = y//9
    ans = min(ans,cnt)

print(ans)

Submission status: Wrong Answer

Solution code:
l6=[6**i for i in range(9)]
l9=[9**i for i in range(8)]
n=int(input())
p=[0,0,0]
nn=[n,n,n]
for i in sorted(set(l6)|set(l9),reverse=True):
    t,nn[0]=divmod(nn[0],i)
    p[0]+=t
for i in l6[::-1]:
    t,nn[1]=divmod(nn[1],i)
    p[1]+=t
for i in l9[::-1]:
    t,nn[2]=divmod(nn[2],i)
    p[2]+=t
print(min(p))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# hello worldと表示する
#dpでできないかな？
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n=I()
lis6=[]
lis9=[]
i=0
while 6**i<10**6:
    lis6.append(6**i)
    i+=1
j=0
while 9**j<10**6:
    lis9.append(9**j)
    j+=1
lis6=list(reversed(lis6))
lis9=list(reversed(lis9))
#print(lis6)
#print(lis9)
def six(y):
    for s in lis6:
        if s<=y:
            a=y%s
            b=y//s
            break
    return a,b
def nine(y):
    for s in lis9:
        if s<=y:
            a=y%s
            b=y//s
            break
    return a,b
#print(nine(16))
ans=[]
q=deque([[n,0]])
while q:
    c,d=q.popleft()
    #print(c,d)
    u,w=six(c)
    #print(u,w)
    if u==0:
        ans.append(d+w)
    else:
        q.append([u,d+w])
    v,x=nine(c)
    #print(v,x)
    if v==0:
        ans.append(d+x)
    else:
        q.append([v,d+x])
#print(q)
print(min(ans))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import math
# n進数の各位の和
def base_10_n(x,n):
    if x == 0:
        return 0
    tmpx = x
    a = int(math.log(x,n))
    ans = 0
    for i in range(a,-1,-1):
        ans += tmpx // n**i
        tmpx %= n**i
    ans += tmpx
    return ans

def main():
    N = int(input())
    ans = 10**12
    for j in range(N+1):
        c = base_10_n(N-j,6)
        d = base_10_n(j,9)
        ans = min(ans, c+d)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import math
# n進数の各位の和
def base_10_n(x,n):
    if x == 0:
        return 0
    tmpx = x
    a = int(math.log(x,n))
    ans = 0
    for i in range(a,-1,-1):
        ans += tmpx // n**i
        tmpx %= n**i
    ans += tmpx
    return ans

def main():
    N = int(input())
    ans = N
    for j in range(N+1):
        c = base_10_n(N-j,6)
        d = base_10_n(j,9)
        ans = min(ans, c+d)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import math
# n進数の各位の和
def base_10_n(x,n):
    if x == 0:
        return 0
    tmpx = x
    a = int(math.log(x,n))
    ans = 0
    for i in range(a,-1,-1):
        ans += tmpx // n**i
        tmpx %= n**i
    ans += tmpx
    return ans

def main():
    N = int(input())
    ans = min(base_10_n(N,6), base_10_n(N,9))
    for j in range(1, N):
        c = base_10_n(N-j,6)
        d = base_10_n(j,9)
        ans = min(ans, c+d)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import math
# n進数の各位の和
def base_10_n(x,n):
    if x == 0:
        return 0
    tmpx = x
    a = int(math.log(x,n))
    ans = 0
    for i in range(a,-1,-1):
        ans += tmpx // n**i
        tmpx %= n**i
    ans += tmpx
    return ans

def main():
    N = int(input())
    ans = min(base_10_n(N,6), base_10_n(N,9))
    for j in range(1, N//9+1):
        c = base_10_n(N-9*j,6)
        d = base_10_n(9*j,9)
        ans = min(ans, c+d)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import math
# n進数の各位の和
def base_10_n(x,n):
    tmpx = x
    a = int(math.log(x,n))
    ans = 0
    for i in range(a,-1,-1):
        ans += tmpx // n**i
        tmpx %= n**i
    ans += tmpx
    return ans

def main():
    N = int(input())
    ans = min(base_10_n(N,6), base_10_n(N,9))
    for j in range(1, (N-1)//9+1):
        c = base_10_n(N-9*j,6)
        d = base_10_n(9*j,9)
        ans = min(ans, c+d)

    for j in range(1, (N-1)//6+1):
        c = base_10_n(N-6*j,9)
        d = base_10_n(6*j,6)
        ans = min(ans, c+d)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import math
# n進数の各位の和
def base_10_n(x,n):
    tmpx = x
    a = int(math.log(x,n))
    ans = 0
    for i in range(a,-1,-1):
        ans += tmpx // n**i
        tmpx %= n**i
    ans += tmpx
    return ans

def main():
    N = int(input())
    ans = min(base_10_n(N,6), base_10_n(N,9))
    for j in range(1, (N-1)//9+1):
        c = base_10_n(N-9*j,6)
        d = base_10_n(9*j,9)
        ans = min(ans, c+d)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import math
# n進数の各位の和
def base_10_n(x,n):
    tmpx = x
    a = int(math.log(x,n))
    ans = 0
    for i in range(a,-1,-1):
        ans += tmpx // n**i
        tmpx %= n**i
    ans += tmpx
    return ans

def main():
    N = int(input())
    ans = base_10_n(N,6)
    for j in range(1, (N-1)//9+1):
        c = base_10_n(N-9*j,6)
        d = base_10_n(9*j,9)
        ans = min(ans, c+d)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import math
# n進数の各位の和
def base_10_n(x,n):
    a = int(math.log(x,n))
    ans = 0
    for i in range(a,-1,-1):
        ans += x // n**i
        x %= n**i
    ans += x
    return ans

def main():
    N = int(input())
    ans = base_10_n(N,6)
    for j in range(1, N//9):
        c = base_10_n(N-9*j,6)
        d = base_10_n(9*j,9)
        ans = min(ans, c+d)
    print(ans)
    # print(base_10_n(-1,6))
    # print([i for i in range(2,-1,-1)])

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import math
# n進数の各位の和
def base_10_n(x,n):
    a = int(math.log(x,n))
    ans = 0
    for i in range(a,-1,-1):
        ans += x // n**i
        x %= n**i
    ans += x
    return ans

def main():
    N = int(input())
    ans = base_10_n(N,6)
    for j in range(1, N//6 ):
        c = base_10_n(N-6*j,6)
        d = base_10_n(6*j,9)
        ans = min(ans, c+d)
    print(ans)
    # print(base_10_n(-1,6))
    # print([i for i in range(2,-1,-1)])

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import math
# n進数の各位の和
def base_10_n(x,n):
    a = int(math.log(x,n))
    ans = 0
    for i in range(a,-1,-1):
        ans += x // n**i
        x %= n**i
    ans += x
    return ans

def main():
    N = int(input())
    ans = base_10_n(N,6)
    for j in range(1, N//18 ):
        c = base_10_n(N-18*j,6)
        d = base_10_n(18*j,9)
        ans = min(ans, c+d)
    print(ans)
    # print(base_10_n(-1,6))
    # print([i for i in range(2,-1,-1)])

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N=int(input())

#1*a+(6^b1)*b+(9^c1)*c
list=[99999]*(N+1)
list[0]=0
list[1]=1
#1回でいけるところをあらかじめ記入
max6end =True
i=0
while max6end:
    if N <= 6**i :
        max6=i
        max6end=False
    i+=1
max9end =True
i=0
while max9end:
    if N <= 9**i :
        max9=i
        max9end=False
    i+=1
    
print ("max6=%d max9=%d" % (max6,max9))
for n in range(1,N+1):
    list[n]=list[n-1]+1
    for i in range(1,max6+1):
        if n < 6**i:
            break
        else:
            if list[n] >= list[n-6**i]+1:
                list[n]=list[n-6**i]+1
    for i in range(1,max9+1):
        if n < 9**i:
            break
        else:
            if list[n] >= list[n-9**i]+1:
                list[n]=list[n-9**i]+1
print(list)

Submission status: Wrong Answer

Solution code:
N = int(input())
tannis = [1]

i = 1
while 6**i < N:
    tannis.append(6**i)
    i += 1

i = 1
while 9**i < N:
    tannis.append(9**i)
    i += 1

dp = [float('inf') for _ in range(N+1)]
dp[0] = 0

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

#print(dp)
print(dp[N])

Submission status: Wrong Answer

Solution code:
N = int(input())
tannis = [1]

i = 1
while 6**i < N:
    tannis.append(6**i)
    i += 1

i = 1
while 9**i < N:
    tannis.append(9**i)
    i += 1

dp = [float('inf') for _ in range(2*(N+1))]
dp[1] = 1

for i in range(2, N+1):
    for t in tannis:
        dp[i] = min(dp[i], dp[i-t]+1)

print(dp[N])

Submission status: Wrong Answer

Solution code:
N = int(input())

tannis = [1]

i = 1
while 6**i < N:
    tannis.append(6**i)
    i += 1

i = 1
while 9**i < N:
    tannis.append(9**i)
    i += 1

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

count = 0
i = 0
while N > 0:
    if N >= tannis[i]:
        count += N // tannis[i]
        N = N % tannis[i]
    else:
        i += 1

print(count)

Submission status: Wrong Answer

Solution code:
import math

n = int(input())
cnt = 0
while n!=0:
    cnt+=1
    n -= max(6**int(math.log(n,6)),9**int(math.log(n,9)))

print(cnt)

Submission status: Wrong Answer

Solution code:
from collections import deque
from math import log


def main():
  n = int(input())
  
  q = deque()
  q.append((n, 0))
  
  while len(q) > 0:
    node = q.popleft()
    amount = node[0]
    
    if amount < 6:
      print(node[1] + amount)
      return
    elif amount > 0:
      log9_fl = int(log(amount, 9))
      log6_fl = int(log(amount, 6))
      
      q.append((amount - 9 ** log9_fl, node[1] + 1))
      q.append((amount - 6 ** log6_fl, node[1] + 1))
      
  
if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
from collections import deque
from math import log


def main():
  n = int(input())
  
  q = deque()
  q.append((n, 0))
  
  while len(q) > 0:
    node = q.popleft()
    amount = node[0]
    
    if amount == 0:
      print(node[1])
      return
    elif amount > 0:
      log9_fl = int(log(amount, 9))
      log6_fl = int(log(amount, 6))
      
      q.append((amount - 9 ** log9_fl, node[1] + 1))
      q.append((amount - 6 ** log6_fl, node[1] + 1))
      q.append((amount - 1, node[1] + 1))
      
  
if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
from math import log


def count_time(amount):
  if amount < 6:
    return amount
  
  log9 = log(amount, 9)
  log6 = log(amount, 6)
  
  if 9 ** int(log9) >= 6 ** int(log6):
    return 1 + count_time(amount - 9 ** int(log9))
  else:
    return 1 + count_time(amount - 6 ** int(log6))


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


if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
def checkmin(i):
    six_k = 1
    nine_k = 1
    list_before_compare = []
    list_before_compare.append(dp_table[i])
    
    #1円引き出したとき
    list_before_compare.append(dp_table[i-1] + 1)
    
    #6のべき乗の引き出し
    while 6**six_k <= i+1:
        list_before_compare.append(dp_table[i-6**six_k] + 1)
        six_k += 1
    
    #9のべき乗の引き出し
    while 9**nine_k <= i+1:
        list_before_compare.append(dp_table[i-9**nine_k] + 1)
        nine_k += 1

    return min(list_before_compare)    

n = int(input())

dp_table = [float("inf")] * n

#1円になるための取り出し方は1通りのみ→最小値は1
dp_table[0] = 1

for i in range(1,n):
    dp_table[i] = checkmin(i)

print(dp_table[-1])

Submission status: Wrong Answer

Solution code:
N = int(input())
print(1)

Submission status: Wrong Answer

Solution code:
N = int(input())

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

memo[0] = 0
memo[1] = 1
# tmp = min(5, N)
# for i in range(tmp+1):
#     memo[i] = i

exp_sixs = []
exp_nines = []

for i in range(1, 100000):
    if 6 ** i <= N:
        exp_sixs.append(6**i)
    else:
        break

for i in range(1, 100000):
    if 9 ** i <= N:
        exp_nines.append(9**i)
    else:
        break

# print(exp_sixs)
# print(exp_nines)
for exp_six  in exp_sixs:
    memo[exp_six] = 1

for exp_nine in exp_nines:
    memo[exp_nine] = 1

for i in range(1, N+1):
    #1つ前の値から出した値
    one_result = memo[i-1] + 1

    #6の累乗分前の値から出した値
    six_result = N+1
    for exp_six in exp_sixs:
        try:
            six_result = min(six_result, memo[i-exp_six] + 1)
        except:
            break

    #9の累乗分前の値から出した値
    nine_result = N+1
    for exp_nine in exp_nines:
        try:
            nine_result = min(nine_result, memo[i-exp_nine] + 1)
        except:
            break
    memo[i] = min(one_result, six_result, nine_result)

print(memo[N])

Submission status: Wrong Answer

Solution code:
N = int(input())

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

tmp = min(5, N)
for i in range(tmp+1):
    memo[i] = i

exp_sixs = []
exp_nines = []

for i in range(1, 100000):
    if 6 ** i <= N:
        exp_sixs.append(6**i)
    else:
        break
for i in range(1, 100000):
    if 9 ** i <= N:
        exp_nines.append(9**i)
    else:
        break

for exp_six  in exp_sixs:
    memo[exp_six] = 1

for exp_nine in exp_nines:
    memo[exp_nine] = 1

for i in range(tmp, N+1):
    #1つ前の値から出した値
    one_result = memo[i-1] + 1

    #6の累乗分前の値から出した値
    six_result = N+1
    for exp_six in exp_sixs:
        try:
            six_result = min(six_result, memo[i-exp_six] + 1)
        except:
            break

    #9の累乗分前の値から出した値
    nine_result = N+1
    for exp_nine in exp_nines:
        try:
            nine_result = min(nine_result, memo[i-exp_nine] + 1)
        except:
            break
    memo[i] = min(one_result, six_result, nine_result)

print(memo[N])

Submission status: Wrong Answer

Solution code:
N = int(input())

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

tmp = min(5, N)
for i in range(tmp+1):
    memo[i] = i

exp_sixs = []
exp_nines = []

for i in range(100000):
    if 6 ** i <= N:
        exp_sixs.append(6**i)
    else:
        break
for i in range(100000):
    if 9 ** i <= N:
        exp_nines.append(9**i)
    else:
        break

for i in exp_sixs:
    memo[i] = 1

for i in exp_nines:
    memo[i] = 1

for i in range(tmp, N+1):
    #1つ前の値から出した値
    one_result = memo[i-1] + 1

    #6の累乗分前の値から出した値
    six_result = N+1
    for exp_six in exp_sixs:
        try:
            six_result = min(six_result, memo[i-exp_six] + 1)
        except:
            break

    #9の累乗分前の値から出した値
    nine_result = N+1
    for exp_nine in exp_nines:
        try:
            nine_result = min(nine_result, memo[i-exp_nine] + 1)
        except:
            break
    memo[i] = min(one_result, six_result, nine_result)

print(memo[N])

Submission status: Wrong Answer

Solution code:
N = int(input())

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

tmp = min(5, N)
for i in range(tmp+1):
    memo[i] = i

exp_sixs = []
exp_nines = []

for i in range(100000):
    if 6 ** i <= N:
        exp_sixs.append(6**i)
    else:
        break
for i in range(100000):
    if 9 ** i <= N:
        exp_nines.append(9**i)
    else:
        break

for i in exp_sixs:
    memo[i] = 1

for i in exp_nines:
    memo[i] = 1

for i in range(7, N+1):
    #1つ前の値から出した値
    one_result = memo[i-1] + 1

    #6の累乗分前の値から出した値
    six_result = N+1
    for exp_six in exp_sixs:
        try:
            six_result = min(six_result, memo[i-exp_six] + 1)
        except:
            break

    #9の累乗分前の値から出した値
    nine_result = N+1
    for exp_nine in exp_nines:
        try:
            nine_result = min(nine_result, memo[i-exp_nine] + 1)
        except:
            break
    memo[i] = min(one_result, six_result, nine_result)

print(memo[N])

Submission status: Wrong Answer

Solution code:
N = int(input())
INF = 10**18
dp = [-1] * (100000 + 1)
dp[0] = 0

V = [1]
i = 1
while 9**i < 100000:
    dp[9**i] = i
    V.append(9**i)
    i += 1
i = 1
while 6**i < 100000:
    dp[6**i] = i
    V.append(6**i)
    i += 1
# print('V', V)
# print('dp', dp[:15])
for i in range(1, 100000 + 1):
    if dp[i] != -1:
        continue
    _min = INF
    for v in V:
        if i - v < 0:
            continue
        _min = min(_min, dp[i - v] + 1)
    dp[i] = _min

print(dp[N])

Submission status: Wrong Answer

Solution code:
n = int(input())
dp = [float('inf')]*n
amt = [1] + [6**i for i in range(1, 6)] + [9**i for i in range(1, 6)]
for a in amt:
    if a-1 < n:
        dp[a-1] = 1
for i in range(n):
    for j in amt:
        if i+j < n:
            dp[i+j] = min(dp[i+j], dp[i]+1)
print(dp[-1])

Submission status: Wrong Answer

Solution code:
N = int(input())
withdrawal_amount_list = sorted(
    [9**3, 9**2, 9, 6**3, 6**2, 6, 1], reverse=True)
count = 0
for price in withdrawal_amount_list:
    if N >= price:
        count += (N // price)
        N %= price
print(count)

Submission status: Wrong Answer

Solution code:
n = int(open(0).read())
A = [1] + [6**i for i in range(1, 7)] + [9**i for i in range(1, 6)]
dp = [0] * (10**6 + 1)
dp[1] = 1
for i in range(2, n+1):
    dp[i] = min(dp[i-a]+1 for a in A if i>a)
for a in A:
    dp[a] = 1
print(dp[n])

Submission status: Wrong Answer

Solution code:
import numpy as np
n = int(input())
six, nine = map(int, np.floor(np.log(n) / np.log([6,9])))
d = np.ones(n + 1) * n
d[0] = 0
d[1] = 1
for i in range(1, n + 1):
    nums = [i - 9 ** j  for j in range(1, nine + 1) if i >= 9 ** j] + \
    [i - 6 ** j for j in range(1, six + 1) if i >= 6 ** j] + [i - 1]
    d[i] = min(d[i], np.min(d[nums] + 1))
print(int(d[-1]))

Submission status: Wrong Answer

Solution code:
import math
import numpy as np
n = int(input())
six = math.floor(math.log(n) / math.log(6))
nine = math.floor(math.log(n) / math.log(9))
d = np.ones(n + 1) * n
d[0] = 0
d[1] = 1
for i in range(1, n + 1):
    nums = [i - pow(9, j)  for j in range(1, nine + 1) if i >= pow(9, j)] + \
    [i - pow(6, j) for j in range(1, six + 1) if i >= pow(6, j)] + [i - 1]
    d[i] = min(d[i], np.min(d[nums] + 1))
print(int(d[-1]))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

bt = set()
for i in range(1, 100):
    if 6**i > N:
        break
    bt.add(6**i)

for i in range(1, 100):
    if 9**i > N:
        break
    bt.add(9**i)

bt = sorted(bt)

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

Submission status: Wrong Answer

Solution code:
N = int(input())
count = 0

values = [1]
# 金額のパターンを設定
for i in range(1, 7):
    values.append(6**i)
    values.append(9**i)

values.sort()

# dpの初期化
dp =  [99999999] * (N+1)
dp[0] = 0
dp[1] = 1

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

print(dp[N])

Submission status: Wrong Answer

Solution code:
N = int(input())
count = 0

values = [1]
# 金額のパターンを設定
for i in range(1, int(N/9)):
    values.append(6**i)
    values.append(9**i)

values.sort()

# dpの初期化
dp =  [99999999] * (N+1)
dp[0] = 0
dp[1] = 1

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

print(dp[N])

Submission status: Wrong Answer

Solution code:
N = int(input())
six = [6**2,6**3,6**4,6**5]
nine = [9**2,9**3,9**4,9**5,9**6,9**7,9**8]
n_flg = False
for n in nine[::-1]:
    if n <= N:
        n_flg = True
        N -= n
        break

s_flg = False
for s in six[::-1]:
    if s <= N:
        s_flg = True
        N -= s
        break
    
a = N % 9   
b = N // 9

print(a + b + n_flg + s_flg)

Submission status: Wrong Answer

Solution code:
N = int(input())
from math import log

max6 = int(log(N, 6))
max9 = int(log(N, 9))
dp = [10**18]*(N+1)
dp[0] = 0
for i in range(1, N+1):
    dp[i] = dp[i-1]+1
    for j in range(max6+1):
        if 6**j>i:
            break
        dp[i] = min(dp[i-6**j]+1, dp[i])
    for k in range(max9+1):
        if 9**k>i:
            break
        dp[i] = min(dp[i-9**k]+1, dp[i])

print(dp[-1])

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    List = [1]

    for i in range(1, 7):
        List.append(pow(6, i))
        List.append(pow(9, i))

    List.sort()
    dp = [[f_inf for _ in range(n + 1)] for _ in range(len(List))]
    dp[0][0] = 0

    for i in range(len(List)):
        for j in range(1, n + 1):
            if 0 <= j - List[i]:
                dp[i][j] = min(dp[i - 1][j], dp[i][j - List[i]] + 1)
            else:
                dp[i][j] = dp[i - 1][j]

    print(dp[len(List) - 1][n])


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
n = int(input())

import math

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

calc(n,0)

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())

INF = 10**10
dp = [INF] * (n + 1)
dp[0] = 0
dp[1] = 1

num_list = [1]

for i in range(1, 9):
    n1 = 6**i
    n2 = 9**i
    if n1 < n:
        num_list.append(n1)
    if n2 < n:
        num_list.append(n2)

for i in range(0, n):
    for j in num_list:
        if i + j <= n:
            dp[i+j] = min(dp[i+j], dp[i] + 1)

print(dp[n])

Submission status: Wrong Answer

Solution code:
N = int(input())
from math import log

max6 = int(log(N, 6))
max9 = int(log(N, 9))
dp = [10**18]*(N+1)
dp[0] = 0
for i in range(1, N+1):
    dp[i] = min(dp[i-1]+1, dp[i])
    for j in range(max6+1):
        if 6**j>i:
            break
        dp[i] = min(dp[i-6**j]+1, dp[i])
    for k in range(max9+1):
        if 9**k>i:
            break
        dp[i] = min(dp[i-9**k]+1, dp[i])

print(dp[-1])

Submission status: Wrong Answer

Solution code:
n = int(input())

INF = 10**10
dp = [INF] * (n + 1)
dp[0] = 0
dp[1] = 1

num_list = [1]

for i in range(1, 9):
    n1 = 6**i
    n2 = 9**i
    if n1 < n:
        num_list.append(n1)
    if n2 < n:
        num_list.append(n2)

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

print(dp[n])

Submission status: Wrong Answer

Solution code:
n=int(input())
c=[1]
i=1
while (6**i<=100000):
  c.append(6**i)
  i+=1
i=1
while (9**i<100000):
  c.append(9**i)
  i+=1
c.sort()
m=[1]
for i in range(1,n):
  mi=1000000
  for j in range(len(c)):
    if i-c[j]<0:
      break
    if m[i-c[j]]+1<mi:
      mi=m[i-c[j]]+1
  m.append(mi)
print(m[n-1])

Submission status: Wrong Answer

Solution code:
N = int(input())

array = []
cnt6 = 0
while 6**cnt6 < N:
    array.append(6**cnt6)
    cnt6 += 1
    
cnt9 = 0
while 9**cnt9 < N:
    array.append(9**cnt9)
    cnt9 += 1

a = sorted(list(set(array)))
# 最小
dp = [i for i in range(N+1)]
# print(dp)
n = 6
for n in a:
    for i in range(N+1):
        if i+n <= N:
            dp[i+n] = min(dp[i]+1, dp[i+n])
print(dp[N])

Submission status: Wrong Answer

Solution code:
n = int(input())

info = []
for i in range(20):
    v, w = 1, 1 ** i
    info.append((v, w))
    v, w = 1, 6 ** i
    info.append((v, w))
    v, w = 1, 9 ** i
    info.append((v, w))

m = len(info)
INF = 10 ** 8
dp = [[INF] * (n + 1) for i in range(m + 1)]
dp[0][0] = 0

for i in range(m):
    v, w = info[i]
    for j in range(n + 1):
        dp[i + 1][j] = min(dp[i][j], dp[i + 1][j])
        if j - w >= 0:
            dp[i + 1][j] = min(dp[i][j - w] + v, dp[i + 1][j])
        
print(dp[-1][-1])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n=int(input())
dp=[float("inf")]*(n+1)
dp[0]=0
for i in range(n-1):
    for j in range(1,7):
        j=6**j
        if i+j<n:
            dp[i+j]=min(dp[i+j],dp[i]+1)
    for j in range(1,6):
        j=9**j
        if i+j<n:
            dp[i+j]=min(dp[i+j],dp[i]+1)
    dp[i+1]=min(dp[i+1],dp[i]+1)
    

print(dp[-1])

Submission status: Wrong Answer

Solution code:
n=int(input())
dp=[float("inf")]*n
dp[0]=1
for i in range(n-1):
    for j in range(1,7):
        j=6**j
        if i+j<n:
            dp[i+j]=min(dp[i+j],dp[i]+1)
    for j in range(1,6):
        j=9**j
        if i+j<n:
            dp[i+j]=min(dp[i+j],dp[i]+1)
    dp[i+1]=min(dp[i+1],dp[i]+1)
    

print(dp[-1])

Submission status: Wrong Answer

Solution code:
def dfs(a,b,c):
  todo=[[]]
  ret=[]
  while len(todo)>0:
    t=todo.pop()
    l=len(t)
    if l==a:
      ret.append(t)
    else:
      s=0
      for i in range(1,l+1):
        s+=6**i*t[i-1]
      for i in range(b+1):
        if s+6**(l+1)*i<=c:
          tc=t.copy()
          tc.append(i)
          todo.append(tc)
  return ret
a=6
b=5
c=int(input())
l=dfs(a,b,c)
ans=c
#print(l)
for li in l:
  ansi=sum(li)
  now=c-sum([6**(i+1)*li[i]for i in range(len(li))])
  for i in range(1,6):
    ansi+=now%9
    now//=9
  ans=min(ans,ansi)
print(ans)

Submission status: Wrong Answer

Solution code:
def dfs(a,b,c):
  todo=[[]]
  ret=[]
  while len(todo)>0:
    t=todo.pop()
    l=len(t)
    if l==a:
      ret.append(t)
    else:
      s=0
      for i in range(1,l+1):
        s+=6**i*t[i-1]
      for i in range(b+1):
        if s+6**(l+1)*i<=c:
          tc=t.copy()
          tc.append(i)
          todo.append(tc)
  return ret
a=6
b=5
c=int(input())
l=dfs(a,b,c)
ans=c
for li in l:
  ansi=sum(li)
  now=c-sum([6**(i+1)*li[i]for i in range(len(li))])
  for i in range(1,6):
    ansi+=now%9
    now//=9
  ans=min(ans,ansi)
print(ans)

Submission status: Wrong Answer

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

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