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:
v = [100000 for i in range(100001)]
v[0] = 0
C = [1,6,9,36,81,216,729,1296,6561,7776,46656,59049]
for i in range(1,100001):
    for j in C:
        if j > i: break
        v[i] = min(v[i],v[i-j]+1)
print(v[int(input())])

Submission status: Accepted

Solution code:
l=[100000 for i in range(100001)]
l[0]=0
dif=[1,6,9,36,81,216,729,1296,6561,7776,46656,59049]
for i in range(1,100001):
    for j in dif:
        if j>i: break
        l[i]=min(l[i],l[i-j]+1)
n=int(input())
print(l[n])

Submission status: Accepted

Solution code:
def withdrow(rest,num,cost):
    
    ans1 = float('inf')
    ans2 = float('inf')
    
    if rest < 24:
        return num + cost[rest]
    else:
        for i in range(1,10):
            if rest < 6**i:
                ans1 = withdrow(rest-6**(i-1), num+1,cost)
                break

    if rest < 24:
        return num + cost[rest]
    else:
        for i in range(1, 10):
            if rest < 9**i:
                ans2 = withdrow(rest-9**(i-1), num+1,cost)
                break

    return min(ans1, ans2)

N = int(input())

cost = [0,1,2,3,4,5,1,2,3,1,2,3,2,3,4,2,3,4,2,3,4,5,6,7]

ans = withdrow(N, 0, cost)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

withdrawal = [1]
i, j = 1, 1
while True:
    if 6 ** i <= n:
        withdrawal.append(6 ** i)
        i += 1
    else:
        break

while True:
    if 9 ** j <= n:
        withdrawal.append(9 ** j)
        j += 1
    else:
        break

withdrawal = sorted(withdrawal)

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

for i in range(1, n + 1):
    candidate = []
    for w in withdrawal:
        if i - w >= 0:
           candidate.append(dp[i - w])
        else:
            break

    dp[i] = min(candidate) + 1

print(dp[-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# import sys
# sys.stdin = open("F:\\Scripts\\input","r")
# sys.stdout = open("F:\\Scripts\\output","w")


MOD = 10**9 + 7
I = lambda:list(map(int,input().split()))


s = []
for i in range(1,7):
	s.append(9**i)
	s.append(6**i)
n , = I()
a = [0]*100009
for i in range(1,100007):
	a[i] = a[i-1] + 1
	for j in s:
		if i - j >= 0:
			# print('hi',end='')
			# print(a[i-j]+1,i,a[i])
			a[i] = min(a[i - j] + 1,a[i])
print(a[n])

Submission status: Accepted

Solution code:
n=int(input())
w=n
for i in range(0,n+1,6):
    i2=n-i
    s=0
    for j in range(6):#1入らない
        ds=i//6**(6-j)
        s+=ds
        i-=ds*6**(6-j)
    for  j in sorted(range(6),reverse=True):
        ds=i2//9**j
        s+=ds
        i2-=ds*9**j
    if s<w:
        w=s
print(w)

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//=6
    t=n-i
    while t>0:
        cc+=t%9
        t//=9
    res=min(res,cc)

print(res)

Submission status: Accepted

Solution code:
MAX_N = 100000
N = int(input())
ret = [1000000 for _ in range(MAX_N + 1)]
ret[0] = 0


def f(i, j):
    if j <= MAX_N:
        ret[j] = min(ret[j], ret[i] + 1)


for i in range(N + 1):
    f(i, i + 1)

    for k in range(1, 7):
        f(i, i + 6 ** k)

    for k in range(1, 6):
        f(i, i + 9 ** k)


print(ret[N])

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())
atoz = [chr(i) for i in range(97,97+26)]

N = inp()

def calc(x,n):
	tmp = 0
	while x > 0:
		tmp += x%n
		x //= n
	return tmp

ans = INF
for i in range(0,N+1,6):
	tmp = calc(i,6)+calc(N-i,9)
	ans = min(ans,tmp)

print(ans)

Submission status: Accepted

Solution code:

def mi():
	return map(int, input().split())

maxn = 100000
s = [1]
n = int(input())
for i in range(20):
	if 6**i<=maxn:
		s.append(6**i)
	if 9**i<=maxn:
		s.append(9**i)
dp = [10**10]*(maxn+4)
dp[0] = 0
m = len(s)
for i in range(1,maxn+1):
	for j in range(m):
		if s[j]<=i:
			subres = dp[i-s[j]]
		if subres!=10**10 and subres+1<dp[i]:
			dp[i] = subres+1
print (dp[n])

Submission status: Accepted

Solution code:
# 部分分け
n = int(input())

ans = 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
    ans = min(ans,cc)
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8

n = int(input())
dp = [0,1]

for i in range(2,n+1):
    Q = []
    Q.append(1+dp[i-1])
    
    p6 = 1
    while i >= 6**p6:
        Q.append(1+dp[i-6**p6])
        p6 += 1

    p9 = 1
    while i >= 9**p9:
        Q.append(1+dp[i-9**p9])
        p9 += 1
    
    dp.append(min(Q))

print(dp[n])

Submission status: Accepted

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

Submission status: Accepted

Solution code:

n = int(input())

dp = [0]

l6 = []
l9 = []

for i in range(7):
    l6.append(6**i)
    l9.append(9**i)

for i in range(1, n+1):
    ans_i = []
    for j in range(7):
        if l6[j]<=i:
            ans_i.append(dp[i-l6[j]]+1)
        if l9[j]<=i:
            ans_i.append(dp[i-l9[j]]+1)
    dp.append(min(ans_i))

print(dp[n])

Submission status: Accepted

Solution code:
n = int(input())
coins = [1]
for i in range(1,7):
    if 6**i <= n:
        coins.append(6**i)
    if 9**i <= n:
        coins.append(9**i)
coins.reverse()
dp = [10**5]*(n+1)

def f(i):
    #print(i)
    if i==0:
        return 0
    if dp[i] != 10**5:
        return dp[i]
    candidates = [f(i-coin)+1 for coin in coins if i-coin >= 0]
    dp[i] = min(candidates)
    return dp[i]

print(f(n))

Submission status: Accepted

Solution code:
N = int(input())

A = [None] * N

x = 1
while 6 ** x <= N:
    x += 1

y = 1
while 9 ** y <= N:
    y += 1

Q = ([1] + [6 ** i for i in range(1, x)] + [9 ** i for i in range(1, y)])
Q.sort()

for n in range(1, N+1):
    if n in Q:
        A[n-1] = 1
    else:
        a = []
        for q in Q:
            if n - q > 0:
                a.append(A[(n - q)-1] + 1)
        A[n-1] = min(a)

print(A[N-1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
C - Strange Bank
https://abc099.contest.atcoder.jp/tasks/abc099_c

"""
import sys
from sys import stdin
input = stdin.readline


def solve(n):
    withdrawals = []
    for i in range(1, 100):
        for j in [6, 9]:
            if j**i <= n:
                withdrawals.append(j**i)
    withdrawals.sort()

    dp = [[-1] * (n+1) for _ in range(len(withdrawals)+1)]
    for x in range(n+1):
        dp[0][x] = x
    for y in range(len(withdrawals)+1):
        dp[y][0] = 0

    for y, w in enumerate(withdrawals, start=1):
        for x in range(1, n+1):
            if dp[y][x-w] >= 0:
                dp[y][x] = min(dp[y][x-w] + 1, dp[y-1][x])
            else:
                dp[y][x] = dp[y-1][x] - dp[y-1][x-1] + dp[y][x-1]
    return dp[-1][-1]


def main(args):
    n = int(input())
    ans = solve(n)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

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

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:
N = int(input())
#a,b = map(int,input().split())

ans = 1e6
for i in range(N+1):
  cnt = 0
  # 6の倍数で支払う金額がi
  S = i
  while(S>0):
    x = S % 6
    cnt += x
    S = S // 6
  # 9の倍数で支払う金額は残り
  S = N - i
  while(S>0):
    x = S % 9
    cnt += x
    S = S // 9
  ans = min(ans, cnt)

print(ans)

Submission status: Accepted

Solution code:
N = int(input())

dp = list(range(N+1))

def calc(unit_base):
    unit = unit_base
    while unit <= amount:
        dp[amount] = min(dp[amount], dp[amount-unit]+1)
        unit *= unit_base

for amount in range(6, N+1):
    calc(6)
    calc(9)

print(dp[N])

Submission status: Accepted

Solution code:
N = int(input())

dp = list(range(N+1))

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

    unit = 9
    while unit <= amount:
        dp[amount] = min(dp[amount], dp[amount-unit]+1)
        unit *= 9

print(dp[N])

Submission status: Accepted

Solution code:
N = int(input())

INF = N
dp = [0, 1, 2, 3, 4, 5] + [INF for _ in range(N-5)]

for amount in range(6, N+1):
    dp[amount] = amount

    unit = 6
    while unit <= amount:
        dp[amount] = min(dp[amount], dp[amount-unit]+1)
        unit *= 6

    unit = 9
    while unit <= amount:
        dp[amount] = min(dp[amount], dp[amount-unit]+1)
        unit *= 9

print(dp[N])

Submission status: Accepted

Solution code:
import sys

N = int(input())
sys.setrecursionlimit(N*10)

memo = dict()
INF = N

def withdraw(amount):
    if amount == 0:
        return 0
    if amount in memo:
        return memo[amount]

    answer = amount
    
    unit = 6
    while unit <= amount:
        answer = min(answer, withdraw(amount-unit)+1)
        unit *= 6

    unit = 9
    while unit <= amount:
        answer = min(answer, withdraw(amount-unit)+1)
        unit *= 9

    memo[amount] = answer
    return answer

print(withdraw(N))

Submission status: Accepted

Solution code:
n = int(input())
res = float('inf')
for i in range(n+1):
    r = 0
    # i円(0<=i<=n)を6の累乗円で
    t = i
    while t>0:
        r += t%6
        t //= 6
    # 残りのn-i円を9の累乗円で引き出す
    t = n - i
    while t>0:
        r += t%9
        t //= 9
    res = min(res,r)
print(res)

Submission status: Accepted

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

INF = 999999999
n = int(input())

coins = [1]

s = 9
while s<=n:
    coins.append(s)
    s *= 9

s = 6
while s<=n:
    coins.append(s)
    s *= 6

coins.sort(reverse=True)

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

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

print(dp[-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())

dp = [i for i in range(101010)]


t = 20

while True:
	for i in range(101010):
		if 6**t+(i+1) < 101010:
			dp[6**t+(i)] = min(dp[6**t+(i)], dp[i] + 1)

	t -= 1
	if t == 0:
		break

t = 20
while True:
	for i in range(101010):
		if 9**t+(i+1) < 101010:
			dp[9**t+(i)] = min(dp[9**t+(i)], dp[i] + 1)

	t -= 1
	if t == 0:
		break

i = 0
while i+1 < 101010:
	dp[i+1] = min(dp[i+1],dp[i]+1)
	i += 1

print dp[n]

Submission status: Accepted

Solution code:
N=input()

nl=[]
nl.append(1)
for i in range(1,7): nl.append(6**i)
for i in range(1,6): nl.append(9**i)

dp=[ float("inf") for i in range(N+1)]
dp[0]=0

for i in range(N+1):
	for dx in nl:
		if i+dx<=N:
			dp[i+dx]=min(dp[i+dx], dp[i]+1)


print dp[N]

Submission status: Accepted

Solution code:
N=input()	#N=a+b

ans=float("inf")
for a in range(N+1):
	b=N-a
	cnt=0
	for i in range(8,-1,-1):
		t=6**i
		if a>=t:
			cnt+=(a/t)
			a=a%t

	for i in range(8,-1,-1):
		t=9**i
		if b>=t:
			cnt+=(b/t)
			b=b%t
	ans=min(ans,cnt)

print ans

Submission status: Accepted

Solution code:
N=input()

dp=[ float("inf") for i in range(N+1) ]
dp[0]=0

i=1

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


print dp[N]

Submission status: Accepted

Solution code:
N = int(input())
m = N
for n6 in range(N+1):
  n9 = N - n6
  q6 = n6; q9 = n9
  c6 = c9 = 0
  while q6 > 0:
    c6 += int(q6%6)
    q6 = int(q6//6)
  while q9 > 0:
    c9 += int(q9%9)
    q9 = int(q9//9)
  if m > c9 + c6:
    m = c9 + c6
print(m)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Mon Aug  6 17:34:40 2018

@author: Yuki
"""

ans = [0] * 100100
ans[0] = 0

n = int(input())
#n = 127
for i in range(1,n+1):
    cand1 = ans[i-1]
    cand2 = 100001
    cand3 = 100001
    x = 6
    while (x<=i):
        #cand2 = min(ans[i-x], cand2)
        cand2 = ans[i-x]
        x=6*x
    y = 9
    while (y<=i):
        #cand3 = min(ans[i-y], cand3)
        cand3 = ans[i-y]
        y=9*y
    ans[i] = min(cand1,cand2,cand3) + 1


print(ans[n])

Submission status: Accepted

Solution code:
ans = [0] * 100100
ans[0] = 0

n = int(input())
#n = 127
for i in range(1,n+1):
    cand1 = ans[i-1]
    cand2 = 100001
    cand3 = 100001
    x = 6
    while (x<=i):
        cand2 = min(ans[i-x], cand2)
        x=6*x
    y = 9
    while (y<=i):
        cand3 = min(ans[i-y], cand3)
        y=9*y
    ans[i] = min(cand1,cand2,cand3) + 1


print(ans[n])

Submission status: Accepted

Solution code:
n = int(input())

nums = []
for i in range(n+1):
    num = 0
    k=0
    while 6**k <= i:
        num += int(i/(6**k))%6
        k+=1
    k=0
    while 9**k <= n-i:
        num += int((n-i)/(9**k))%9
        k+=1
    
    nums.append(num)

print(min(nums))

Submission status: Accepted

Solution code:
from itertools import count, takewhile

def dfs(n:int, d={}) -> int:
    if n<6:
        return n
    
    if n in d:
        return d[n]
    
    max9 = max(takewhile(lambda x: x<=n, (9**i for i in count())))
    max6 = max(takewhile(lambda x: x<=n, (6**i for i in count())))
    
    d[n] = min(dfs(n-max9), dfs(n-max6))+1
    
    return d[n]

print(dfs(int(input())))

Submission status: Accepted

Solution code:
#!/usr/bin/python3

from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def main():
    N = int(input())
    dp = [INF] * (N + 2)
    dp[0] = 0

    for a in [9, 6]:
        for x in range(1, N):
            if a ** x > N:
                break
            for i in range(N):
                if i + a ** x <= N:
                    dp[i + a ** x] = min(dp[i + a ** x], dp[i] + 1)

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

    print(dp[N])
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())

dp = np.zeros(N+1, dtype=int)

dp[0] = 0


for n in range(1, N+1):
    minv = dp[n-1]

    multi = 1
    six = n - int(pow(6, multi))
    while six >= 0:
        value = dp[six]
        if value < minv:
            minv = value
        multi += 1
        six = n - int(pow(6, multi))

    multi = 1
    nine = n - int(pow(9, multi))
    while nine >= 0:
        value = dp[nine]
        if value < minv:
            minv = value
        multi += 1
        nine = n - int(pow(9, multi))

    dp[n] = minv + 1

print(dp[N])

Submission status: Accepted

Solution code:
MAX_N = 10**5

N = int(input())

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

MONEY_LIST = [6**i for i in range(7)]
MONEY_LIST.extend([9**i for i in range(1,6)])
MONEY_LIST.sort()

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

Submission status: Accepted

Solution code:
N = int(input())
A = [1]
for i in range(1,7):
    A.append(6 ** i)
for i in range(1, 6):
    A.append(9 ** i)


A = sorted(A)
dp = [float("inf")] * (N+1)
dp[0] = 0

for i in range(1,N+1):
    for k, v in enumerate(A):
        if i >= v:
            dp[i] = min(dp[i], dp[i-v]+1)


print(dp[N])

Submission status: Accepted

Solution code:
INF, MAX_N = 1e9, 100000
coins = set()
coins.add(1)
six, nine = 6, 9
while six <= MAX_N:
    coins.add(six)
    six *= 6
while nine <= MAX_N:
    coins.add(nine)
    nine *= 9
coins = list(coins)

count = {}
for coin in coins:
    count[coin] = 1

for n in range(1, MAX_N + 1):
    if n in count.keys():
        continue
    count[n] = INF
    for coin in coins:
        if n - coin < 0:
            continue
        count[n] = min(count[n], count[n - coin] + 1)

print(count[int(input())])

Submission status: Accepted

Solution code:
n = int(input())
num = float("inf")
for i in range(n + 1):
    rec = 0
    k = i
    while k > 0:
        rec += k % 6
        k = k // 6
    k = n - i
    while k > 0:
        rec += k % 9
        k = k // 9
    num = min(num, rec)

print(num)