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: Runtime Error

Solution code:
def re(r,k,l):
    if k==0:return r
    while(k<l[0]):
        l=l[1:]
    return re(r+1,k-l[0],l)





n=int(input())
i=1
l6=[]
ans=10**5
while(i<n):
    l6.append(i)
    i*=6
i=1
l9=[]
while(i<n):
    l9.append(i)
    i*=9
l6.sort(reverse=True)
l9.sort(reverse=True)
for i in range(n):
    ans=min(ans,re(0,n-i,l6)+re(0,i,l9))
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
dp = [float("Inf")]*(n+1)
for i in range(6):
    dp[i] = i
for i in range(n+1):
    power = 1
    while i >= 6 ** power:
        dp[i] = min(dp[i],dp[i-6**power]+1)
        power += 1
    power = 1
    while i >= 9 ** power:
        dp[i] = min(dp[i],dp[i-9**power]+1)
        power += 1
print(dp[n])

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!
N=int(input())
l=[1]
count=0

def cand(num):
    i=1
    while N>=num**i:
        l.append(num**i)
        i+=1

def sub(target,index):
    i=0
    if target==0:
        
    elif index==0:
        
    while target-l[index]>0:
        sub(target-l[index]**i,l[index-1])
        

cand(6)
cand(9)

l.sort()
print(l)

#メモ　この方針があってるのかもわからん

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
n = int(input())
can = [1, 6, 9, 36, 81, 216, 729, 1296, 6561, 7776, 46656, 59049]
cnt = 0
s = len(can)-1
while n > 0:
  cnt += 1
  while(n - can[s] >= 0):
    s -= 1
  n = n - can[s]
print(cnt)

Submission status: Runtime Error

Solution code:
N = int(input())
INF = 10**6
dp = [INF] * (max(9, N))
for i in range(10):
  if  0 < i < 6:
    dp[i] = i
  elif i < 9:
    dp[i] = i%6+1
for i in range(N):
  n = m = 1
  while i+9**n <= N:
    dp[i+9**n] = min(dp[i+9**n], dp[i] + 1)
    n += 1
  while i+6**m <= N:
    dp[i+6**m] = min(dp[i+6**m], dp[i] + 1)
    m += 1
print(dp[N])

Submission status: Runtime Error

Solution code:
N = int(input())
INF = 10**6
dp = [INF] * (N+1)
for i in range(9):
  if i < 6:
    dp[i] = i
  elif i < 9:
    dp[i] = i%6+1

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

Submission status: Runtime Error

Solution code:
N = int(input())
INF = 10**6
dp = [INF] * (N+1)
for i in range(10):
  if i < 6:
    dp[i] = i
  elif i < 9:
    dp[i] = i%6+1
  else:
    dp[i] = 1
for i in range(N):
  n = m = 1
  while i+9*n > N:
    dp[i+9*n] = min(dp[i+9*n], dp[i] + 1)
    n += 1
  while i+6*m > N:
    dp[i+6*m] = min(dp[i+6*m], dp[i] + 1)
    m += 1
print(dp[N])

Submission status: Runtime Error

Solution code:
N = int(input())
INF = 10**6
dp = [INF] * (max(9, N)+1)
for i in range(10):
  if  0 < i < 6:
    dp[i] = i
  elif i < 9:
    dp[i] = i%6+1
  else:
    dp[i] = 1
for i in range(N):
  n = m = 1
  for j in range(1, 6):
    dp[i+j] = min(dp[i+j], dp[i] + j)
  while i+9**n <= N:
    dp[i+9**n] = min(dp[i+9**n], dp[i] + 1)
    n += 1
  while i+6**m <= N:
    dp[i+6**m] = min(dp[i+6**m], dp[i] + 1)
    m += 1
print(dp[N])

Submission status: Runtime Error

Solution code:
N = int(input())
INF = 10**6
dp = [INF] * (N+1)
for i in range(10):
  if  0 < i < 6:
    dp[i] = i
  elif i < 9:
    dp[i] = i%6+1
  else:
    dp[i] = 1
for i in range(N):
  n = m = 1
  while i+9**n <= N:
    dp[i+9**n] = min(dp[i+9**n], dp[i] + 1)
    n += 1
  while i+6**m <= N:
    dp[i+6**m] = min(dp[i+6**m], dp[i] + 1)
    m += 1
print(dp[N])

Submission status: Runtime Error

Solution code:
import heapq

n = int(input())
max_i = 0

while n>6**max_i:
  max_i+=1
  
cand_list = list(set([-6**i for i in range(max_i)] + [-9**i for i in range(max_i)]))

heapq.heapify(cand_list)
counter = 0

while n > 0:
  cand_n = -1 * heapq.heappop(cand_list)
  while n >= cand_n:
    n -= cand_n
    counter += 1
  
print(counter)

Submission status: Runtime Error

Solution code:
import heapq

n = int(input())
max_i = 0

while n>6**max_i:
  max_i+=1
  
cand_list = list(set([-6**i for i in range(max_i)] + [-9**i for i in range(max_i)]))

heapq.heapify(cand_list)
counter = 0

while n > 0:
  cand_n = -1 * heapq.heappop(cand_list)
  if n >= cand_n:
    n -= cand_n
    counter += 1
  
print(counter)

Submission status: Runtime Error

Solution code:
a,b=map(int,input().split())
n=b-a
print(n*(n+1)//2-b)

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
from functools import reduce
import copy
import math


sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def solve(inputs):
    n = int(inputs[0])
    LIMIT = 100000
    sixs = [6]
    nines = [9]
    while sixs[-1] <= LIMIT:
        sixs.append(6 * sixs[-1])
    sixs.pop()
    while nines[-1] <= LIMIT:
        nines.append(9 * nines[-1])
    nines.pop()

    choises = [1, *sixs, *nines]
    # [count]
    dp = [0]

    for i in range(1, n+1):
        candidates = []
        for c in choises:
            if i - c >= 0:
                candidates.append(dp[i-c] + 1)
        dp.append(min(candidates))

    return dp[-1]


def string_to_int(string):
    return list(map(int, string.split()))


if __name__ == "__main__":
    ret = solve(inputs(1))
    print(ret)

Submission status: Runtime Error

Solution code:
n=int(input())
S=6
N=9
lst=[]
cnt=0
for i in range(16667):
  S*=6
  N*=9
  lst.append(S)
  lst.append(N)
while n>5:
  for i in len(lst):
    if lst[i]>n:
      n-=lst[i-1]
      cnt+=1
      break
print(cnt+n)