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())
ans=0
while N:
    if 12<=N<=14:
        N-=12
        ans+=2
    if 864<=N<=944:
        N-=864
        ans+=4
    if 1458<=N<=1511:
        N-=1458
        ans+=2
    if 7857<=N<=7937:
        N-=7857
        ans+=2
    if 13122<=N<=14336:
        N-=13122
        ans+=2
    if 93312<=N:
        N-=93312
        ans+=2
    i=0
    while 9**i<=N:
        i+=1
    i-=1
    j=0
    while 6**j<=N:
        j+=1
    j-=1
    N-=max(9**i,6**j)
    ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
ans=0
while N:
    if 12<=N<=14:
        N-=12
        ans+=2
    if 1458<=N<=1511:
        N-=1458
        ans+=2
    if 7857<=N<=7937:
        N-=7857
        ans+=2
    if 13122<=N<=14336:
        N-=13122
        ans+=2
    if 93312<=N:
        N-=93312
        ans+=2
    i=0
    while 9**i<=N:
        i+=1
    i-=1
    j=0
    while 6**j<=N:
        j+=1
    j-=1
    N-=max(9**i,6**j)
    ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
ans=0
while N:
    if 12<=N<=14:
        N-=12
        ans+=2
    if 1458<=N<=1511:
        N-=1458
        ans+=2
    if 13122<=N<=14336:
        N-=13122
        ans+=2
    if 93312<=N:
        N-=93312
        ans+=2
    i=0
    while 9**i<=N:
        i+=1
    i-=1
    j=0
    while 6**j<=N:
        j+=1
    j-=1
    N-=max(9**i,6**j)
    ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
ans=0
while N:
    if 12<=N<=14:
        N-=6
        ans+=1
    if 1458<=N<=1511:
        N-=729
        ans+=1
    if 13122<=N<=14336:
        N-=6561
        ans+=1
    i=0
    while 9**i<=N:
        i+=1
    i-=1
    j=0
    while 6**j<=N:
        j+=1
    j-=1
    N-=max(9**i,6**j)
    ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
ans=0
while N:
    if 12<=N<=14:
        N-=6
        ans+=1
    if 1458<=N<=1511:
        N-=729
        ans+=1
    i=0
    while 9**i<=N:
        i+=1
    i-=1
    j=0
    while 6**j<=N:
        j+=1
    j-=1
    N-=max(9**i,6**j)
    ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
ans=0
while N:
    if 12<=N<=14:
        N-=6
        ans+=1
    if 1458<=N<=2024:
        N-=729
        ans+=1
    i=0
    while 9**i<=N:
        i+=1
    i-=1
    j=0
    while 6**j<=N:
        j+=1
    j-=1
    N-=max(9**i,6**j)
    ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
ans=0
while N:
    if 12<=N<=14:
        N-=6
        ans+=1
    i=0
    while 9**i<=N:
        i+=1
    i-=1
    j=0
    while 6**j<=N:
        j+=1
    j-=1
    N-=max(9**i,6**j)
    ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
ans=0
while n>5:
  i=0
  j=0
  while n>=9**i:
    i+=1
  while n>=6**j:
    j+=1
  if 9**i>=6**j:
    n=n-9**(i-1)
  else:
    n=n-6**(j-1)
  ans+=1
print(ans+n//1)

Submission status: Wrong Answer

Solution code:
N = int(input())
ans = float('inf')
ls = []
l = [1]
tmp = 6
while tmp <= 100000:
    l += [tmp]
    tmp *= 6

tmp = 9
while tmp <= 100000:
    l += [tmp]
    tmp *= 9

dp = [float('inf')]*(N+1)
dp[1] = 1
for i in range(N+1):
    for n in l:
        if i-n>=0:
            dp[i] = min(dp[i], dp[i-n]+1)
print(dp[N])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys
import math
N = int(sys.stdin.readline().rstrip())

def create_money(i):
    money = []
    tmp = 1
    for _ in range(math.floor(math.log(N, i))):
        tmp *= i
        money.append(tmp)
    
    return money

money = [1]
money += create_money(6)
money += create_money(9)

dp = [[10**18] * (N + 1) for _ in range(len(money) + 1)]
dp[0][0] = 0

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

print(dp[len(money)][N])

Submission status: Wrong Answer

Solution code:
import sys
import math
N = int(sys.stdin.readline().rstrip())

def create_money(i):
    money = []
    tmp = 1
    for _ in range(math.floor(math.log(N, i))):
        tmp *= i
        money.append(tmp)
    
    return money

money = [1]
money += create_money(6)
money += create_money(9)

dp = [[10**18] * (N + 1) for _ in range(len(money) + 1)]
dp[0][0] = 0

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

print(dp[i][N])

Submission status: Wrong Answer

Solution code:
import sys
import math
N = int(sys.stdin.readline().rstrip())

def create_money(i):
    money = []
    tmp = 1
    for _ in range(math.floor(math.log(N, i))):
        tmp *= i
        money.append(tmp)
    
    return money

money = [1]
money += create_money(6)
money += create_money(9)
money.sort()
money = money[::-1]

dp = [[10**18] * (N + 1) for _ in range(len(money) + 1)]
dp[0][0] = 0

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

print(dp[i][N])

Submission status: Wrong Answer

Solution code:
import sys
import math
N = int(sys.stdin.readline().rstrip())

def create_money(i):
    money = []
    tmp = 1
    for _ in range(math.floor(math.log(N, i))):
        tmp *= i
        money.append(tmp)
    
    return money

money = [1]
money += create_money(6)
money += create_money(9)
money.sort()
money = money[::-1]

dp = [[10**18] * (N + 1) for _ in range(len(money) + 1)]
dp[0][0] = 0

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

ans = 10**18
for i in range(len(money) + 1):
    if dp[i][N] > 0:
        ans = min(ans, dp[i][N])

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
N = int(sys.stdin.readline().rstrip())

def create_money(i):
    money = []
    tmp = 1
    for _ in range(math.floor(math.log(N, i))):
        tmp *= i
        money.append(tmp)
    
    return money

money = [1]
money += create_money(6)
money += create_money(9)
money.sort()
money = money[::-1]

dp = [[10**18] * (N + 1) for _ in range(len(money) + 1)]
dp[0][0] = 0

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

print(dp[i][N])

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
#from decimal import *

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

for i in range(2, N+1):
	L = [6**x for x in range(ceil(log2(i)/log2(6)))] + [9**x for x in range(1, ceil(log2(i)/log2(9)))]
	dp[i] = min([dp[i-y] for y in L]) + 1

print(dp[N])

Submission status: Wrong Answer

Solution code:
n = int(input())
dp = [200000] * (n+10)
dp[0] = 0
dp[1] = 1
for i in range(1,n):
    dp[i+1] = min(dp[i+1], dp[i]+1)
    six = 6
    while i + six <= n:
        dp[i+six] = min(dp[i+six], dp[i]+1)
        six *= 6 

    nine = 9
    while i + nine <= n:
        dp[i+nine] = min(dp[i+nine], dp[i]+1)
        nine *= 9

print(dp[n])

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc099/tasks/abc099_c

# DPを考えてみる
# dp[i]: i円を引き出すのに必要な回数
# dp[0] = 1
# dp[1] = 1
# dp[6] の倍数 = 1
# dp[9] の倍数 = 1

# 10万以下でありえる値
# 6**7 # 279936
# 9**6 # 531441
c = [1] + [6**i for i in range(1,7)] + [9**i for i in range(1,6)]

Inf = int(1e18)

n = int(input())
dp = [Inf] * (n + 1)
dp[0] = dp[1] = 1

# 金額毎
for ci in c:
    for i in range(ci, n+1):
        # ある金額のminは，その金額を降ろさないmin + 1回
        # 1000円でc=9の場合，dp[1000] = min(dp[1000], dp[1000-9]+ 1)
        dp[i] = min(dp[i], dp[i-ci] + 1)

print(dp[n])

Submission status: Wrong Answer

Solution code:
def tmp_ans(total_cost, six_cost):
    res = 0
    tmp = n
    t = six_cost
    while t > 0:
        res += t % 6
        t //= 6
    t = total_cost - six_cost
    while t > 0:
        res += t % 9
        t //= 9
    return res

n = int(input())
ans = n
for x in range(n):
    ans = min(ans, tmp_ans(n, x))
print(ans)

Submission status: Wrong Answer

Solution code:
dp=[1000000 for i in range(100010)]
dp[0]=0
for n in range(1,11):
  power=1
  while(power<=n):
    dp[n]=min(dp[n],dp[n-power]+1)
    power*=6
  power=1
  while(power<=n):
    dp[n]=min(dp[n],dp[n-power]+1)
    power*=9

i=int(input())
print(dp[i])

Submission status: Wrong Answer

Solution code:
dp=[0 for i in range(100010)]
dp[0]=0
for n in range(1,100001):
  dp[n]=200000
  power=1
  while(power<=n):
    dp[n]=min(dp[n],dp[n-power]+1)
    power*=6
  while(power<=n):
    dp[n]=min(dp[n],dp[n-power]+1)
    power*=9

n=int(input())
print(dp[n])

Submission status: Wrong Answer

Solution code:
n=int(input())
dp=[0 for i in range(100010)]
dp[0]=0
for i in range(100000):
  dp[i]=200000
  power=1
  while(power<=n):
    dp[n]=min(dp[n],dp[n-power]+1)
    power*=6
  while(power<=n):
    dp[n]=min(dp[n],dp[n-power]+1)
    power*=9

print(dp[n])

Submission status: Wrong Answer

Solution code:
n = int(input())
count = 0
apple = []
for i in range(1, 6):
    apple.append(9**i)
for i in range(1, 7):
    apple.append(6**i)
orange = sorted(apple)
for i in orange[::-1]:
    if n - i <= 0:
        pass
    else:
        count += (n // i)
        n = n % i
print(count + n)

Submission status: Wrong Answer

Solution code:
import sys
n = int(input())
mem = [None]*(n+1)
def DFS(k, d):
    if k<0 or d>1000:
        return 10**9
    if k==0:
        return 0
    if k<6:
        return k
    if mem[k] is not None:
        return mem[k]
    tmp = 10**5
    for i in range(1, 7):
        tmp = min(tmp, DFS(k-6**i, d+1)+1)
    for i in range(1, 6):
        tmp = min(tmp, DFS(k-9**i, d+1)+1)
    mem[k] = tmp
    return tmp
if n<6:
    print(n)
else:
    print(DFS(n, 0))

Submission status: Wrong Answer

Solution code:
import sys
n = int(input())
mem = [None]*(n+1)
def DFS(k, d):
    if k<0 or d>100:
        return 10**9
    if k==0:
        return 0
    if k<6:
        return k
    if mem[k] is not None:
        return mem[k]
    tmp = 10**5
    for i in range(1, 7):
        tmp = min(tmp, DFS(k-6**i, d+1)+1)
    for i in range(1, 6):
        tmp = min(tmp, DFS(k-9**i, d+1)+1)
    mem[k] = tmp
    return tmp
if n<6:
    print(n)
else:
    print(DFS(n, 0))

Submission status: Wrong Answer

Solution code:
n = int(input())

ans = 0
while n > 0:
    i = 0
    while pow(6, i) < n:
        i += 1
    j = 0
    while pow(9, j) < n:
        j += 1
    n -= max(pow(6, max(0, i-1)), pow(9, max(0, j-1)))
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

n = int(input())
def solve(n):
    f = [float('inf') for _ in range(n+1)]
    f[0] = 0
    for i in range(1, n+1):
        f[i] = f[i-1] + 1
        k = 6
        l = 9
        while k <= i:
            f[i] = min(f[i], f[i-k] + 1)
            k *= 6
        while l <= i:
            f[i] = min(f[i], f[i-l] + 1)
            l *= 6
    print(f[n])
solve(n)

Submission status: Wrong Answer

Solution code:
import numpy as np

n = int(input())
i = int(np.log(n) / np.log(6))
j = int(np.log(n) / np.log(9))
f = [float('inf') for _ in range(n+1)]
f[0] = 0
for k in range(1, n+1):
    f[k] = min([f[k-1]] + [f[k-6**(l+1)] for l in range(i)] + [f[k-9**(m+1)] for m in range(j)]) + 1
print(f[n])

Submission status: Wrong Answer

Solution code:
def resolve():
    import sys
    input = sys.stdin.readline
    # 整数 1 つ
    n = int(input())
    # 整数複数個
    # a, b = map(int, input().split())
    # 整数 N 個 (改行区切り)
    # N = [int(input()) for i in range(N)]
    # 整数 N 個 (スペース区切り)
    # N = list(map(int, input().split()))
    # 整数 (縦 H 横 W の行列)
    # A = [list(map(int, input().split())) for i in range(H)]

    Count = [n] * (n+1)
    Count[0] = 0

    import math
    Jmp6 = [6**i for i in range(int(math.log(n, 6)) +1)]
    Jmp9 = [9**i for i in range(int(math.log(n, 9)) +1)]
    Jmp = Jmp6 + Jmp9
#    Jmp = sorted(Jmp)
    del Jmp[0]

    for i in range(1, n+1):
        for x in Jmp:
            if x > i:
                break
            Count[i] = min(Count[i], Count[i-x] +1)
            # if Count[i] > cnt:
            #     Count[i] = cnt

    print(Count[n])
resolve()

Submission status: Wrong Answer

Solution code:
n=int(input())
count=0
if n//9>=1:
  count+=1
if n//6>=1:
  count+=1
count+=n%9%6
print(count)

Submission status: Wrong Answer

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

import sys
# import time
import math
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)



def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1             # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())


    n = ii()

    dp = [i for i in range(n+1)]
    for i in range(6, n+1):
        dp[i] = min(dp[i], dp[i - pow(6, int(math.log(i, 6)))] + 1, dp[i - pow(9, int(math.log(i, 9)))] + 1)    
    # print(dp)
    print(dp[n])



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

import sys
# import time
import math
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)



def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1             # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())


    n = ii()
    dp = [inf] * (n+1)
    for i in range(min(n+1, 6)):
        dp[i] = i
    for i in range(6, n+1):
        m = int(math.log(i, 6))
        for j in range(1, m+1):
            dp[i] = min(dp[i], dp[i - pow(6, j)] + 1)
        m = int(math.log(i, 9))
        for j in range(1, m+1):
            dp[i] = min(dp[i], dp[i - pow(9, j)] + 1)

    
    print(dp[n])


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

import sys
# import time
import math
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)



def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1             # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())


    n = ii()
    dp = [0] * (n+1)
    for i in range(1, min(n+1, 6)):
        dp[i] = i
    for i in range(6, n+1):
        six = pow(6, int(math.log(i, 6)))
        nine = pow(9, int(math.log(i, 9)))
        dp[i] = min(dp[i-six], dp[i-nine]) + 1
    
    print(dp[n])


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N =int(input())
SIX  = [6**i for i in range(1,10)]
NINE = [9**i for i in range(1,10)]
SIX.extend(NINE)
SIX.append(1)
SIX = sorted(SIX,reverse=True)

ans = 99
for s in SIX:
    cnt=0
    if N > s:
        N2 =N-s
    else:
        N2 = N
    for s2 in SIX:
        if N2 >=s2:
        
            P,N2 = divmod(N2,s2)
            cnt+=P
    if cnt <= ans:
        ans = cnt
print(ans+1)

Submission status: Wrong Answer

Solution code:
N =int(input())
SIX  = [6**i for i in range(1,7)]
NINE = [9**i for i in range(1,6)]
SIX.extend(NINE)
SIX.append(1)
SIX = sorted(SIX,reverse=True)

ans = 99
for s in SIX:
    cnt=0
    if N > s:
        N2 =N-s
    else:
        N2 = N
    for s2 in SIX:
        if N2 >=s2:
        
            P,N2 = divmod(N2,s2)
            cnt+=P
    if cnt <= ans:
        ans = cnt
print(ans+1)

Submission status: Wrong Answer

Solution code:
N =int(input())
SIX  = [6**i for i in range(1,7)]
NINE = [9**i for i in range(1,5)]
SIX.extend(NINE)
SIX.append(1)
SIX = sorted(SIX,reverse=True)

ans = 99
for s in SIX:
    cnt=0
    if N > s:
        N2 =N-s
    else:
        N2 = N
    for s2 in SIX:
        if N2 >=s2:
        
            P,N2 = divmod(N2,s2)
            cnt+=P
    if cnt <= ans:
        ans = cnt
print(ans+1)

Submission status: Wrong Answer

Solution code:
N =int(input())
SIX  = [6**i for i in range(1,7)]
NINE = [9**i for i in range(1,5)]
SIX.extend(NINE)
SIX.append(1)
SIX = sorted(SIX,reverse=True)
N2 =N
cnt=0
for s in SIX:
    if N2 >=s:
        
        P,N2 = divmod(N2,s)
        cnt+=P
    
print(cnt)

Submission status: Wrong Answer

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

N = int(input())

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

print(dp[N])

Submission status: Wrong Answer

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

N = int(input())

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

print(dp[N])

Submission status: Wrong Answer

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

N = int(input())

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

print(dp[N])

Submission status: 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<=i:
            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<=i:
            dp[i]=min(dp[i],dp[i-power2]+1)
            power2*=9
    print(dp)
    return dp[n]

print(solve())