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())
dp = [float('inf')] * (10**5+1)
dp[0] = 0

for i in range(1, N+1):
    dp[i] = min(dp[i-1], dp[i-6], dp[i-6**2], dp[i-6**3], dp[i-6**4], dp[i-6**5], dp[i-6**6],
                dp[i-9], dp[i-9**2], dp[i-9**3], dp[i-9**4], dp[i-9**5]) + 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 += int(t % 6)
		t = int(t / 6)
	t = N - i
	while t > 0:
		cc += int(t % 9)
		t = int(t / 9)
	if res > cc:
		res = cc
print(res)

Submission status: Accepted

Solution code:
from itertools import count, takewhile, dropwhile

def dfs(n, max9, max6, d={0:0}):
  if n in d: return d[n]
  
  max9 = next(dropwhile(lambda x: x>n, (max9 / 9**i for i in count())))
  max6 = next(dropwhile(lambda x: x>n, (max6 / 6**i for i in count())))
  d[n] = min(dfs(n-max9, max9, max6), dfs(n-max6, max9, max6)) + 1
  return d[n]

n = int(input())

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

print(dfs(n, max9, max6))

Submission status: Accepted

Solution code:
N = int(raw_input())
p = [1]
for j in [6, 9]:
  i = j
  while i <= N:
    p.append(i)
    i *= j
c = [N] * (N+1)
c[0] = 0
for i in range(0, N+1):
  for j in p:
    if i+j <= N:
      c[i+j] = min(c[i+j], c[i]+1)
print c[N]

Submission status: Accepted

Solution code:
#!/bin/python

import math
import os
import random
import re
import sys

def dp(N):
    global yen
    if table.get(N) != None:
        return table.get(N)
    if N == 0:
        return 0
    if N < 0:
        return sys.maxint
    result = sys.maxint
    for i in range(len(yen)):
        result = min(result,dp(N-yen[i]))
    table[N] = 1+result
    return 1+result

def solution(N):
    return dp(N)
        
table = {}

if __name__ == '__main__':
    minVal = sys.maxint
    N = int(raw_input())
    yen = [59049,46656,7776,6561,1296,729,216,81,36,9,6,1]
    result = solution(N)

    print result

Submission status: Accepted

Solution code:
INF = 10 ** 20

n = int(input())

dp = [INF for _ in range(n + 1)]
dp[0] = 0
lst = [1]
acc = 6
while acc <= n:
  lst.append(acc)
  acc *= 6
acc = 9
while acc <= n:
  lst.append(acc)
  acc *= 9
lst.sort()

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

print(dp[n])

Submission status: Accepted

Solution code:
def s(a,b):return a if a<b else s(a//b,b)+a%b
n=int(input());print(min(s(i,6)+s(n-i,9)for i in range(n+1)))

Submission status: Accepted

Solution code:
n = int(input())

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

# dp[i] = i円を引き出すのに必要な最低回数
# dp[i] = min(dpcd [i-6**p]+1,dp[i-9**q],dp[i])

Submission status: Accepted

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

N = int(input())

A = [1]
i = 1
while 6 ** i <= 100000:
    A.append(6 ** i)
    i += 1
j = 1
while 9 ** j <= 100000:
    A.append(9 ** j)
    j += 1
A.sort()  # 引き出せる金額のリスト

table = [1000000 for _ in range(N + 1)]  # i円を引き出す最小の操作回数をメモ、参照するのは常に前の値なのでループを回せる
table[0] = 0

for i in range(1, N+1):
    a = 0
    while 6 ** a <= i:
        table[i] = min(table[i], table[i - 6 ** a] + 1)  # 1円,6円,36円,...を使って操作回数を減らす
        a += 1
    b = 0
    while 9 ** b <= i:
        table[i] = min(table[i], table[i - 9 ** b] + 1)  # 1円,9円,81円,...を使って操作回数を減らす
        b += 1

print(table[N])

Submission status: Accepted

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

N = int(input())

A = [1]
i = 1
while 6 ** i <= 100000:
    A.append(6 ** i)
    i += 1
j = 1
while 9 ** j <= 100000:
    A.append(9 ** j)
    j += 1
A.sort()

table = [1000000 for _ in range(N + 1)]
table[0] = 0

for i in range(1, N+1):
    a = 0
    while 6 ** a <= i:
        table[i] = min(table[i], table[i - 6 ** a] + 1)
        a += 1
    b = 0
    while 9 ** b <= i:
        table[i] = min(table[i], table[i - 9 ** b] + 1)
        b += 1

print(table[N])

Submission status: Accepted

Solution code:
n = int(input())
options = []
x = 6
while x <= n:
    options.append(x)
    x *= 6
x = 9
while x <= n:
    options.append(x)
    x *= 9
dp = list(range(n + 1))
for opt in options:
    for i in range(n - opt + 1):
        dp[i + opt] = min(dp[i + opt], dp[i] + 1)
print(dp[-1])

Submission status: Accepted

Solution code:
def by6(x):
    res = 0
    k = 6**7
    while x > 0:
        while x >= k:
            x -= k
            res += 1
        k /= 6
    return res
def by9(x):
    res = 0
    k = 9**6
    while x > 0:
        while x >= k:
            x -= k
            res += 1
        k /= 9
    return res
n = int(input())
ans = n
for i in range(n + 1):
    ans = min(ans, by6(i) + by9(n - i))
print(ans)