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())
M = 100

ans = 0
dp = [99999] * 100010

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

Submission status: Accepted

Solution code:
def solve(N: int):
    coins = set()
    coins.add(1)
    i = 1
    while 6**i <= N:
        coins.add(6**i)
        i += 1
    i = 1
    while 9**i <= N:
        coins.add(9**i)
        i += 1
         

    dp = [float('inf')] * (N + 1)
    dp[0] = 0
    
    for n in range(1, N + 1):
        for coin in coins:
            if n - coin >= 0:
                dp[n] = min(dp[n - coin] + 1, dp[n])
                
    return dp[N]
N = int(input())
print(solve(N))

Submission status: Accepted

Solution code:
def smaller(x, y):
	if x < y: return x
	return y

nine = []
six = []
a = 9
while a <= 100000:
	nine.append(a)
	a *= 9
a = 6
while a <= 100000:
	six.append(a)
	a *= 6

dp = [0]
for i in range(1, 100001):
	min = dp[i-1]+1
	for j in range(0, len(nine)):
		if i < nine[j]: break
		min = smaller(min, dp[i-nine[j]]+1)
	for j in range(0, len(six)):
		if i < six[j]: break
		min = smaller(min, dp[i-six[j]]+1)
	dp.append(min)
print dp[int(raw_input())]

Submission status: Accepted

Solution code:
n = int(input())

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

dp[0] = 0

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())

dp = [float('inf') for _ 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())
ans = N

for i in range(N + 1):
    cnt = 0
    t1 = i
    t2 = N - i
    while t1 > 0:
        cnt += t1 % 6
        t1 //= 6

    while t2 > 0:
        cnt += t2 % 9
        t2 //= 9
        
    ans = min(ans, cnt)

print(ans)

Submission status: Accepted

Solution code:
# sys.stdin.readline()
import sys
input = sys.stdin.readline

n = int(input())
ans = n
for x in range(n+1):
    c = 0
    t = x
    for i in range(10**5):
        c += t%6
        t //= 6
        if t <= 0:
            break
    t = n-x
    for j in range(10**5):
        c += t%9
        t //= 9
        if t <= 0:
            break
    if ans > c:
        ans = c
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

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

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

for i in range(1,n+1):
    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 = [10**5] *(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
for i in range(1,n+1):
    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())
ans = n
for i in range(n+1):
    c = 0
    t = i
    while(t > 0):
        c += t%6
        t //= 6
    t = n-i
    while(t > 0):
        c += t%9
        t //= 9
    if ans > c:
        ans = c
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

min_count = N
for i in range(N + 1):

    count = 0

    six = i
    while six > 0:
        count += six % 6
        six //= 6

    nine = N - i
    while nine > 0:
        count += nine % 9
        nine //= 9

    min_count = min(min_count, count)

print(min_count)

Submission status: Accepted

Solution code:
N = int(input())

dp = [float('inf')]* 100001

SIXL = [ 6**i for i in range(0,7)]
NINEL = [9**i for i in range(0,6)]
X = sorted(SIXL + NINEL)
dp = [float('inf')]*(N+1)
dp[0] = 0
for i in range(1,N+1):
  for j in X:
    if i-j >= 0:
      dp[i] = min(dp[i],dp[i-j] + 1)
print(dp[-1])

Submission status: Accepted

Solution code:
import sys, os

f = lambda:list(map(int,input().split()))
if 'local' in os.environ :
    sys.stdin = open('./input.txt', 'r')

def solve():
    n = f()[0]
    dp = [0] * (n+1)

    dp[1] = 1

    for i in range(2, 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])

solve()

Submission status: Accepted

Solution code:
def f(num, base):
    ret = 1
    while num >= ret:
        ret *= base
    return ret // base


a = {int(input())}
cnt = 0
while all(a):
    a = {x - f(x, 6) for x in a} | {x - f(x, 9) for x in a}
    cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
# ContestName
# URL
import sys
#import numpy as np

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N = i2n()
    coins = [1]
    d = 6
    while d <= N:
        coins.append(d)
        d *= 6
    d = 9
    while d <= N:
        coins.append(d)
        d *= 9
    dp = [0] * (N+1)
    for i in range(1, N+1):
        n = 100000
        for c in coins:
            if i - c < 0:
                continue
            t = dp[i-c] + 1
            if t < n:
                n = t
        dp[i] = n
    print(dp[N])

main()

Submission status: Accepted

Solution code:
n=int(input())
dp=[0]
for i in range(1,n+1):
    if i<6:
        dp.append(dp[i-1]+1)
    elif 6<=i<9:
        dp.append(dp[i-6]+1)
    else:
        i6=i
        count6=0
        while i6>=6:
            i6=i6/6
            count6=count6+1
        a=dp[i-6**count6]+1
        i9=i
        count9=0
        while i9>=9:
            i9=i9/9
            count9=count9+1
        b=dp[i-9**count9]+1
        dp.append(min(a,b))
print(dp[n])

Submission status: Accepted

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

Submission status: Accepted

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

n = int(input())
dp = [sys.maxsize] * 110000
dp[0] = 0

for i in range(1, n+1):
  pow6 = 1
  while pow6 <= 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:
#DP　動的計画法

N = int(input())

INF = 10 ** 9
dp = [INF] * (N+1) #初期化配列

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

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

Submission status: Accepted

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


def solve(N: int):
    dp = list(range(N + 1))
    for i in [6,9]:
        j = 1
        while i ** j <= N:
            base = i ** j
            idx = 0
            while idx + base <= N:
                dp[idx + base] = min(dp[idx + base], dp[idx] + 1)
                idx += 1
            j += 1
    #print(dp)
    ret = dp[N]
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
###############################################################################

from sys import stdout
from bisect import bisect_left as binl
from copy import copy, deepcopy
from collections import defaultdict


mod = 1


def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return tuple(map(int, input_tuple))


def intina():
    return [int(i) for i in input().split()]


def intinl(count):
    return [intin() for _ in range(count)]


def modadd(x, y):
    global mod
    return (x + y) % mod


def modmlt(x, y):
    global mod
    return (x * y) % mod


def lcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


def combination(x, y):
    assert(x >= y)

    if y > x // 2:
        y = x - y

    ret = 1

    for i in range(0, y):
        j = x - i
        i = i + 1

        ret = ret * j
        ret = ret // i

    return ret


def get_divisors(x):
    retlist = []
    for i in range(1, int(x**0.5) + 3):
        if x % i == 0:
            retlist.append(i)
            retlist.append(x // i)
    return retlist


def get_factors(x):
    retlist = []
    for i in range(2, int(x**0.5) + 3):
        while x % i == 0:
            retlist.append(i)
            x = x // i
    retlist.append(x)
    return retlist


def make_linklist(xylist):
    linklist = {}
    for a, b in xylist:
        linklist.setdefault(a, [])
        linklist.setdefault(b, [])
        linklist[a].append(b)
        linklist[b].append(a)
    return linklist


def calc_longest_distance(linklist, v=1):
    distance_list = {}
    distance_count = 0
    distance = 0
    vlist_previous = []
    vlist = [v]
    nodecount = len(linklist)

    while distance_count < nodecount:
        vlist_next = []
        for v in vlist:
            distance_list[v] = distance
            distance_count += 1
            vlist_next.extend(linklist[v])
        distance += 1
        vlist_to_del = vlist_previous
        vlist_previous = vlist
        vlist = list(set(vlist_next) - set(vlist_to_del))

    max_distance = -1
    max_v = None
    for v, distance in distance_list.items():
        if distance > max_distance:
            max_distance = distance
            max_v = v

    return (max_distance, max_v)


def calc_tree_diameter(linklist, v=1):
    _, u = calc_longest_distance(linklist, v)
    distance, _ = calc_longest_distance(linklist, u)
    return distance


###############################################################################


def main():
    n = intin()

    ans = n

    for i in range(n // 6 + 1):
        count = 0

        s6 = i * 6
        ii = i
        for j in range(1, n + 1):
            scount = ii % 6
            count += scount
            ii = ii // 6
            s6 -= (6**j) * scount
            if not s6:
                break

        s9 = n - i * 6
        ii = s9

        for j in range(0, n + 1):
            scount = ii % 9
            count += scount
            ii = ii // 9
            s9 -= (9**j) * scount
            if not s9:
                break

        ans = min(ans, count)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
dp=[0]+[10**6]*100010

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

N = int(input())

ans = N
for i in range(N+1):
    tmp_ans = 0
    tmp_N = i
    while tmp_N > 0:
        tmp_ans += tmp_N % 9
        tmp_N //= 9
    tmp_N = N-i
    while tmp_N > 0:
        tmp_ans += tmp_N % 6
        tmp_N //= 6
    ans = min(ans, tmp_ans)
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
l=[1]
for i in [6,9]:
    x=i
    while x<=n:
        l.append(x)
        x*=i
dp=[10**9]*(n+1)
dp[0]=0
for x in l:
    for i in range(n):
        if i+x<=n:dp[i+x]=min(dp[i+x],dp[i]+1)
        else:break
print(dp[n])

Submission status: Accepted

Solution code:
n=int(input())
l=[1]
for i in [6,9]:
    x=i
    while x<=n:
        l.append(x)
        x*=i
dp=[10**9]*(n+1)
dp[0]=0
for x in l:
    for i in range(n):
        if i+x<=n:dp[i+x]=min(dp[i+x],dp[i]+1)
print(dp[n])

Submission status: Accepted

Solution code:
#Cはソート済み
def getNumCoin(C,n):
    T=[float('inf') for i in range(n+1)]
    T[0]=0
    m=len(C)
    
    for i in range(m):
        for j in range(C[i],n+1):
            T[j]=min(T[j], T[j-C[i]]+1)
    return T[n]
  
N=int(input())
nine=[0,1,9,9**2,9**3,9**4,9**5]
six=[6,6**2,6**3,6**4,6**5,6**6]
L=sorted(nine+six)
print(getNumCoin(L,N))

Submission status: Accepted

Solution code:
# /usr/bin/python
# -*- coding: utf-8 -*-
import math
import heapq


def nine(n):
  ret = 0
  for r in range(6,0,-1):
    p,n = divmod(n,9**r)
    ret += p
  return ret+n

def six(n):
  ret = 0
  for r in range(7,0,-1):
    p,n = divmod(n,6**r)
    ret += p
  return ret+n



if __name__ == "__main__":
  N = int(input())
  heap_q = []
  for l in range(N+1):
    heapq.heappush(heap_q,nine(l)+six(N-l))
  print(heapq.heappop(heap_q))

Submission status: Accepted

Solution code:
# /usr/bin/python
# -*- coding: utf-8 -*-
import math



def nine(n):
  ret = 0
  for r in range(6,0,-1):
    p,n = divmod(n,9**r)
    ret += p
  return ret+n

def six(n):
  ret = 0
  for r in range(7,0,-1):
    p,n = divmod(n,6**r)
    ret += p
  return ret+n



if __name__ == "__main__":
  N = int(input())
  ans = [N for _ in range(N+1)]
  for l in range(N+1):
    ans[l] = nine(l)+six(N-l)
  print(min(ans))

Submission status: Accepted

Solution code:
# /usr/bin/python
# -*- coding: utf-8 -*-
import math



def nine(n):
  ret = 0
  for r in range(6,0,-1):
    p,n = divmod(n,9**r)
    ret += p
  return ret+n

def six(n):
  ret = 0
  for r in range(7,0,-1):
    p,n = divmod(n,6**r)
    ret += p
  return ret+n



if __name__ == "__main__":
  N = int(input())
  ans = N
  for l in range(N+1):
    ans = min(ans,nine(l)+six(N-l))
  print(ans)

Submission status: Accepted

Solution code:
N = int(input())
INF = 10 ** 6
six = [[6 ** i * j for j in range(1, 6)] for i in range(1, 7)]
nin = [[9 ** i * j for j in range(1, 9)] for i in range(1, 6)]
dp = [INF] * (100010)
dp[0] = 0
for p in [6, 9]:
    for n in range(1, 10 ** 5 + 1):
        power = 1
        while power <= n:
            dp[n] = min(dp[n], dp[n - power] + 1)
            power *= p
print(dp[N])

Submission status: Accepted

Solution code:
n=int(input())
dp=[0]*n
l69=sorted([1]+[6**i for i in range(1,7)]+[9**i for i in range(1,6)])
g=0
for i in range(n):
    for j in range(len(l69)):
        if i+1-l69[j]>=0:
            g=j
    dp[i]=min(dp[i-p]+1 for p in l69[:g+1])

print(dp[n-1])

Submission status: Accepted

Solution code:
import bisect

def main():
    buf = input()
    N = int(buf)
    withdrawal = []
    withdrawal += [int(6 ** x) for x in range(10)]
    withdrawal += [int(9 ** x) for x in range(10)]
    withdrawal = list(sorted(withdrawal))
    stack = [[N, 0]]
    best = 999
    while stack:
        current = stack.pop()
        if current[1] > best:
            continue
        if current[0] == 0:
            if current[1] < best:
                best = current[1]
            continue
        point = bisect.bisect_right(withdrawal, current[0])
        stack.append([current[0]-withdrawal[point-1], current[1]+1])
        stack.append([current[0]-withdrawal[point-2], current[1]+1])
    print(best)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
Inf = float("inf")
dp = [Inf]*(N+1)
dp[0] = 0
for i in range(1,N+1):
        still1 = 1
        while still1 <= N:
                dp[i] = min(dp[i],1+dp[i-still1])
                still1 *= 6
        still2 = 1
        while still2 <= N:
                dp[i] = min(dp[i],1+dp[i-still2])
                still2 *= 9
print(dp[i])

Submission status: Accepted

Solution code:
N=int(input())
list=[1]
i=1
while(6**i<=N):
    list.append(6**i)
    i+=1
i=1
while(9**i<=N):
    list.append(9**i)
    i+=1
dp=[0 for i in range(N+1)]
#dp[i] i円引き出すのにかかる操作
for i in range(N):
    kouho=10**9
    for k in list:
        if i+1-k>=0:
            kouho=min(kouho,dp[i+1-k]+1)
    dp[i+1]=kouho
print(dp[N])

Submission status: Accepted

Solution code:


def main():
    num = int(input())
    ans = num

    for i in range(num + 1):
        cc = 0
        t = i
        while t > 0:
            cc += t % 6
            t //= 6
        t = num - i
        while t > 0:
            cc += t % 9
            t //= 9
        if ans > cc:
            ans = cc

    print(ans)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
l9=list(9**i for i in range(1,6))
l6=list(6**j for j in range(1,8))
l=sorted(l9+l6)
dp=[_ for _ in range(100010)]
for k in l:
    for m in range(k,n+1):
        dp[m]=min(dp[m-k]+1,dp[m])
print(dp[n])

Submission status: Accepted

Solution code:
n=int(input())
ll=[6,9,36,81,216,729,1296,6561,7776,46656,59049]
dp=[i for i in range(100010)]

for l in ll:
    for x in range(l,n+1):
        dp[x]=min(dp[x],dp[x-l]+1)
print(dp[n])

Submission status: Accepted

Solution code:
n=int(input())
ans=10**10
dp=[0]*100001
for i in range(1,n+1):
  tmp=[dp[i-1]+1]
  if i>=6**1:
    tmp.append(dp[i-6**1]+1)
  if i>=9**1:
    tmp.append(dp[i-9**1]+1)
  if i>=6**2:
    tmp.append(dp[i-6**2]+1)
  if i>=9**2:
    tmp.append(dp[i-9**2]+1)
  if i>=6**3:
    tmp.append(dp[i-6**3]+1)
  if i>=9**3:
    tmp.append(dp[i-9**3]+1)
  if i>=6**4:
    tmp.append(dp[i-6**4]+1)
  if i>=9**4:
    tmp.append(dp[i-9**4]+1)
  if i>=6**5:
    tmp.append(dp[i-6**5]+1)
  if i>=9**5:
    tmp.append(dp[i-9**5]+1)
  if i>=6**6:
    tmp.append(dp[i-6**6]+1)
  if i>=9**6:
    tmp.append(dp[i-9**6]+1)
  dp[i]=min(tmp)
print(dp[n])

Submission status: Accepted

Solution code:
N = int(input())

INF = 105 * 10 ** 7
dp = [INF] * 100010
dp[0] = 0

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

print(dp[N])

Submission status: Accepted

Solution code:
N = int(input())

ans = N
for i in range(N + 1):

    temp_ans = 0
    first = i
    second = N - i

    while first != 0:
        temp_ans += first % 6
        first = first // 6
    while second != 0:
        temp_ans += second % 9
        second = second // 9

    ans = min(ans, temp_ans)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:


def read_input():
    n = int(input())
    return n


def count_coin(x, op, min_op):
    if x == 0:
        return 0

    if x in min_op.keys():
        return min_op[x]

    min_count = 10000000
    for o in op:
        if x >= o:
            count = 1 + count_coin(x - o, op, min_op)
            if count < min_count:
                min_count = count

    min_op[x] = min_count
    return min_count


def submit():
    n = read_input()

    ops = [1, 6, 9]

    for op in ops[1:]:
        i = 1
        t = op ** i
        while t <= n:
            ops.append(t)
            t *= op

    ops = list(set(ops))
    ops.sort(reverse=True)
    print(count_coin(n, ops, {}))

if __name__ == '__main__':
    submit()

Submission status: Accepted

Solution code:
n = int(input())
six = []
for i in range(20):
    six.append(6 ** i)
nine = []
for i in range(20):
    nine.append(9 ** i)

res = 10 ** 10
for i in range(n + 1):
    j = n - i
    k = i
    # print(i,j )
    cnt = 0

    #6
    piv = 19
    while k > 0 and piv >= 0:
        cnt += k // six[piv]
        k %= six[piv]
        piv -= 1

    #9
    piv = 19
    while j > 0 and piv >= 0:
        cnt += j // nine[piv]
        j %= nine[piv]
        piv -= 1

    res = min(res,cnt)
print(res)

Submission status: Accepted

Solution code:
l=[1,6,9,36,81,216,729,1296,6561,7776,46656,59049]
l2=[0]*100001

N=int(input())

for i in range(1,N+1):
  mn=100000000000000000
  for x in l:
    if i-x>=0 and l2[i-x]<mn:
      mn=l2[i-x]+1
  l2[i]=mn

print(l2[N])

Submission status: Accepted

Solution code:
N=int(input())
l=[1,6,9,36,81,216,729,1296,6561,7776,46656,59049]
l2=[0]*100001

for i in range(1,100001):
  mn=100000000000000000
  for x in l:
    if i-x>=0 and l2[i-x]<mn:
      mn=l2[i-x]+1
  l2[i]=mn
print(l2[N])

Submission status: Accepted

Solution code:
N=int(input())
l=[1,6,9,36,81,216,729,1296,6561,7776,46656,59049]
l2=[0]*100010
for i in range(1,100010):
  mn=100000000000000000
  for x in l:
    if i-x>=0 and l2[i-x]<mn:
      mn=l2[i-x]+1
  l2[i]=mn
print(l2[N])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())

dp = [0] * (N + 1)

for i in range(1, N + 1):
    dp[i] = float('inf')
    p = 1
    while i - p >= 0:
        dp[i] = min(dp[i], dp[i - p] + 1)
        p *= 6
    q = 9
    while i - q >= 0:
        dp[i] = min(dp[i], dp[i - q] + 1)
        q *= 9
print(dp[N])

Submission status: Accepted

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

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

print(dp[N])

Submission status: Accepted

Solution code:
N=int(input())
list=[1]
i=1
while(6**i<=N):
    list.append(6**i)
    i+=1
i=1
while(9**i<=N):
    list.append(9**i)
    i+=1
list.sort(reverse=True)
n=len(list)
INF=10**19
dp=[INF]*(N+1)
dp[0]=0
for i in range(N):
    for j in list:
        if i+1-j>=0:
            dp[i+1]=min(dp[i+1],dp[i+1-j]+1)
print(dp[N])

Submission status: Accepted

Solution code:
# 解説
N=int(input())
r=N
for i in range(N+1):
  c=0;t=i
  while t>0:c+=t%6;t//=6
  t=N-i
  while t>0:c+=t%9;t//=9
  r=min(r,c)
print(r)

Submission status: Accepted

Solution code:
N = int(input())


# dp[i]: i yen 卸すのに必要な最小の手数
dp = [1e+5]*(N+1)
dp[0] = 0
for i in range(1,N+1):
    dp[i] = dp[i-1]
    tmp = 6
    while i-tmp >= 0:
        dp[i] = min(dp[i], dp[i-tmp])
        tmp *= 6
    tmp = 9
    while i-tmp >= 0:
        dp[i] = min(dp[i], dp[i-tmp])
        tmp *= 9
    dp[i] += 1

print(dp[N])

Submission status: Accepted

Solution code:
N = int(input())
res = N
for i in range(N+1):
  cc = 0
  t = i
  while t>0:
    cc += t % 6
    t = t // 6
  t = N - i
  while t>0:
    cc += t % 9
    t = t // 9
  if cc < res:
    res = cc
print(res)

Submission status: Accepted

Solution code:
import sys
import numpy as np

readInt = lambda: int(sys.stdin.readline())
readIntN = lambda: [int(v) for v in sys.stdin.readline().split(' ')]

n = readInt()
ret = n
for s in range(n+1):
    c = 0
    v = s
    while 0 < v:
        c += v % 6
        v //= 6
    v = n - s
    while 0 < v:
        c += v % 9
        v //= 9
    ret = min(ret, c)
print(ret)

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]
a.sort()
dp = [10**6]*160000
for i in a:
    dp[i] = 1
for i in range(1, N+1):
    for j in a:
        dp[i+j] = min(dp[i]+1, dp[i+j])
print(dp[N])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N=int(input())

dp=[0]*(N+1)
for i in range(1,N+1):
  dp[i]=dp[i-1]+1
  power6=1
  while((6**power6)<=i):
    dp[i]=min(dp[i],dp[i-(6**power6)]+1)
    power6+=1
  power9=1
  while((9**power9)<=i):
    dp[i]=min(dp[i],dp[i-(9**power9)]+1)
    power9+=1
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)
    j,k=1,1
    while i+6**j<=n:
        dp[i+6**j]=min(dp[i+6**j],dp[i]+1)
        j+=1
    while i+9**k<=n:
        dp[i+9**k]=min(dp[i+9**k],dp[i]+1)
        k+=1
print(dp[-1])

Submission status: Accepted

Solution code:
n = int(input())

def compress(n, k, depth=1):
    d, m = divmod(n, k)
    if d == 0:
        return n * depth
    return compress(d, k) + m * depth

minv = float("inf")
for n9 in range(n // 9 + 1):
    m = (n - n9 * 9)
    n6, n1 = divmod(m, 6)
    result = n1 + compress(n6, 6) + compress(n9, 9)
    minv = min(minv, result)
print(min(minv, n))

Submission status: Accepted

Solution code:
N = int(input())
DP = [0]+[10**7]*(N)
li = [1] + [6**i for i in range(1,7)] + [9**i for i in range(1,6)]
for i in range(N+1):
    if(i in li):
        DP[i]=1
    else:
        for j in 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())
INF = float('inf')
dp = [INF] * 100010
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 = 1
    while i - k >= 0:
        dp[i] = min(dp[i], dp[i-k] + 1)
        k *= 9
print(dp[N])

Submission status: Accepted

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

	for i in range(2, N+1):
		ans = dp[i-1]+1
		tmp6 = 6
		while tmp6 <= i:
			ans = min(ans, dp[i-tmp6]+1)
			tmp6 *= 6

		tmp9 = 9
		while tmp9 <= i:
			ans = min(ans, dp[i-tmp9]+1)
			tmp9 *= 9

		dp[i] = ans

	print(dp[N])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())

res = 10**10

for i in range(N+1):
  count = 0
  six = i
  while six>0:
    count += six%6
    six = six//6
  nine = N-i
  while nine>0:
    count += nine%9
    nine = nine//9
  res = min(res,count)

print(res)

Submission status: Accepted

Solution code:
import copy
N = int(input())
#use {1, 6, 9, 6**2,...}
count = 1
use_money = [1]
x = 1
while 6**x<=N:
  use_money.append(6**x)
  x+=1
x = 1
while 9**x<=N:
  use_money.append(9**x)
  x+=1
use_money.sort(reverse=True)
money = copy.copy(use_money)

while not(N in money):
  B = []
  for x in money:
    for y in use_money:
      if x+y<=N and not(x+y in B):
        B.append(x+y)
  B.sort(reverse=True)
  money = B[:min(5,len(B))]
  count+=1
print(count)

Submission status: Accepted

Solution code:
N = int(input())

l1 = 2 ** 30
p6 = [1] * 7
p9 = [1] * 6
for i in range(1,7):
    p6[i] = p6[i-1] * 6
    if i < 6 : p9[i] = p9[i-1] * 9

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(N: int):
    cand = [1]
    a = 6
    while a < 10**5:
        cand.append(a)
        a *= 6
    a = 9
    while a < 10**5:
        cand.append(a)
        a *= 9
    cand.sort()
    M = len(cand)

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


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
z=set([1])
for i in range(100):
	if 6**i <= 100000:
		z.add(6**i)
	if 9**i <= 100000:
		z.add(9**i)

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

for n in range(1, N+1):
	ans = []
	for m in z:
		if n-m >= 0:
			ans.append(1 + A[n-m])
	A[n] = min(ans)

print(A[N])

Submission status: Accepted

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

for n in range(1, N+1):
    dp.append(dp[n-1]+1)
    exp = 6
    while exp <= n:
        dp[n] = min(dp[n], dp[n-exp] + 1)
        exp *= 6
    exp = 9
    while exp <= n:
        dp[n] = min(dp[n], dp[n-exp] + 1)
        exp *= 9

print(dp[-1])