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

ans = 0
mod_base = [59409, 46656, 7776, 6561, 1296, 729, 216, 81, 36, 9, 6, 1]
mod_list = [59409, 46656, 7776, 6561, 1296, 729, 216, 81, 36, 9, 6, 1]
ans_list = [0 for _ in range(100000)]

for mod in mod_base:
	ans_list[mod - 1] = 1

for i in range(10000):
	if ans_list[n - 1] != 0:
		break
	new_mod_list = []
	for j in mod_list:
		for k in mod_base:
			if j + k <= 100000 and ans_list[j + k - 1] == 0:
				new_mod_list.append(j + k)
				ans_list[j + k - 1] = i + 2
	mod_list = sorted(list(set(new_mod_list)), reverse=True)

print(ans_list[n - 1])

Submission status: Wrong Answer

Solution code:
n = int(input())

ans = 0
mod_base = [59409, 46656, 7776, 6561, 1296, 729, 216, 81, 36, 9, 6, 1]
mod_list = [59409, 46656, 7776, 6561, 1296, 729, 216, 81, 36, 9, 6, 1]
ans_list = [0 for _ in range(100000)]

for mod in mod_base:
	ans_list[mod - 1] = 1

for i in range(100):
	if ans_list[n - 1] != 0:
		break
	new_mod_list = []
	for j in mod_list:
		for k in mod_base:
			if j + k <= 100000 and ans_list[j + k - 1] == 0:
				new_mod_list.append(j + k)
				ans_list[j + k - 1] = i + 2
	mod_list = sorted(list(set(new_mod_list)), reverse=True)

print(ans_list[n - 1])

Submission status: Wrong Answer

Solution code:
n = int(input())

ans = 0
owari = False

mod_list = [59409, 46656, 7776, 6561, 1296, 729, 216, 81, 36, 9, 6]

i = 0

while owari == False and i <= 10:
	for j in mod_list[i:]:
		if n % j == 0:
			owari = True
			print(ans + n // j)
			break
	ans += n // mod_list[i]
	n = n % mod_list[i]
	i += 1

if owari == False:
	print(ans + n)

Submission status: Wrong Answer

Solution code:
n = int(input())

ans = 0

mod_list = [59409, 46656, 7776, 6561, 1296, 729, 216, 81, 36, 9, 6]

for i in mod_list:
#	print(n // i)
	ans += n // i
	n = n % i

print(ans + n)

Submission status: Wrong Answer

Solution code:
n = int(input())

ans = 0

mod_list = [59409, 46656, 7776, 6561, 1296, 729, 216, 81, 36, 9, 6]

for i in mod_list:
	print(n // i)
	ans += n // i
	n = n % i

print(ans + n)

Submission status: Wrong Answer

Solution code:
n = int(input())
ans = float('Inf')
memo_n = [0]*10
memo_s = [0]*10
for i in range(1, 10):
  memo_n[i] = 9**i
  memo_s[i] = 6**i

def f(n, count):
  global ans

  if n < 6:
    ans = min(ans, count + n)
    return
  
  nine = 0
  for i in memo_n:
    if i < n:
      nine = i
  
  six = 0
  for i in memo_s:
    if i < n:
      six = i

  if nine >= 9:
    f(n - nine, count + 1)
  
  if six >= 6:
    f(n - six, count + 1)

f(n, 0)
print(ans)