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: Accepted

Solution code:
n = int(input())


def saiki(tgt, i, count, ans):
    if i == 0 or tgt == 0:
        ans = min(tgt+count, ans)
        return ans

    num = tgt//temp[i]
    while num >= 0:
        nn = tgt - num*temp[i]
        ans = saiki(nn, i-1, count+num, ans)
        if ans < count+num:
            return ans
        num -= 1
    return ans


temp = [1]
a = 1
while n >= 6**a:
    temp.append(6**a)
    a += 1

b = 1
while n >= 9**b:
    temp.append(9**b)
    b += 1

temp.sort()
#print(temp)
print(saiki(n, len(temp)-1, 0, 10**9))

Submission status: Accepted

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] = 0

# 金額毎
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: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)

N = int(open(0).read())
p = [59049, 46656, 7776, 6561, 1296, 729, 216, 81, 36, 9, 6, 1]

mem = [0] * (N+1)
def dp(n):
    global mem
    if n <= 0:
        return 0
    elif mem[n]:
        return mem[n]
    else:
        mem[n] = min([dp(n-x) + 1 for x in p if n - x >= 0])
        return mem[n]
print(dp(N))

Submission status: Accepted

Solution code:
n = int(input())

# 6**7 # 279936
# 9**6 # 531441
c = [1] + [6**i for i in range(1,7)] + [9**i for i in range(1,6)]
c.sort()
#[1, 6, 9, 36, 81, 216, 729, 1296, 6561, 7776, 46656, 59049]
INF = 10 ** 10

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

for ci in c:
    for i in range(ci, n+1):
        dp[i] = min(dp[i], dp[i-ci] + 1)
print(dp[n])

Submission status: Accepted

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+1):
    ans = min(ans, tmp_ans(n, x))
print(ans)

Submission status: Accepted

Solution code:
# dp
# N円を作るのに最も小さい操作回数

import sys
readline = sys.stdin.readline

N = int(readline())

dp = [i for i in range(N + 1)]

for i in range(len(dp)):
  n = 6
  while i + n < len(dp):
    if dp[i + n] > dp[i] + 1:
      dp[i + n] = dp[i] + 1
    n *= 6
  n = 9
  while i + n < len(dp):
    if dp[i + n] > dp[i] + 1:
      dp[i + n] = dp[i] + 1
    n *= 9
print(dp[N])

Submission status: Accepted

Solution code:
dp=[1000000 for i in range(100010)]
dp[0]=0
for n in range(1,100010):
  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: Accepted

Solution code:
n = int(input())
dp = [i for i in range(n+1)]

for i in range(n):
    dp[i+1] = min(dp[i+1],dp[i] + 1)
    cou = 1
    while True:
        if i + 6**cou <= n:
            dp[i+6**cou] = min(dp[i+6**cou],dp[i]+1)
            cou += 1
        elif i + 6**cou > n:
            break
    cou = 1
    while True:
        if i + 9**cou <= n:
            dp[i+9**cou] = min(dp[i+9**cou],dp[i]+1)
            cou += 1
        elif i + 9**cou > n:
            break
print(dp[n])

Submission status: Accepted

Solution code:
N = int(input())

P = [1]

for i in range(1, N):
    if 6**i > N:
        break
    P.append(6**i)

for i in range(1, N):
    if 9**i > N:
        break
    P.append(9**i)

P.sort()

DP = [float('inf')] * (N + 1)
DP[0] = 0
for i in range(N):
    for p in P:
        if i + p > N:
            break
        DP[i+p] = min(DP[i+p], DP[i] + 1)
print(DP[N])

Submission status: Accepted

Solution code:
n = int(input())

dp = [0 for _ in range(n+1)]

for i in range(1, n+1): # 1円の場合からn円の場合まで繰り返す
    Min = dp[i-1] + 1 # i-1円を引き出してから1円を引き出す場合の引き出し回数の最小値
    j = 1
    while pow(6, j) <= i:
        Min = min(Min, dp[i-pow(6, j)] + 1) # i-6^j円を引き出してから6^j円を引き出す場合の引き出し回数の最小値
        j += 1
    j = 1
    while pow(9, j) <= i:
        Min = min(Min, dp[i-pow(9, j)] + 1) # i-9^j円を引き出してから9^j円を引き出す場合の引き出し回数の最小値
        j += 1
    dp[i] = Min

print(dp[n])

Submission status: Accepted

Solution code:
N = int(input())
A = [1, 6, 6**2, 6**3, 6**4, 6**5, 6**6, 9, 9**2, 9**3, 9**4, 9**5]
dp = [1000000] * 300000
dp[0] = 0

for i in range(N):
    for a in A:
        d = dp[i] + 1
        dp[i + a] = min(dp[i + a], d)

print(dp[N])

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())

dp = [-1]*(N+1)
dp[0] = 0
dp[1] = 1
for i in range(1, N+1):
    if dp[i] == -1:
        dp[i] = dp[i-1] + 1
        k = 6
        while i >= k:
            dp[i] = min(dp[i], dp[i-k]+1)
            k *= 6
        l = 9
        while i >= l:
            dp[i] = min(dp[i], dp[i-l]+1)
            l  *= 9
print(dp[N])

Submission status: Accepted

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

Submission status: Accepted

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 *= 9
    print(f[n])
solve(n)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N = I()

L = set()

for i in range(1000):
  if 6**i <= 100000:
    L.add(6**i)
  else:
    break
for i in range(1000):
  if 9**i <= 100000:
    L.add(9**i)
  else:
    break

count = 1
bag = {N}

while True:
  new_bag = set()
  for i in bag:
    for l in L:
      left = i - l
      if left == 0:
        print(count)
        exit()
      elif left > 0:
        new_bag.add(left)
  bag = new_bag
  count += 1

Submission status: Accepted

Solution code:
N = int(input())

dp = list(range(0, N+1))

for i in range(1, N+1):
    for j in [6, 9]:
        for k in range(1, N):
            if 0 <= i-j**k:
                dp[i] = min(dp[i], dp[i-j**k]+1)
            else:
                break

print(dp[-1])

Submission status: Accepted

Solution code:
N = int(input())

dp = [10**100]*(N + 10**6)
dp[0] = 0
delta = [1, 6, 6**2, 6**3, 6**4, 6**5, 6**6, 9, 9**2, 9**3, 9**4, 9**5]
for i in range(0, N):
    for d in delta:
        dp[i+d] = min(dp[i+d], dp[i] + 1)
print(dp[N])

Submission status: Accepted

Solution code:
n = int(input())
inf = float('inf')
dp = [inf]*(n+1)
dp[0] = 0
a = 1
b = 6
c = 9
for i in range(1,n+1):
    if i>=b*6:
        b*=6
    if i>=c*9:
        c*=9
    if i<6:
        dp[i] = i
    elif i<9:
        dp[i] = min(dp[i],dp[i-b]+1)
    else:
        dp[i] = min(dp[i],dp[i-b]+1,dp[i-c]+1)
print(dp[n])

Submission status: Accepted

Solution code:
from sys import stdin
input = stdin.readline

def VI(N, init=0):
  return [init for _ in range(N)]
def VVI(N, M, init=0):
  return [[init for _ in range(M)] for _ in range(N)]

def VD(N, init=0.0):
  return [init for _ in range(N)]
def VVD(N, M, init=0.0):
  return [[init for _ in range(M)] for _ in range(N)]

def Decimal(x):
  print("{0:.10f}".format(x))

class Pair:
  def __init__(self, x=0, y=0):
    self.first = x
    self.second = y

  def __repr__(self):
    return '{0} {1}'.format(self.first, self.second)

  def __lt__(self, pi):
    return self.first < pi.second

def POW(x, n):
  ret = 1
  while n:
    if n&1:
      ret *= x
    x *= x
    n >>= 1
  return ret

MAX_N = int(1e5+5)

dp = VI(MAX_N, MAX_N)
dp[0] = 0
dp[1] = 1

for i in range(2, MAX_N):
  dp[i] = min(dp[i], dp[i-1]+1)
  for j in range(10):
    six = POW(6, j)
    if six > i:
      break
    else:
      dp[i] = min(dp[i], dp[i-six]+1)

  for j in range(10):
    nine = POW(9, j)
    if nine > i:
      break
    else:
      dp[i] = min(dp[i], dp[i-nine]+1)

N = int(input().rstrip())
print(dp[N])

Submission status: Accepted

Solution code:
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial
from bisect import bisect_left #bisect_left(list, value)
#from fractions import gcd
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

N = int(input())
INF = 10**18

res = 0
dp = [INF]*(10*N)
dp[0] = 0
for i in range(0, N):
    dp[i+1] = min(dp[i+1], dp[i]+1)

    j = 1
    while i+6**j <= N:
        dp[i+6**j] = min(dp[i+6**j], dp[i]+1)
        j += 1

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

print(dp[N])

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()

from collections import defaultdict, deque, Counter
from sys import exit
import heapq
import math
import fractions
import copy
from itertools import permutations
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

N = getN()

num = [1]
sixsta = 6
while sixsta < 100000:
    num.append(sixsta)
    sixsta *= 6

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

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

Submission status: Accepted

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

dp = [float('inf')] * (n + 1)
dp[0] = 0
for i in range(n):
    for c in list_c:
        if i + c <= n:
            dp[i + c] = min(dp[i + c], dp[i] + 1)

print(dp[-1])

Submission status: Accepted

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())

    def div_n(divisor, num):
        """
        >>> div_n(9, 9**2)
        2
        >>> div_n(9, 9**2-1)
        1
        """
        candidate = int(math.log(num, divisor))
        if pow(divisor,(candidate+1)) == num:
            return candidate+1
        else:
            return candidate
    
    
    n = ii()

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



if __name__ == "__main__":
    # import doctest
    # doctest.testmod()
    main()

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    N = int(readline())
    coin = [6**i for i in range(10) if 6**i <= N]
    coin += [9**i for i in range(10) if 9**i <= N]
    coin.sort()
    dp = [INF]*(N+1)
    dp[0]=0
    for c in coin:
        for i in range(N+1):
            if i>=c:
                dp[i] = min(dp[i-c]+1, dp[i])
    print(dp[-1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import numpy as np
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    N = int(readline())
    coin = [6**i for i in range(10) if 6**i <= N]
    coin += [9**i for i in range(10) if 9**i <= N]

    dp = np.zeros(N+1,dtype=np.int32)
    dp += MOD
    dp[0] = 0
    for c in coin:
        for _ in range(9):
            dp[c:] = np.minimum(dp[:-c]+1, dp[c:])
    print(dp[-1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
dp = [n] * (n+1)
dp[0] = 0
# 貰うdp -- dp[i] に遷移を集める
for i in range(1,n+1):
    pow6 = 1
    while pow6 <= i: # i円を実現できるか、を回す
        dp[i] = min(dp[i],dp[i-pow6] + 1)
        pow6 *= 6
    pow9 = 1
    while pow9 <= i:
        dp[i] = min(dp[i], dp[i-pow9] + 1)
        pow9 *= 9
print(dp[n])

Submission status: Accepted

Solution code:
N=int(input())
ans=float("Inf")
for i in range(N+1):
   k=N-i
   k2=i
   six=0
   nine=0
   while k2>0:
      six+=k2%6
      k2//=6
   while k>0:
      nine+=k%9
      k//=9
   ans=min(ans,six+nine)
print(ans)

Submission status: Accepted

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(10):
        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 *= 6
        nine *= 9

print(dp[N])

Submission status: Accepted

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
    return dp[n]

print(solve())

Submission status: Accepted

Solution code:
n=int(input())
dp=[10**18]*(n+1)
dp[n]=0
for i in range(5,0,-1):
    for j in range(n,0,-1):
        if j-9**i>=0:
            dp[j-9**i]=min(dp[j-9**i],dp[j]+1)

for i in range(6,-1,-1):
    for j in range(n,0,-1):
        if j-6**i>=0:
            dp[j-6**i]=min(dp[j-6**i],dp[j]+1)
pass
print(dp[0])

Submission status: Accepted

Solution code:
import copy
n = int(input())
# cur = n
# ans = 0
# while cur >= 6:
#     div6 = 0
#     a = copy.deepcopy(cur)
#     while a != 0:
#         a //= 6
#         div6 += 1
#     div9 = 0
#     b = copy.deepcopy(cur)
#     while b != 0:
#         b //= 9
#         div9 += 1
#     div6 -= 1
#     div9 -= 1
#     if 6**div6 > 9**div9:
#         cur -= 6**div6
#     else:
#         cur -= 9**div9
#     ans += 1
#     print(cur)
# print(ans + cur)

dp = [0]*(n+1)
moto = []
a = 1
while a <= n:
    a *= 6
    if a <= n:
        moto.append(a)
a = 1
while a <= n:
    a *= 9
    if a <= n:
        moto.append(a)

for i in range(1, n+1):
    tar = [dp[i-1]+1]
    for j in moto:
        if i >= j:
            tar.append(dp[i-j]+1)
    dp[i] = min(tar)
print(dp[n])

Submission status: Accepted

Solution code:
def ninebank(val):
    left = val
    ret = 0
    div = 9 ** 5
    while div > 0:
        ret += left // div
        left = left % div
        div = div // 9
    return ret


def sixbank(val):
    left = val
    ret = 0
    div = 6 ** 10
    while div > 0:
        ret += left // div
        left = left % div
        div = div // 6
    return ret


n = int(input())
ret = 10 ** 10
for i in range(n+1):
    x = ninebank(i)
    y = sixbank(n - i)
    ret = min(ret, x + y)
print(ret)

Submission status: Accepted

Solution code:
n = int(input())
inf = 10**9
dp = [inf] * (n + 1)
dp[0] = 0

for i in range(1, n + 1):
    dp[i] = dp[i - 1] + 1
    mlp6 = 6
    while i - mlp6 >= 0:
        dp[i] = min(dp[i], dp[i - mlp6] + 1)
        mlp6 *= 6
    mlp9 = 9
    while i - mlp9 >= 0:
        dp[i] = min(dp[i], dp[i - mlp9] + 1)
        mlp9 *= 9
print(dp[-1])

Submission status: Accepted

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 + 100)
    memo[0] = 0

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

    print(memo[N])


if __name__ == '__main__':
    main()

Submission status: Accepted

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(1, N + 1):
        for nine in range(1, i + 1):
            if 9**nine > i:
                break
            memo[i] = min(memo[i], memo[i - 9**nine] + 1)
        for six in range(1, i + 1):
            if 6**six > i:
                break
            memo[i] = min(memo[i], memo[i - 6**six] + 1)
        memo[i] = min(memo[i], memo[i - 1] + 1)

    print(memo[N])


if __name__ == '__main__':
    main()

Submission status: Accepted

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

sys.setrecursionlimit(100000)
INF = 100100100

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


def f(n):

    # 0なら終了
    if n == 0:
        return 0

    # メモされてたら終了
    if not memo[n] == -1:
        return memo[n]

    ans = INF

    # 9
    for i in range(1, n):
        if 9 ** i > n:
            break
        ans = min(ans, f(n - 9**i) + 1)

    # 6
    for i in range(1, n):
        if 6 ** i > n:
            break
        ans = min(ans, f(n - 6**i) + 1)

    # 1
    ans = min(ans, f(n - 1) + 1)

    # メモ
    memo[n] = ans
    return ans


def main():

    print(f(N))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

sys.setrecursionlimit(100000)
INF = float('inf')

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


def f(n):

    # 0なら終了
    if n == 0:
        return 0

    # メモされてたら終了
    if not memo[n] == INF:
        return memo[n]

    ans = INF

    # 9
    for i in range(1, n):
        if 9 ** i > n:
            break
        ans = min(ans, f(n - 9**i) + 1)

    # 6
    for i in range(1, n):
        if 6 ** i > n:
            break
        ans = min(ans, f(n - 6**i) + 1)

    # 1
    ans = min(ans, f(n - 1) + 1)

    # メモ
    memo[n] = ans
    return ans


def main():
    print(f(N))


if __name__ == '__main__':
    main()

Submission status: Accepted

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: Accepted

Solution code:
N = int(input())

pow6 = [6**i for i in range(1,7)]
pow9 = [9**i for i in range(1,6)]

dp = [1e10 for i in range(N+1)]
dp[0] = 0

for i in range(N):
    dp[i+1] = dp[i]+1

    for x in pow6:
        if i+1 - x < 0: break
        dp[i+1] = min(dp[i+1], dp[i+1 - x]+1)
    
    for x in pow9:
        if i+1 - x < 0: break
        dp[i+1] = min(dp[i+1], dp[i+1 - x]+1)
    
print(dp[N])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())
N = I()
dp = [float('INF')]*(N+1)
dp[0] = 0
for i in range(1,N+1):
    dp[i] = dp[i-1]+1
    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: Accepted

Solution code:
# AtCoder
N = int(input())
dp = [float('inf')]*100010
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: Accepted

Solution code:
import math,numpy, collections

n = int(input())
ans = n
cnt = 0
for i in range(n+1):
    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: Accepted

Solution code:
import numpy as np
n=int(input())

dp=[float("inf")]*(n+1)
dp[0]=0

for i in range(1,n+1):
  dp[i]=min(dp[i],dp[i-1]+1)
  for j in range(1,n+1):
    if i-6**j<0: break
    dp[i]=min(dp[i],dp[i-6**j]+1)
    if i-9**j<0: continue
    dp[i]=min(dp[i],dp[i-9**j]+1)
  #print("debug:",i,",",dp[i])

print(dp[n])

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

n = ni()

dp = [99999999]*(n+1)
dp[0] = 0
for i in range(1, n+1):
    dp[i] = dp[i-1] + 1
    k = 6
    while i-k >= 0:
        dp[i] = min(dp[i], dp[i-k]+1)
        k *= 6
    k = 9
    while i-k >= 0:
        dp[i] = min(dp[i], dp[i-k]+1)
        k *= 9
print(dp[n])

Submission status: Accepted

Solution code:
n = int(input())

dp = [float('inf')] * (n + 1)
dp[0] = 0


for i in range(n):
    dp[i + 1] = min(dp[i + 1], dp[i] + 1)
    for j in range(n):
        if i + 6 ** (j + 1) <= n:
            dp[i + 6 ** (j + 1)] = min(dp[i + 6 ** (j + 1)], dp[i] + 1)
        else:
            break
    for k in range(n):
        if i + 9 ** (k + 1) <= n:
            dp[i + 9 ** (k + 1)] = min(dp[i + 9 ** (k + 1)], dp[i] + 1)
        else:
            break

print(dp[n])

Submission status: Accepted

Solution code:
n = int(input())

dp = [float('inf')] * (n + 1)
dp[0] = 0


for i in range(n):
    dp[i + 1] = min(dp[i + 1], dp[i] + 1)
    for j in range(n):
        if i + 6 ** (j + 1) <= n:
            dp[i + 6 ** (j + 1)] = min(dp[i + 6 ** (j + 1)], dp[i] + 1)
        else:
            break
        for k in range(n):
            if i + 9 ** (k + 1) <= n:
                dp[i + 9 ** (k + 1)] = min(dp[i + 9 ** (k + 1)], dp[i] + 1)
            else:
                break

print(dp[n])