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:
#!/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 s(n, r):
    if n == 0:
        return 0
    return n % r + s(n // r, r)


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)
        c = s(j,6)
        d = s(N-j,9)
        ans = min(ans, c+d)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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[N])

Submission status: Accepted

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

Solution code:
from functools import reduce
N = int(input())
amounts = sorted(sum(([6 ** (i + 1), 9 ** i] for i in range(6)), []))
account = 1 << N
times = 0
while (times := times + 1) and not (account := reduce(lambda a, b: a | b, [account >> amount for amount in amounts])) & 1:
    pass
print(times)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n = inn()
mn = BIG
for i in range(0,n+1,9):
    j = n-i
    sm = 0
    k = i
    while k>0:
        sm += k%9
        k //= 9
    k = j
    while k>0:
        sm += k%6
        k //= 6
    mn = min(mn,sm)
print(mn)

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

from collections import defaultdict, deque
from sys import exit
import heapq
import math
import copy
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
# list(map(int, input().split()))
mod = 10 ** 9 + 7

N = getN()
splitlist = [1]
splitsix = 6
while splitsix < 100000:
    splitlist.append(splitsix)
    splitsix *= 6
splitnine = 9
while splitnine < 100000:
    splitlist.append(splitnine)
    splitnine *= 9
splitlist.sort()
# これやらないと再帰が無限に実行される
splitlist.reverse()

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

# 貰うdp
for i in range(N + 1):
    for k in splitlist:
        if i >= k:
            dp[i] = min(dp[i], dp[i - k] + 1)
print(dp[-1])

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

from collections import defaultdict, deque
from sys import exit
import heapq
import math
import copy
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
# list(map(int, input().split()))
mod = 10 ** 9 + 7

N = getN()
splitlist = [1]
splitsix = 6
while splitsix < 100000:
    splitlist.append(splitsix)
    splitsix *= 6
splitnine = 9
while splitnine < 100000:
    splitlist.append(splitnine)
    splitnine *= 9
splitlist.sort()
# これやらないと再帰が無限に実行される
splitlist.reverse()

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

def spliter(n):
    if dp[n] < 1000000:
        return dp[n]
    res = float('inf')
    for split in splitlist:
        if n >= split:
            res = min(res, spliter(n - split) + 1)
    dp[n] = res
    return res
spliter(N)
print(dp[-1])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def s(n, r):
  if n == 0:
    return 0
  return n % r + s(n // r, r)
n = int(input())
ans = 100000
for i in range(n + 1):
  ans = min(ans, s(i, 6) + s(n - i, 9))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
dp = [float('Inf')] * (100000 + 1)
dp[0] = 0
for i in range(1, n + 1):
    dp[i] = dp[i - 1] + 1
    cnt = 1
    for j in range(0, 7):
        cnt *= 6 
        if i - cnt >= 0:
            dp[i] = min(dp[i], dp[i - cnt] + 1)
    cnt = 1
    for j in range(0, 6):
        cnt *= 9
        if i - cnt >= 0:
            dp[i] = min(dp[i], dp[i - cnt] + 1)
print(dp[n])

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    dp = [i for i in range(N + 1)]
    pow6 = 6
    while pow6 <= N:
        for i in range(N + 1):
            if i + pow6 > N:
                break
            dp[i + pow6] = min([dp[i + pow6], 1 + dp[i]])
        pow6 *= 6
    pow9 = 9
    while pow9 <= N:
        for i in range(N + 1):
            if i + pow9 > N:
                break
            dp[i + pow9] = min([dp[i + pow9], 1 + dp[i]])
        pow9 *= 9
    print(dp[N])


if __name__ == '__main__':
    main()

Submission status: Accepted

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:
        list_before_compare.append(dp_table[i-6**six_k] + 1)
        six_k += 1
    
    #9のべき乗の引き出し
    while 9**nine_k <= i:
        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通りのみ→最小値は1
dp_table[0] = 0

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

print(dp_table[-1])

Submission status: Accepted

Solution code:
n = int(input())
count=n
for i in range(0,n+1):
  temp=0
  temp6=i
  while temp6>0:
    temp=temp+temp6%6
    temp6=int(temp6/6)
  temp9=n-i
  while temp9>0:
    temp=temp+temp9%9
    temp9=int(temp9/9)
  count=min(count,temp)
print(count)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N=int(input())
    ans=INF
    for i in range(N+1):
        tmp=0
        n=i
        while n>0:
            tmp+=n%6
            n//=6
        m=N-i
        while m>0:
            tmp+=m%9
            m//=9
        ans=min(ans,tmp)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
mi=n
for k in range(n+1):
    six=0
    nine=0
    k2=n-k
    while k>0:
        six+=k%6
        k//=6
    while k2>0:
        nine+=k2%9
        k2//=9
    mi=min(mi,six+nine)
print(mi)

Submission status: Accepted

Solution code:
N=int(input())
L=[1]
for i in range(1,100):
    a=6**i
    if a<=100000:
        L.append(a)
    else:
        break
for i in range(1,100):
    a=9**i
    if a<=100000:
        L.append(a)
    else:
        break
dp=[1000000]*(N+1)
dp[0]=0
for i in range(1,N+1):
    sub=10**5
    for l in L:
        if i-l>=0:
            sub=min(sub, dp[i-l]+1)
    dp[i]=sub

print(dp[N])

Submission status: Accepted

Solution code:
N = int(input())

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

memo[0] = 0
memo[1] = 1

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:
        if (i - exp_six) >= 0:
            six_result = min(six_result, memo[i-exp_six] + 1)
        else:
            break

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

Submission status: Accepted

Solution code:
N = int(input())
money = [1]
i = 1
while True:
    i *= 6
    if i <= 100000:
        money.append(i)
    else:
        break
i = 1
while True:
    i *= 9
    if i <= 100000:
        money.append(i)
    else:
        break

M = len(money)

dp = [[10 ** 9 for _ in range(N + 1)] for _ in range(M + 1)]

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

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

print(dp[M][N])

Submission status: Accepted

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] = 1
    V.append(9**i)
    i += 1
i = 1
while 6**i < 100000:
    dp[6**i] = 1
    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: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
dp = [float('inf')]*n
amt = [1] + [6**i for i in range(1, 7)] + [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: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
c = [1]
x = 6
while x <= n:
    c.append(x)
    x *= 6
x = 9
while x <= n:
    c.append(x)
    x *= 9
l = len(c)
dp = [[float("inf")]*(n+1) for _ in range(l+1)]
dp[0][0] = 0
for i in range(l):
    for yen in range(n+1):
        if yen - c[i] < 0: dp[i+1][yen] = dp[i][yen]
        else: dp[i+1][yen] =  min(dp[i][yen],dp[i+1][yen-c[i]]+1)
# for i in range(l+1): print(dp[i])
print(dp[l][n])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
ans=n
for i in range(n+1):
    cnt=0
    t=i
    while t>0:
        cnt+=t%6
        t//=6
    j=n-i
    while j>0:
        cnt+=j%9
        j//=9
    ans=min(ans,cnt)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
dp = [float("INF") for i in 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: Accepted

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

Submission status: Accepted

Solution code:
import itertools,sys
def I(): return int(sys.stdin.readline().rstrip())
N = I()
if N<=5:
    print(N)
    exit()
dp = [float('INF')]*(N+1)
dp[0] = 0
num6,num9 = 6,9
d6d9 = set()
while num6<=N:
    d6d9.add(num6)
    num6 *= 6
while num9<=N:
    d6d9.add(num9)
    num9 *= 9
for i,x in itertools.product(range(N+1),d6d9):
    if i+x>=N+1:
        continue
    dp[i+1] = min(dp[i+1],dp[i]+1)
    dp[i+x] = min(dp[i+x],dp[i]+1)
print(dp[-1])

Submission status: Accepted

Solution code:
N=int(input())
dp=[float('inf') for i in 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: Accepted

Solution code:
N=int(input())
dp=[float('inf') for i in range(100001)]
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:
def solve():
    N = int(input())
    dp = [float('inf')] * (N+1)
    dp[0] = 0

    for i in range(1,N+1):
        # 1yen
        dp[i] = min(dp[i], dp[i-1]+1)

        # 6 ** n yen
        n = 1
        while i - pow(6,n) >= 0:
            dp[i] = min(dp[i], dp[i-pow(6,n)]+1)
            n += 1

        # 9 ** n yen
        n = 1
        while i - pow(9,n) >= 0:
            dp[i] = min(dp[i], dp[i-pow(9,n)]+1)
            n += 1
    
    print(dp[-1])

if __name__ == '__main__':
    solve()

Submission status: Accepted

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

Submission status: Accepted

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

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+1):
    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])

Submission status: Accepted

Solution code:
import numpy as np
n = int(input())
# 1, 6, 6**2, ---, 9, 9**2, -----
lim = 10 ** 18
dp = [lim] * (n + 1)
dp[0] = 0

check = [1]
# for 6
temp = 6
while (temp <= n):
    check.append(temp)
    temp *= 6

# for 9
temp = 9
while (temp <= n):
    check.append(temp)
    temp *= 9

# print(check)

for i in range(1, n + 1):
    for cc in check:
        temp = i - cc
        if (temp >= 0):
            dp[i] = min(dp[i], dp[temp] + 1)
            # i -cc = 0 になるのは、i = 6,9,46,81　のとき
            # > 元の値と前ステップのコスト＋１を比較して、小さい方を選択
            # dp[0] + 1から始まる。
            # print(dp[i])

print(dp[n])

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
def main():
    import bisect
    n = int(input())
    m = [10 ** 5 for _ in range(n + 1)]
    m[0] = 0
    a = [6 ** i for i in range(7)]
    b = [9 ** i for i in range(6)]
    c = sorted(a + b)
    for i in range(1, n + 1):
        j = bisect.bisect_right(c, i)
        k = [1 + m[i - x] for l, x in enumerate(c) if l < j]
        m[i] = min(k)

    print(m[-1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    m = [10 ** 5 for _ in range(n + 1)]
    m[0] = 0
    for i in range(1, n + 1):
        j = 0
        while i - 6 ** j >= 0:
            m[i] = min(1 + m[i - 6 ** j], m[i])
            j += 1
        j = 0
        while i - 9 ** j >= 0:
            m[i] = min(1 + m[i - 9 ** j], m[i])
            j += 1

    print(m[-1])


if __name__ == '__main__':
    main()

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
ans = n
for i in range(n+1):
    j = n - i
    preans = 0
    while i > 0:
        preans += i % 6
        i //= 6
    while j > 0:
        preans += j % 9
        j //= 9
    ans = min(ans, preans)
print(ans)

Submission status: Accepted

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

L=[1]
for i in range(1,N):
    if 6**i<=N:
        L.append(6**i)
    else:
        break
for i in range(1,N):
    if 9**i<=N:
        L.append(9**i)
    else:
        break
L=np.array(L)
dp=np.ones((N+1))*100000
dp[0]=0
dp[1]=1
for i in range(2,N+1):
    dp[i]=(dp[i-L]+1).min()

print(int(dp[N]))

Submission status: Accepted

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

L=[1]
for i in range(1,N):
    if 6**i<=N:
        L.append(6**i)
    else:
        break
for i in range(1,N):
    if 9**i<=N:
        L.append(9**i)
    else:
        break

dp=[100000]*(N+1)
dp[0]=0
dp[1]=1
for i in range(2,N+1):
    sub=100000
    for l in L:
        if i-l>=0:
            sub=min(dp[i-l]+1,sub)
    dp[i]=sub

print(dp[N])

Submission status: Accepted

Solution code:
import numpy as np
N=int(input())
six=[1]
nine=[]
for i in range(1,N):
  six.append(6**i)
  nine.append(9**i)
  if 6**i>N:
    break
six=np.array(six)
nine=np.array(nine)
L=np.concatenate([six,nine])    
now=N
count=0
dp=np.ones(N+L.max()+1)*10**5
dp[1]=1
dp[0]=0
#dp[i+1]　iをちょうど引き出すのに必要な最小回数
for i in range(1,N):
  dp[i+1]=(dp[i-L+1]+1).min()

  
print(int(dp[N]))
#print(len(L))

Submission status: Accepted

Solution code:
N = int(input())
dp = [float("inf") for i in range(N+1)]
for i in range(6):
  if i <= N:
    dp[i] = i

for i in range(N+1):
  c = 1
  while i+6**c <= N:
    dp[i+6**c] = min(dp[i+6**c],dp[i]+1)
    c += 1
  c = 1
  while i+9**c <= N:
    dp[i+9**c] = min(dp[i+9**c],dp[i]+1)
    c += 1

for i in range(N,0,-1):
  if dp[i] != 0:
    ans = dp[i] + N-i
    break
print(ans)

Submission status: Accepted

Solution code:
def make_list(a, n):
    res = [1]
    i = 1
    while pow(a, i) <= n:
        res.append(pow(a, i))
        i += 1
    return res[::-1]


def find_withdraw_times(n, w):
    res = 0
    for ww in w:
        res += n // ww
        n %= ww
    return res


def main():
    n = int(input())
    answer = float("inf")
    way_6 = make_list(6, n)
    way_9 = make_list(9, n)
    for i in range(n + 1):
        answer = min(answer, find_withdraw_times(i, way_6) + find_withdraw_times(n - i, way_9))
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
n = int(input())

num_li = []
for i in range(10):
    num_li.append(6**i)
    num_li.append(9**i)
num_li.sort(reverse=True)

dp = [10**18 for i in range(n+1)]
dp[0]=0
for i in range(1,n+1):
    for j in num_li:
        if i-j>=0:
            dp[i]=min(dp[i],dp[i-j]+1)

print(dp[n])

Submission status: Accepted

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+2):
        if 6**j>i:
            break
        dp[i] = min(dp[i-6**j]+1, dp[i])
    for k in range(max9+2):
        if 9**k>i:
            break
        dp[i] = min(dp[i-9**k]+1, dp[i])

print(dp[-1])

Submission status: Accepted

Solution code:
n=int(input())
m=[int(pow(6,i)) for i in range(7)]
m9=[int(pow(9,i)) for i in range(1,6)]
m+=m9
m.sort(reverse=True)
# print(m)
dp=[10**18 for i in range(n+1)]
dp[0]=0
for i in range(1,n+1):
  for j in m:
    if i-j>=0:
      dp[i]=min(dp[i],dp[i-j]+1)
# print(dp)
print(dp[n])

Submission status: Accepted

Solution code:
import sys

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)]
    dp[0] = 0

    for i in range(1, n + 1):
        for L in List:
            if i - L >= 0:
                dp[i] = min(dp[i], dp[i - L] + 1)

    print(dp[n])


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import sys
import re
import math
import collections

import bisect

# import copy
# import heapq
# from collections import deque
# import decimal

# sys.setrecursionlimit(100001)
INF = sys.maxsize
# MOD = 10 ** 9 + 7

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


# ===CODE===


def main():
    n = ni()
    l = 10 ** 5 + 1

    items = [1]
    for i in range(10 ** 3):
        tmp6 = 6 ** i
        if tmp6 < l:
            items.append(tmp6)

        tmp9 = 9 ** i
        if tmp9 < l:
            items.append(tmp9)

    s = {0}
    for i in range(l):
        next_s = set()
        for ts in s:
            for d in items:
                if ts+d <= n:
                    next_s.add(ts+d)
        if n in next_s:
            print(i+1)
            break
        s = next_s


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n = inp()
res = [INF] * (n+1)
res[0] = 0
ge = [1]
for i in [6,9]:
    now = 1
    while True:
        now *= i
        if now > n:
            break
        ge.append(now)
ge.sort()
for i in range(1,n+1):
    for x in ge:
        if x > i:
            continue
        res[i] = min(res[i], res[i-x]+1)
print(res[n])

Submission status: Accepted

Solution code:
n = int(input())
dp = [10 ** 5 for _ in range(n + 1)]

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

print(dp[n])

Submission status: Accepted

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

Solution code:
from itertools import product
def count9(cur):
    count = 0
    for i in range(6)[::-1]:
        count += cur//(9**i)
        cur %= 9**i
    return count
n = int(input())
ans = count9(n)
for x in product("012345",repeat = 6):
    digitsum = 0
    SUM = 0
    for i in range(6):
        SUM += int(x[i])*6**(i+1)
        digitsum += int(x[i])
    if SUM <= n:
        ans = min(ans,digitsum+count9(n-SUM))
print(ans)

Submission status: Accepted

Solution code:
memo = {}
def f(x):
    if 0<=x<=5:
        return x
    if x in memo:
        return memo[x]
    k = 0
    while 9**k<=x:
        k += 1
    m = 0
    while 6**m<=x:
        m += 1
    memo[x] = min(f(x-9**(k-1))+1,f(x-6**(m-1))+1)
    return memo[x]
print(f(int(input())))

Submission status: Accepted

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=[0]
for i in range(1,n+1):
  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])

Submission status: Accepted

Solution code:
def main():
    inf = 1 << 30

    N = int(input())

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

    for i in range(1, N + 1):
        t = inf
        x = 1
        while x <= i:
            t = min(t, dp[i - x])
            x *= 6
        x = 1
        while x <= i:
            t = min(t, dp[i - x])
            x *= 9
        dp[i] = t + 1

    print(dp[N])


if __name__ == '__main__':
    main()

Submission status: Accepted

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(a)
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: Accepted

Solution code:
n = int(input())
#dp[i] = iennの金を引き出すのにかかる操作回数の最小値
dp = [float('inf')]*(n+1)
dp[0] = 0
from math import log
for i in range(1,n+1):
    for j in range(int(log(n,6)+0.00001)+1):
        dp[i] = min(dp[i],dp[i-6**j]+1)
    for j in range(int(log(n,9)+0.00001)+1):
        dp[i] = min(dp[i],dp[i-9**j]+1)
print(dp[n])

Submission status: Accepted

Solution code:
N = int(input())

def digit(x, base):
    if x == 0:
        return 0
    return digit(x // base, base) + x % base

def calc(six, nine):
    return digit(six, 6) + digit(nine, 9)

ans = 10**18
for six in range(N + 1):
    ans = min(ans, calc(six, N - six))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
n0 = n
money = [1]
pow6 = 6
while pow6 <= n:
    money.append(pow6)
    pow6 *= 6
# pow9 = 9
# while pow9 <= n:
#     p.append(pow9)
#     pow9 *= 9
money.sort(reverse = True)

def cnt(x):
    res = 0
    while x > 0:
        res += x%9
        x = x // 9
    return res
anst = 1e100
for i in range(n0//9+1):
    ans = cnt(i)
    n = n0 - i*9
    for m in money:
        if m <= n:
            ans += n//m
            n %= m
    anst = min(anst,ans)
print(anst)

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
C = [6 ** x for x in range(8) if 6 ** x <= N]
C += [9 ** x for x in range(8) if 9 ** x <= N]

dp = np.zeros(N + 1, np.int64)
dp += 10 ** 10

for c in C:
    dp[c] = 1
for c in C:
    for _ in range(9):
        dp[c:] = np.minimum(dp[c:], dp[:-c] + 1)
print(dp[N])

Submission status: Accepted

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 + 1][j - w] + v, dp[i + 1][j])

print(dp[-1][-1])

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
    
    tmp = 6
    while i - tmp >= 0:
        dp[i] = min(dp[i], dp[i - tmp] + 1)
        tmp *= 6
    
    tmp = 9
    while i - tmp >= 0:
        dp[i] = min(dp[i], dp[i - tmp] + 1)
        tmp *= 9

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