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:

import math as m

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

k_six =int(m.log(n, 6)) + 1
k_nine = int(m.log(n, 9)) + 1

plus = set([1] + [6**(i+1) for i in range(k_six)] + [9**(i+1) for i in range(k_nine)])

for i in range(n+1):
    for p in plus:
        if i + p > n:
            continue
        if dp[i+p]<0:
            dp[i+p] = dp[i] + 1
        else:
            dp[i+p] = min(dp[i]+1, dp[i+p])

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

Submission status: Accepted

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

Submission status: Accepted

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

ans = n
l = (int)(math.log(n, 9)+1)

for i in range(n+1):
  tmp_ans = 0
  a_six = i
  a_nine = n-i
  for i in reversed(range(7)):
    tmp = a_six//6**i
    tmp_ans += tmp
    a_six -= tmp*6**i
  a_nine += a_six
  for i in reversed(range(7)):
    tmp = a_nine//9**i
    tmp_ans += tmp
    a_nine -= tmp*9**i
  if ans > tmp_ans:
    ans = tmp_ans

print(ans)

Submission status: Accepted

Solution code:
#import time


def func():
    N = int(input())
    step = [0 for i in range(N+1)]

    for i in range(1, N+1):
        minimum = step[i-1]+1
        p = 0
        r = 0
        while i >= 9 ** (p+1):
            p += 1
            minimum = min(minimum, 1+step[i-9**p])
        while i >= 6 ** (r+1):
            r += 1
            minimum = min(minimum, 1+step[i-6**r])
        step[i] = minimum

    print(step[N])

if __name__ == "__main__":
 #   start = time.time()
    func()
 #   elapsed_time = time.time() - start
 #   print("elapsed_time:{0}".format(elapsed_time) + "[sec]")

Submission status: Accepted

Solution code:
from bisect import bisect_right
import sys
from functools import lru_cache

sys.setrecursionlimit(10**8)

N = int(input())

# Nの範囲に伴う累乗の範囲
# 1: inf
# 6: 1-6
# 9: 1-5

l = [6**i for i in range(1, 6+1)] + [9**i for i in range(1, 5+1)]
l.sort()

# print(l)

@lru_cache(maxsize=None)
def dfs(n):
	r = bisect_right(l, n)
	if r <= 0:
		return n
	min_num = 10**9
	for i in range(r):
		min_num = min(min_num, dfs(n-l[i])+1)
	return min_num

print(dfs(N))

Submission status: Accepted

Solution code:
n = int(input())
six_list = [1,6,36,216,1296,7776,46656]
nine_list = [1,9,81,729,6561,59049]
six_list.reverse()
nine_list.reverse()
rest = n
ans = n

#問題の条件に6の累乗だけでなく9の累乗もあるから話がややこしくなる（6と9の累乗をまとめたリストの大きいものから引き出していっても最適解にならない)
#そこで問題を分割するために、n円のうち、いくら分を6の累乗の形で引き出し、残りを9の累乗の形で引き出すかを全部試す

for a in range(n+1):
        
        six_rest = a #n円のうちa円を6の累乗の形で引き出す
        nine_rest = n-a
        count_6 = 0
        count_9 = 0
        for number in six_list:
                if six_rest//number >= 1:
                        count_6 += six_rest//number
                        six_rest -= six_rest//number * number
        for number in nine_list:
                if nine_rest//number >= 1:
                        count_9 += nine_rest//number
                        nine_rest -= nine_rest//number * number
        if ans > count_6 + count_9:
                ans = count_6 + count_9

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
ans = N
for i in range(N // 9 + 1):
  cnti = 0
  _i = i
  while _i :
    cnti += _i % 9
    _i //= 9
  cntj = 0
  j = (N - 9 * i) // 6
  _j = j
  while _j:
    cntj += _j % 6
    _j //= 6
  ans = min(cnti + cntj + N - 9 * i - 6 * j, ans)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

A = []

tmp = 6

while tmp<=N:
    A.append(tmp)
    tmp = tmp*6
    

tmp = 9

while tmp<=N:
    A.append(tmp)
    tmp = tmp*9
    
A.sort()
    
dp = [[0 for i in range(N+1)] for j in range(len(A)+1)]

for i in range(N+1):
    dp[0][i] = i
    
for i in range(len(A)):
    for j in range(N+1):
        if A[i]<=j:
            dp[i+1][j] = min(dp[i+1][j-A[i]]+1, dp[i][j])
        else:
            dp[i+1][j] = dp[i][j]
            
print(dp[len(A)][N])

Submission status: Accepted

Solution code:
# encoding: utf-8
N = int(input())

memo = [None] * (N + 1)

def cut(val, pow6, pow9):
    # print("#", val, pow6, pow9)
    rets = [100000] * 2
    if memo[val] != None: return memo[val]
    # maximum 6 ** x
    p6_tmp = pow6
    for x in list(range(pow6))[::-1]:
        if val < (6 ** (x + 1)): p6_tmp -= 1
        else:
            rets[0] = cut(val - (6 ** (x + 1)), p6_tmp, pow9) + 1
            break
    else: rets[0] = val
    # maximum 9 ** x
    p9_tmp = pow9
    for x in list(range(pow9))[::-1]:
        if val < (9 ** (x + 1)): p9_tmp -= 1
        else:
            rets[1] = cut(val - (9 ** (x + 1)), pow6, p9_tmp) + 1
            break
    else: rets[1] = val
    # return
    ret = min(rets)
    if memo[val] == None: memo[val] = ret
    return ret

print(cut(N, 32, 32))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
res = float('inf')
for a in range(n+1):
    # 6の累乗としてa円引き出す
    rest = n - a
    cnt = 0
    for i in range(6,-1,-1):
        if a // (6**i) != 0:
            cnt += a // (6**i)
            a %= 6 ** i
    for i in range(5,-1,-1):
        if rest // (9**i) != 0:
            cnt += rest // (9**i)
            rest %= 9 ** i
    res = min(res, cnt)
print(res)

Submission status: Accepted

Solution code:
N = int(input())

reslis = []
for i in range(N + 1):
    count = 0
    temp = i
    while True:
        count += temp % 9
        if temp//9 == 0:
            break
        else:
            temp = temp//9
    temp = N - i
    while True:
        count += temp % 6
        if temp//6 == 0:
            break
        else:
            temp = temp//6
    reslis.append(count)


reslis.sort()
print(reslis[0])

Submission status: Accepted

Solution code:
N = int(input())
table = [1e100 for i in range(100000 + 10)]
table[0] = 0

for i in range(1, 8):
    if 6 ** i <= 100000 + 10:
        table[6 ** i] = 1

    if 9 ** i <= 100000 + 10:
        table[9 ** i] = 1

for i in range(1, 100000 + 10):
    table[i] = table[i - 1] + 1
    for j in range(1, 8):
        if i - 6 ** j >= 0:
            table[i] = min(table[i], table[i - 6 ** j] + 1)
        if i - 9 ** j >= 0:
            table[i] = min(table[i], table[i - 9 ** j] + 1)

print(table[N])

Submission status: Accepted

Solution code:
import math

N = int(input())
# A = [int(x) for x in input().split()]


C = [1]
for i in range(math.floor(math.log(N,9)) + 2):
    if i !=0 :
        C.append(9 ** i)
for i in range(math.floor(math.log(N,6)) + 2):
    if i != 0:
        C.append(6 ** i)


INF = 10**10
dp = [INF] * (N+1)
dp[0] = 0

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

print(dp[N])

Submission status: Accepted

Solution code:
import math

N = int(input())
# A = [int(x) for x in input().split()]


C = [1]
for i in range(math.ceil(math.log(N,9)) + 3):
    if i !=0 :
        C.append(9 ** i)
for i in range(math.ceil(math.log(N,6)) + 3):
    if i != 0:
        C.append(6 ** i)


INF = 10**10
dp = [INF] * (N+1)
dp[0] = 0

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

print(dp[N])

Submission status: Accepted

Solution code:
from math import log
n = int(input())
a = 10**5

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

Submission status: Accepted

Solution code:
N = int(input())
nine = [9**5, 9**4, 9**3, 9**2, 9, 1]
six = [6**6, 6**5, 6**4, 6**3, 6**2, 6, 1]
counter = 100000

for i in range(N+1):
    j = N-i
    countN = 0
    for k in nine:
        if not i:
            break
        countN += i // k
        i = i % k

    countS = 0
    for k in six:
        if not j:
            break
        countS += j // k
        j = j % k

    counter = min(counter, countN+countS)

print(counter)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
paySix = []
payNine = []
i = 0
while 6**i <= n:
   paySix.append(6**i)
   i += 1
i = 0
while 9**i <= n:
   payNine.append(9**i)
   i += 1

maxCount = n
sum = 0
for j in range(n+1):
    count = 0
    count6 = 0
    count9 = 0
    nine = j
    six = n - j
    for i in reversed(range(len(payNine))):
        count9 += int(nine/payNine[i])
        nine -= int(nine/payNine[i])*payNine[i]
    # print("\ndiv target:{} 9Count:{}".format(j, count9))
    for i in reversed(range(len(paySix))):
        count6 += int(six/paySix[i])
        six -= int(six/paySix[i])*paySix[i]
    # print("div target:{} 6Count:{}".format(n-j, count6))
    maxCount = min(maxCount, count9+count6)
print(maxCount)
"""
pay = [1]
i = 1
while 6**i <= n:
   pay.append(6**i)
   i += 1
i = 1
while 9**i <= n:
   pay.append(9**i)
print(i)
pay = sorted(pay)
print(len(pay))
count = 0
for i in reversed(range(len(pay))):
    # print(i)
    count += int(n/pay[i])
    n -= int(n/pay[i])*pay[i]
    if n == 0:
        print(count)
"""
""""
for i in range(1, 100000):
    if 9 ** i < n:
        nine.append(9 ** i)
    else:
        break
for i in range(1, 100000):
    if 6 ** i < n:
        six.append(6 ** i)
    else:
        break

count = 0
last = n
while last >= 9:
    if nine:
        while nine[-1] > last:
            nine.pop()
    if six:
        while six[-1] > last:
            six.pop()

    if nine:
        tmp9 = nine[-1]
        num9 = int(last / tmp9)
    if six:
        tmp6 = six[-1]
        num6 = int(last / tmp6)

    if num9 < num6:
        count += num9
        last %= tmp9
        nine.pop()
    elif num9 == num6 and last % tmp9 <= last % tmp6:
        count += num9
        last %= tmp9
        nine.pop()
    else:
        count += num6
        last %= tmp6
        six.pop()


count += int(last / 6)
last %= 6
print(count + last)
"""

Submission status: Accepted

Solution code:
N = int(input())

def base_n(x, n):
    results = 0
    while x > 0:
        results += x % n
        x //= n
    return results

print(min([base_n(i, 6) + base_n(N - i, 9) for i in range(N + 1)]))

Submission status: Accepted

Solution code:
import itertools
N = int(input())

base = [1]
for i in range(1, 7):
    if 6 ** i <= N:
        base.append(6 ** i)
for i in range(1, 6):
    if 9 ** i <= N:
        base.append(9 ** i)
ans = N
dp = [0] * (N + 1)
for i in range(1, N + 1):
    dp[i] = min([dp[i - j] + 1 if i - j >= 0 else j for j in base])

print(dp[N])

Submission status: Accepted

Solution code:
def calc(x, base):
    res = 0
    while x:
        x, m = divmod(x, base)
        res += m
    return res


def main():
    N = int(input())
    ans = min(calc(i, 6) + calc(N - i, 9) for i in range(N + 1))
    print(ans)


main()

Submission status: Accepted

Solution code:
n = int(input())

min_cnt = float('inf')
for i in range(0, n+1, 9):
    cnt = 0
    t = i
    while t >= 9:
        cnt += t % 9
        t //= 9
    cnt += t

    t = (n-i)
    while t >= 1:
        cnt += t % 6
        t //= 6
    cnt += t

    if cnt < min_cnt:
        min_cnt = cnt
print(min_cnt)

Submission status: Accepted

Solution code:
N = int(input())

ans = N
for i in range(N + 1):
    nine, pvt = 0, i
    while pvt > 0:
        nine += pvt % 9
        pvt //= 9

    six, pvt = 0, N - i
    while pvt > 0:
        six += pvt % 6
        pvt //= 6
    
    ans = min(ans, nine + six)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
koho = [1]
i=1
while True:
    if i > 1e6:
        break
    i *= 6
    koho.append(i)
i=1
while True:
    if i > 1e6:
        break
    i *= 9
    koho.append(i)

dp = [0] * (N+1)
for i in range(1, N+1):
    tmp = []
    for k in koho:
        if k > i:
            continue
        tmp.append(dp[i - k] + 1)
    dp[i] = min(tmp)
print(dp[N])

Submission status: Accepted

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

Submission status: Accepted

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

hiki9 = []
hiki6 = []
n = int(log(N) / log(9) + 1)  # log9の計算に誤差があるので一つ多めに取っておく
for i in range(n+1):
    hiki9.append(9**i)
n = int(log(N) / log(6) + 1)
for i in range(n+1):
    hiki6.append(6**i)
hiki9.sort(reverse=True)
hiki6.sort(reverse=True)
x = []
for i in range(N+1):
    n9 = i
    tmpx = 0
    for h in hiki9:
        while h <= n9:
            n9 -= h
            tmpx += 1
    n6 = N - i
    for h in hiki6:
        while h <= n6:
            n6 -= h
            tmpx += 1
    x.append(tmpx)
x.sort()
print(x[0])

Submission status: Accepted

Solution code:
N = int(input())
B6 = [6**i for i in range(1,7)]
B9 = [9**i for i in range(1,6)]
L = B6 + B9
L = sorted(list(set(L)))
dp = [int(i) for i in range(N+1)]

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

Submission status: Accepted

Solution code:
#ABC099C
N=int(input())
i=0
t=0
ans=N
for i in range(N+1):
    nine = 0
    six = 0
    t=i
    while (t>0):
        nine+=t%9
        t//=9
    t=N-i
    while (t>0):
        six+=t%6
        t//=6
    if ans>nine+six:
        ans=nine+six
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

INF = float('inf')
dp = [INF for i in range(n+1)]

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

print(dp[n])

Submission status: Accepted

Solution code:
N = int(input())
B6 = [6**i for i in range(1,8)]
B9 = [9**i for i in range(1,7)]
L = sorted(list(set(B6+B9)))
dp = [i for i in range(N+1)]
for i in L :
    for j in range(i,N+1) :
        dp[j] = min(dp[j], dp[j-i]+1)
print(dp[-1])

Submission status: Accepted

Solution code:
N = int(input())
B6 = [6**i for i in range(1,8)]
B9 = [9**i for i in range(1,7)]
L = sorted(list(set((B6+B9))))
dp = [i for i in range(N+1)]
for i in L :
    for j in range(i,N+1) :
        dp[j] = min(dp[j], dp[j-i]+1)
print(dp[-1])

Submission status: Accepted

Solution code:
N = int(input())

dp = [i for i in range(N+1)]
B6 = [6**i for i in range(1,8)]
B9 = [9**i for i in range(1,7)]
L = B6 + B9
L = sorted(list(set(L)))

for i in L :
    for j in range(i, N+1) :
        dp[j] = min(dp[j-i]+1, dp[j])
print(dp[-1])

Submission status: Accepted

Solution code:
import itertools
N = int(input())

sixs = [6, 36, 216, 1296, 7776, 46656]

ans = N
for ptn in itertools.product(range(6), repeat=6):
    money = ope = 0
    for s,p in zip(sixs,ptn):
        money += s*p
        ope += p
    if money > N: continue
    if ope > ans: continue
    rem = N - money
    while rem:
        ope += rem%9
        rem //= 9
    ans = min(ans, ope)
print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10**5)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n = ni()

res = 1
coin = [1]
i = 1
while res < 10**5:
    coin.append(6**i)
    i += 1
    res *= 6
    
res = 1
i = 1
while res < 10**5:
    coin.append(9**i)
    i += 1
    res *= 9
    
coin.sort()
    
dp = [10**5]*(n+1)
dp[0] = 0

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

Submission status: Accepted

Solution code:
#公式解法見て書いた
iN = int(input())

a6 = [0]*7
for i in range(7):
    a6[i] = 6 ** i
a6.reverse()
a9 = [0]*6
for i in range(6):
    a9[i] = 9 ** i
a9.reverse()

iAns = iN
for i in range(iN+1):
    iD = iN - i
    iC = 0
    for j in range(7):
        if i:
            iG = a6[j]
            if i >= iG:
                iC += (i // iG)
                i %=iG
    if iAns <= iC:
        continue
    for j in range(6):
        if iD :
            iG = a9[j]
            if iD >= iG:
                iC += (iD // iG)
                iD %= iG
    if iAns > iC:
        iAns = iC
print(iAns)

Submission status: Accepted

Solution code:
#公式解法見て書いた
iN = int(input())

a6 = [0]*7
for i in range(7):
    a6[i] = 6 ** i
a6.reverse()
a9 = [0]*6
for i in range(6):
    a9[i] = 9 ** i
a9.reverse()

iAns = iN
for i in range(iN+1):
    iD = iN - i
    iC = 0
    for j in range(7):
        if i:
            iG = a6[j]
            if i >= iG:
                iC += (i // iG)
                i %=iG
    for j in range(6):
        if iD :
            iG = a9[j]
            if iD >= iG:
                iC += (iD // iG)
                iD %= iG
    if iAns > iC:
        iAns = iC
print(iAns)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin


d_in = lambda: int(stdin.readline())  # N = d_in()


def get_order(n, m):
    order = 0
    while n > 0:
        n = n // m
        order += 1
    return order


def decimal2bit(n, m):
    """
    nのm進数表現
    """
    if n == 0:
        return []
    order = get_order(n, m)
    ans = []
    for i in range(order, -1, -1):
        ans.append(n // (m ** i))
        n -= m ** i * ans[-1]
    return ans


def search(n):
    ans = float('inf')
    for i in range(n // 9 + 1):
        nine = decimal2bit(9 * i, 9)
        six = decimal2bit(n - 9 * i, 6)
        ans = min(ans, sum(nine) + sum(six))
    print(ans)


if __name__ == '__main__':
    N = d_in()
    search(N)

Submission status: Accepted

Solution code:
N = int(input())
B6 = [6**i for i in range(1,7)]
B9 = [9**i for i in range(1,6)]
L = B6 + B9
L = sorted(list(set(L)))
dp = [i for i in range(N+1)]
for i in L :
    for j in range(i,(N+1)) :
        dp[j] = min(dp[j-i]+1,dp[j])
ans = dp[N]
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

cands = [1]
for i in range(1, 10):
    if 6**i <= 100000:
        cands.append(6**i)
    if 9**i <= 100000:
        cands.append(9**i)
cands = sorted(cands)

ans = list(range(n+1))
for c in cands[1:]:
    for i in range(n+1):
        if i < c:
            pass
        else:
            ans[i] = min(ans[i], ans[i-c] + 1)
print(ans[-1])

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

    t = n - i
    while t > 0:
        cnt += t % 9
        t //= 9

    ans = min(ans, cnt)

print(ans)

Submission status: Accepted

Solution code:
n = int(input())

c = [i for i in range(n + 1)]

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

Submission status: Accepted

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

Submission status: Accepted

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