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

res=n
for i in range(n+1):
    count=0
    j=n-i
    while i>0:
        count+=i%6
        i//=6
    while j>0:
        count+=j%9
        j//=9
    if res>count:
        res=count

print(int(res))

Submission status: Accepted

Solution code:
N = int(input())

dp = [10**9] * (N+1)
dp[0], dp[1] = 0, 1
i = 6
while i<=N:
    dp[i] = 1
    i *= 6
i = 9
while i<=N:
    dp[i] = 1
    i *= 9

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

print(dp[N])

Submission status: Accepted

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
N = int(input())

dp = [10**9] * (N+1)
dp[1] = 1
# dp[6] = 1
# dp[9] = 1
i = 6
while i <= N:
    dp[i] = 1
    i *= 6
i = 9
while i <= N:
    dp[i] = 1
    i *= 9

for i in range(1, N):
    if dp[i] != 10**9:
        dp[i+1] = min(dp[i+1], dp[i]+1)
        j = 6
        while i+j <= N:
            dp[i+j] = min(dp[i+j], dp[i]+1)
            j *= 6
        j = 9
        while i+j <= N:
            dp[i+j] = min(dp[i+j], dp[i]+1)
            j *= 9
print(dp[N])

Submission status: Accepted

Solution code:
n=int(input())
dp=[i for i in range(100001)]
for i in range(100001):
    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
else:
    print(dp[n])

Submission status: Accepted

Solution code:
n = int(input())

max_range = 10 ** 5
dp = [int(i) for i in range(max_range + 1)]

for i in [6,9]:
    check = i
    while check < max_range:
        for j in range(max_range + 1):
            if j - check >= 0:
                dp[j] = min(dp[j],dp[j-check] + 1)

        check =  check * i
        
print(dp[n])

Submission status: Accepted

Solution code:
import itertools
import numpy as np
import sys
input = sys.stdin.readline
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()


N = I()

ans = 10e10
for i in range(N+1):
    j = N-i
    cnt = 0
    while i > 0:
        cnt += i%6
        i //= 6
    while j > 0:
        cnt += j%9
        j //= 9
    ans = min(ans,cnt)

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N] = [long(input_raw[0])]
    coin_list = [1]
    for i in range(1, N):
        if N >= 6 ** i:
            coin_list.append(6 ** i)
        else:
            break

    for i in range(1, N):
        if N >= 9 ** i:
            coin_list.append(9 ** i)
        else:
            break

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

if __name__ == '__main__':
    main()