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: Wrong Answer

Solution code:
n = int(input())

def search(n,num):
    i = 1
    while True:
        if n < num**i:
            return i-1
        i += 1
        
ans = n
for i1 in range(0,6):
    for i2 in range(0,6):
        for i3 in range(0,6):
            for i4 in range(0,6):
                for i5 in range(0,6):
                    for i6 in range(0,6):
                            res = n
                            res -= (6**1)*i1+(6**2)*i2+(6**3)*i3+(6**4)*i4+(6**5)*i5+(6**6)*i6
                            if res > 0:
                                count = i1+i2+i3+i4+i5+i6
                                for i in reversed(range(1,6)):
                                    cnt = int(res / (9**i))
                                    res -= (9**i) * cnt
                                    count += cnt
                                count += res
                                if ans > count:
                                    ans = count
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())

def search(n,num):
    i = 1
    while True:
        if n < num**i:
            return i-1
        i += 1
        
ans = n
for i1 in range(0,6):
    for i2 in range(0,6):
        for i3 in range(0,6):
            for i4 in range(0,6):
                for i5 in range(0,6):
                    for i6 in range(0,6):
                            res = n
                            res -= (6**1)*i1+(6**2)*i2+(6**3)*i3+(6**4)*i4+(6**5)*i5+(6**6)*i6
                            if res > 0:
                                count = i1+i2+i3+i4+i5+i6
                                for i in reversed(range(1,6)):
                                    cnt = int(res / (9**i))
                                    res -= (9**i) * cnt
                                    count += cnt
                                if ans > count:
                                    ans = count
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())

def search(n,num):
    i = 1
    while True:
        if n < num**i:
            return i-1
        i += 1
        
ans = n
for i1 in range(0,6):
    for i2 in range(0,6):
        for i3 in range(0,6):
            for i4 in range(0,6):
                for i5 in range(0,6):
                    for i6 in range(0,6):
                            res = n
                            res -= (6**1)*i1+(6**2)*i2+(6**3)*i3+(6**4)*i4+(6**5)*i5+(6**6)*i6
                            if res > 0:
                                count = i1+i2+i3+i4+i5+i6
                                while res > 6:
                                    nine_val = search(res,9)
                                    nine_count = int(res/(9**nine_val))
                                    count += nine_count
                                    res -= (9**nine_val) * nine_count
                                count += res
                                if ans > count:
                                    ans = count
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())

def search(n,num):
    i = 1
    while True:
        if n < num**i:
            return i-1
        i += 1
        
ans = n
for i1 in range(0,6):
    for i2 in range(0,6):
        for i3 in range(0,6):
            for i4 in range(0,6):
                for i5 in range(0,6):
                    for i6 in range(0,6):
                            res = n
                            res -= (6**1)*i1+(6**2)*i2+(6**3)*i3+(6**4)*i4+(6**5)*i5+(6**6)*i6
                            if res > 0:
                                count = i1+i2+i3+i4+i5+i6
                                while res > 9:
                                    nine_val = search(res,9)
                                    nine_count = int(res/9**nine_val)
                                    count += nine_count
                                    res -= (9**nine_val) * nine_count
                                count += res
                                if ans > count:
                                    ans = count
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())

def search(n,num):
    i = 1
    while True:
        if n < num**i:
            return i-1
        i += 1
        
ans = n
for i1 in range(0,6):
    for i2 in range(0,6):
        for i3 in range(0,6):
            for i4 in range(0,6):
                for i5 in range(0,6):
                    for i6 in range(0,6):
                        for i7 in range(0,6):
                            res = n
                            res -= (6**1)*i1+(6**2)*i2+(6**3)*i3+(6**4)*i4+(6**5)*i5+(6**6)*i6*(6**7)*i7
                            if res > 0:
                                count = i1+i2+i3+i4+i5+i6
                                while res > 6:
                                    nine_val = search(res,9)
                                    nine_count = int(res/9**nine_val)
                                    count += nine_count
                                    res -= (9**nine_val) * nine_count
                                count += res
                                if ans > count:
                                    ans = count
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())

def search(n,num):
    i = 1
    while True:
        if n < num**i:
            return i-1
        i += 1
        
ans = n
for i1 in range(0,6):
    for i2 in range(0,6):
        for i3 in range(0,6):
            for i4 in range(0,6):
                for i5 in range(0,6):
                    for i6 in range(0,6):
                        res = n
                        res -= (6**1)*i1+(6**2)*i2+(6**3)*i3+(6**4)*i4+(6**5)*i5+(6**6)*i6
                        if res > 0:
                            count = i1+i2+i3+i4+i5+i6
                            while res > 6:
                                nine_val = search(res,9)
                                nine_count = int(res/9**nine_val)
                                count += nine_count
                                res -= (9**nine_val) * nine_count
                            count += res
                            if ans > count:
                                ans = count
print(ans)

Submission status: Wrong Answer

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 = sys.maxint
    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()