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:
# -*- coding: utf-8 -*-

n = int(input())
count_9 = 0
count_6 = 0
count_1 = 0

while n < 6:
    need_9 = int(math.log(n, 9))
    need_6 = int(math.log(n, 6))
    if need_9 > need_6:
        n -= 9^need_9
        count_9 += 1
    else:
        n -= 6^need_6
        count_6 += 1

count_1 = n

print(count_9 + count_6 + count_1)

Submission status: Runtime Error

Solution code:
n = int(input())
list = []

while n > 9**5:
    n = n - 9**5
    list.append(g)

while n > 6**6:
    n = n - 6**6
    list.append(g)


while n > 6**5:
    n = n - 6**5
    list.append(g)


for i in [4,3,2,1]:

    for r in [9,6,]:
        while n > r**i:
            n = n - r**i
            list.append(r**i)



length = len(list) + n
print(length)

Submission status: Runtime Error

Solution code:
n = int(input())
b = [1, 6, 9, 36, 81, 216, 729, 1296, 6561, 7776, 46656, 59049]
bl = 14

res = 1000000
while True:
    tmp = 0
    cu = n
    boole = True
    for i in reversed(range(0, len(b))):
        if cu >= b[i]:
            print(int(cu / b[i]))
            tmp += int(cu / b[i])
            cu = cu % b[i]
            if boole:
                b.pop(i)
    print(tmp)
    res = min(res, tmp)
    if n < b[1]:
        break
        
print(res)

Submission status: Runtime Error

Solution code:
from math import log
from functools import lru_cache

n=int(input())

@lru_cache(maxsize=100000)
def f(n):
    if n<=0: return 1000000
    if n in l:return 1
    return min([f(n-li) for li in l])+1

t=0
while n>20:
    t+=1
    n-=max(6**int(log(n,6)),9**int(log(n,9)))
    
    
a=int(log(n,6))
b=int(log(n,9))
l=list(set([1]+[6**i for i in range(a+1)]+[9**i for i in range(b+1)]))
    
print(t+f(n))

Submission status: Runtime Error

Solution code:
# Q_C
N = int(input())

def count_test(num, a):
    ans = 0
    n = len(a)
    for d in a:
        n = n - 1
        tmp = num // d
        if tmp > 0:
            num = num % d
            ans += tmp
            for i in range(n):
                tmp2 = count_test(num, a[i +1:])
                if tmp2 < ans2:
                    tmp2 = ans2
    ans = ans +  num
    
    if ans > ans2:
        ans = ans2
    return ans

a = []
for i  in range(1, 6):
    a.append(9**i)
    a.append(6**i)

a.append(6**6)

a = sorted(a,reverse=True)

ans = 999999
for i in range(len(a)):
    tmp = count_test(N, a[i:])
    if ans > tmp:
        ans = tmp

print(ans)

Submission status: Runtime Error

Solution code:
# Q_C
N = int(input())

def count_test(num, a):
    ans = 0
    n = len(a)
    for d in a:
        n = n - 1
        tmp = num // d
        if tmp > 0:
            num = num % d
            ans += tmp
            for i in range(n):
                tmp2 = count_test(num, a[i +1:])
                if tmp2 < ans2:
                    tmp2 = ans2
    ans = ans +  num
    
    if ans > ans2:
        ans = ans2
    return ans

a = []
for i  in range(1, 6):
    a.append(9**i)
    a.append(6**i)

a.append(6**6)

a = sorted(a,reverse=True)

ans = 999999
for i in range(len(a)):
    tmp = count_test(N, a[i:])
    print(tmp , '-',  a[i:])
    if ans > tmp:
        ans = tmp

print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
l=[1]
for i in range(1,10):
    a = 6**i
    b = 9**i
    if a <= N:
        l.append(a)
    else :
        break
    if b <= N:
        l.append(b)
    else :
        break
k = 0
while N>=0:
    l = [i for i in l if i <=N]
    N -= max(l)
    k += 1
    print('{} {}'.format(N,k))
print(k)

Submission status: Runtime Error

Solution code:
#! /usr/bin/env python3

import copy

def solve(n, actions, offset):

    res = 0
    val = 100000
    if n == 0 or len(actions) == 0:
        return(offset)
    while (val > n):
        val = actions.pop()
    if val == 1:
        return(n + offset)
    while n >= val * 3:
        res += 1
        n -= val
    tmp = 100000
    i = 0
    while n >= 0:
        tmp = min(tmp, solve(copy.copy(n), copy.copy(actions), copy.copy(i)))
        i += 1
        n -= val
    return(tmp + res + offset)


n = int(input())

res = 0

actions = [1]

for i in range(1, 6 + 1):
    actions.append(6 ** i)
    actions.append(9 ** i)

print(solve(n, actions, 0))

Submission status: Runtime Error

Solution code:
N = int(input())

def count_test(N, a):
    ans = 0
    n = len(a)
    for d in a:
        n = n - 1
        tmp = N // d
        if tmp > 0:
            N = N % d
            ans += tmp
            for i in range(n):
                tmp2 = count_test(N, a[i +1:])
                if tmp2 < ans2:
                    tmp2 = ans2
    ans = ans +  N
    
    if ans > ans2:
        ans = ans2
    return ans

list = []
for i  in range(1, 6):
    list.append(9**i)
    list.append(6**i)

list.append(6**6)

a = sorted(list,reverse=True)

ans = 999999
for i in range(len(a)):
    tmp = count_test(N, a[i:])
    print(tmp , '-',  a[i:])
    if ans > tmp:
        ans = tmp

print(ans)

Submission status: Runtime Error

Solution code:
def count(n, cnt):
    result = [n+cnt]

    i = 1
    while n - 9**i > 0:
        result.append(count(n - 9**i, cnt+int(n/(9**i))))
        i += 1

    i = 1
    while n - 6**i > 0:
        result.append(count(n - 6**i, cnt+int(n/(6**i))))
        i += 1

    return min(result)

N = int(input())
print(count(N, 0))

Submission status: Runtime Error

Solution code:
from math import log
from functools import lru_cache

n=int(input())

a=int(log(n,6))
b=int(log(n,9))
l=list(set([1]+[6**i for i in range(a+1)]+[9**i for i in range(b+1)]))

@lru_cache(maxsize=100000)
def f(n):
    if n<=0: return 1000000
    if n in l:return 1
    return min([f(n-li) for li in l])+1

print(f(n))

Submission status: Runtime Error

Solution code:
def knapsack(V,n):
    if n == -1:
        return V
    if (V,n) in OS_dict.keys():
        return OS_dict[(V,n)]
    elif V < cost[n]:
        r = knapsack(V,n-1)
        OS_dict[(V, n)] = r
        return r
    else:
        r = min(knapsack(V,n-1),knapsack(V-cost[n],n)+value[n]) #完全背包问题只需将第二个选项改为knapsack(V-cost[n],n)+value[n]
        OS_dict[(V,n)] = r
        return r



N = int(input())
now = 9
cost = []
value = []
while now <= N:
    cost.append(now)
    now *= 9
now = 6
while now <= N:
    cost.append(now)
    now *= 6
for x in range(len(cost)):
    value.append(1)
OS_dict = {}
V = N
best = knapsack(V,len(cost)-1)
print(best)

Submission status: Runtime Error

Solution code:
for i in range(1, 6):
    if n > 6:
        while n > a[-i] or n > b[-i]:
            if (n // a[-i] + n % a[-i]) < (n // b[-i] + n % b[-i]):
                if n > a[-i]:
                    n -= a[-i]
                    count += 1
            else:
                if n > b[-i]:
                    n -= b[-i]
                    count += 1
count += n
print(count)

Submission status: Runtime Error

Solution code:
money = []
N=int(input())
n=9
m=6
while n < 100000:
    money.append (n)
    n = n*9

while m < 100000:
    money.append (m)
    m = m*6

money.sort()
money.reverse()

times = 0

for i in money:
    times += int(N/i)
    N -= int(N/i) * i
    if N<36:
        break

possibility = [
for j in range(0,int(N/9)+1):
    M = N-9*j
    possibility.append(j + int(M/6) + M%6)

print (times + min(possibility))

Submission status: Runtime Error

Solution code:
money = int(input())
six = 1
nine = 1
now = 1
kingaku = [1]
while money > now:
    if pow(6,six) < pow(9,nine):
        now = pow(6,six)
        six += 1
    else:
        now = pow(9,nine)
        nine += 1
    kingaku.append(now)
kingaku.pop()
count = 0
def check(money, lis, idx, count):
    m = lis[idx]
    if money < 0:
        return 1000000
    if idx < 0:
        return count
    if idx == 0:
        return count + money
    if money < m:
        return check(money, lis, idx-1, count)
    sho = money // m
    mini = 1000000
    for i in range(sho + 1):
        value = check(money-m*i, lis, idx-1, count+i)
        if value < mini:
            mini = value
    return mini
print(check(money, kingaku, len(kingaku)-1, 0))

Submission status: Runtime Error

Solution code:
import sys
if __name__ == "__main__":
    N = int(input())
    drow_lst = [59049, 46656, 7776, 6561, 1296, 729, 216, 81, 36, 9, 6, 1]
#    drow_lst = [7776, 6561, 1296, 729, 216, 81, 36, 9, 6, 1]
    min = 1000000
    buf_lst = []
    for ele in drow_lst:
        if ele <= N:
            buf_lst.append(ele)
    drow_lst = buf_lst
    for i in range(len(drow_lst)):
        cnt = 0
        buf = N
        buf_drow_lst = drow_lst[i:len(drow_lst)]
        check = []
#        print(buf_drow_lst)
        for ele in buf_drow_lst:
#            print("buf"+str(buf))
#            print("ele"+str(ele))
            if buf % 9 == 0:
                check_buf = cnt + (buf // 9)
                check.append(check_buf)
            if buf % 6 == 0:
                check_buf = cnt + (buf // 6)
                check.append(check_buf)
            if buf >= ele:
                cnt += buf // ele
#                print("cnt"+str(cnt))
                buf = buf % ele
        if min > cnt:
            min = cnt
#        print(check)
        if len(check) > 0 and min > min(check):
            min = min(check)
    print(min)

Submission status: Runtime Error

Solution code:
import numpy as np

N = int(input())

pow6 = [6]
pow9 = [9]

i=0
while pow6[i]*6 < N:
    pow6.append(6*pow6[i])
    i += 1

i=0
while pow9[i]*9 < N:
    pow9.append(9*pow9[i])
    i += 1

ans = 0
while N > 6:

    tmp_6 = [i for i in pow6 if i < N]
    tmp_9 = [i for i in pow9 if i < N]

    if tmp_9[-1] >= tmp_6[-1]:
        N -= tmp_9[-1]
    else:
        N -= tmp_6[-1]
    ans = ans + 1

ans = ans + N
print(ans)

Submission status: Runtime Error

Solution code:
import math
import sys

N = int(sys.stdin.readline())

queue = [(N, 1)]
min_cnt = math.inf

while queue:
    N, cnt = queue.pop()
    if N >= 9:
        v = math.pow(9, math.floor(math.log(N, 9)))
        if N - v >= 6 and cnt < min_cnt:
            queue.append((N - v, cnt + 1))
        elif cnt + (N - v) < min_cnt:
            min_cnt = cnt + int(N - v)
    if N >= 6:
        v = math.pow(6, math.floor(math.log(N, 6)))
        if cnt < min_cnt:
            queue.append((N - v, cnt + 1))
        elif cnt + (N - v) < min_cnt:
            min_cnt = cnt + int(N - v)

if math.isinf(min_cnt):
    print(N)
else:
    print(min_cnt)

Submission status: Runtime Error

Solution code:
import math
import sys

N = int(sys.stdin.readline())

queue = [(N, 1)]
blacklist = set()
min_cnt = math.inf

while queue:
    N, cnt = queue.pop()
    if N >= 9:
        v = math.pow(9, math.floor(math.log(N, 9)))
        if N - v >= 6 and cnt < min_cnt:
            queue.append((N - v, cnt + 1))
        elif cnt + (N - v) < min_cnt:
            min_cnt = cnt + int(N - v)
    if N >= 6:
        v = math.pow(6, math.floor(math.log(N, 6)))
        if cnt < min_cnt:
            queue.append((N - v, cnt + 1))
        elif cnt + (N - v) < min_cnt:
            min_cnt = cnt + int(N - v)

if math.isinf(min_cnt):
    print(N)
else:
    print(min_cnt)

Submission status: Runtime Error

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


def main():
    six = []
    i = 1
    while True:
        n = 6 ** i
        if n > 100000:
            break
        six.append(n)
        i += 1
    nine = []
    i = 1
    while True:
        n = 9 ** i
        if n > 100000:
            break
        nine.append(n)
        i += 1

    N = int(input())

    queue = [[N, 0]]
    ANS = N
    while True:
        n, k = queue.pop(0)
        if ANS < k:
            break
        if n < 0:
            continue
        elif n < 6:
            ANS = min(ANS, k + n)
        elif n < 9:
            ANS = min(ANS, k + 1 + n - 6)
        else:
            while n < nine[-1]:
                nine.pop(-1)
            while n < six[-1]:
                six.pop(-1)
            queue.append([n - nine[-1], k + 1])
            queue.append([n - six[-1], k + 1])
    print(ANS)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

N = int(input())

nine = []
for i in range(1,6):
    nine.append(9**i)

six = []
for i in range(1,7):
    six.append(6**i)


one = nine+six
one.sort()
one.reverse()

ans = []

for i in one:
    if i < N or i == N:
        max_num = int(N/i)
        break
            
for j in range(0,max_num):
    count = 0
    n = N
    check = 0
    for i in one:
        if i < n or i == n:
            if check == 0:
                cnt = int(n/i)-j
                check = 1
            else:
                cnt = int(n/i)
#            print(i," ",cnt)
            n = n - cnt*i
            count = count + cnt
    #        print(n)
    count = count + n
    ans.append(count)

print(min(ans))

Submission status: Runtime Error

Solution code:
import math

n = int(input())

ans = 0

while True:
    a = int(math.log(n,9))
    b = int(math.log(n,6))
    if a == b == 0:
        ans += n
        break
    else:
        if 9 ** a >= 6 ** b:
            n -= 9 ** a
            ans += 1
        else:
            n -= 6 ** b
            ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
from goto import goto, label

kingaku = int(input())

kaisu = 0

while(1):
    label .start

    if kingaku > 9**5:
        kingaku -= 9**5
        kaisu += 1
        goto .start

    if kingaku > 6**6:
        kingaku -= 6**6
        kaisu += 1
        goto .start

    if kingaku > 9**4:
        kingaku -= 9**4
        kaisu += 1
        goto .start

    if kingaku > 6**5:
        kingaku -= 6**5
        kaisu += 1
        goto .start


    if kingaku > 9**3:
        kingaku -= 9**3
        kaisu += 1
        goto .start


    if kingaku > 6**4:
        kingaku -= 6**4
        kaisu += 1
        goto .start


    if kingaku > 9**2:
        kingaku -= 9**2
        kaisu += 1
        goto .start


    if kingaku > 6**3:
        kingaku -= 6**3
        kaisu += 1
        goto .start


    if kingaku > 9**1:
        kingaku -= 9**1
        kaisu += 1
        goto .start


    if kingaku > 6**2:
        kingaku -= 6**2
        kaisu += 1
        goto .start


    if kingaku > 6**1:
        kingaku -= 6**1
        kaisu += 1
        goto .start


    if kingaku > 9**0:
        kingaku -= 9**0
        kaisu += 1
        goto .start

    if kingaku == 1:
        kaisu += 1
        break

print(kaisu)

Submission status: Runtime Error

Solution code:
import math
import sys

N = int(sys.stdin.readline())

min_leaf_cnt = math.inf

class Node:
    def __init__(self, N, cnt, v):
        self.N = N
        self.cnt = cnt
        self.v = v
        self.left = None
        self.right = None
        if self.cnt < min_leaf_cnt:
            self._fill_leaf()

    def _fill_leaf(self):
        if self.N >= 6:
            v = math.pow(6, math.floor(math.log(self.N, 6)))
            self.left = Node(self.N - v, self.cnt + 1, v)
        if self.N >= 9:
            v = math.pow(9, math.floor(math.log(self.N, 9)))
            self.right = Node(self.N - v, self.cnt + 1, v)
        if self.left is None and self.right is None:
            global min_leaf_cnt
            if self.cnt + self.N < min_leaf_cnt:
                min_leaf_cnt = self.cnt + int(self.N)

Node(N, 0, 0)
print(min_leaf_cnt)

Submission status: Runtime Error

Solution code:
import math

money = int(input())

six = [6**i for i in range(1, 8)]
nine = [9**i for i in range(1, 7)]

all = [1] + sorted(six + nine)

dp = [float(math.inf) for i in range(100001)]
dp[0] = 0

for i in range(0, 100001):
    for el in all:
        temp = i + el
        if temp < 100001:
            dp[temp] = min(dp[temp], dp[i] + 1)

print(dp[money])

Submission status: Runtime Error

Solution code:
n = int(raw_input())

ans = 100000

d = []

for a in range(1,7):d.append( 6**a )
for a in range(1,6):d.append( 9**a )
d.append(1)
d.sort()
#print d

dp = [1000000000] * 100000
dp[0] = 0
for x in range(0,n+1):
  for y in d:
    if x-y >= 0:
      dp[x] = min( dp[x-y] + 1, dp[x] )

print dp[n]

Submission status: Runtime Error

Solution code:
n = int(raw_input())

ans = 100000

d = []

for a in range(1,7):d.append( 6**a )
for a in range(1,6):d.append( 9**a )
d.append(1)
d.sort()
print d

dp = [1000000000] * 100000
dp[0] = 0
for x in range(0,n+1):
  for y in d:
    if x-y >= 0:
      dp[x] = min( dp[x-y] + 1, dp[x] )

print dp[n]

Submission status: Runtime Error

Solution code:
N = int(input())

count = 0

numbers = sorted([9**5, 9**4, 9**3, 9**2, 9, 6**6, 6**5, 6**4, 6**3, 6**2, 6], reverse=True)

def search(n):
    for i in numbers:
        if i <= n:
            return i

for i in range(1000):
    N -= search(N)
    count += 1
    if 1 <= N <= 5:
        count += N
        break
    elif N == 0:
        break

print(count)

Submission status: Runtime Error

Solution code:
import java.util.Scanner;

public class Main {
    static int[][] dp;
    static int[] yen = new int[]{6, 36, 216, 36 * 36, 36 * 36 * 6, 216*216, 9, 81, 729, 81 * 81, 81 * 729, 729* 729};

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        dp = new int[yen.length + 1][100001];

        for (int i = 0; i < dp[0].length; i++) {
            dp[0][i] = i;
        }

        for (int i = 0; i < yen.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                if (j - yen[i] >= 0) {
                    dp[i + 1][j] = Math.min(dp[i + 1][j - yen[i]] + 1, dp[i][j]);
                }
                else {
                    dp[i + 1][j] = dp[i][j];
                }
            }
        }
        System.out.println(dp[dp.length - 1][n]);
    }
}

Submission status: Runtime Error

Solution code:
n = int(input())
possible = [1]
i=1
while i <= 100000:
  i = i*6
  possible+=[i]
i=1
while i <= 100000:
  i = i*9
  possible+=[i]
possible.sort(reverse =1)
ans = 1
table = set(possible)
while True:
  if n in table:
    print(ans)
    break
  ans+=1
  nexttable = set()
  for num in table:
    for p in possible:
      if num + p <100000
        nexttable.add(num+p)
  table = table | nexttable

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product

sys.setrecursionlimit(100000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@lru_cache(maxsize=None)
def r(N):
    # print(N)
    if N == 1:
        return 1
    elif N == 0:
        return 0
    a = 1
    b = 6**int(math.floor(math.log(N, 6)))
    c = 9**int(math.floor(math.log(N, 9)))
    if c > 0:
        ac = r(N - c) + 1
    else:
        ac = sys.maxsize
    if b > 0:
        ab = r(N - b) + 1
    else:
        ab = sys.maxsize
    aa = r(N - a) + 1
    return min(aa, ab, ac)


@mt
def slv(N):
    return r(N)


def main():
    N = read_int()
    print(slv(N))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N = int(input())
i = 0
j = 0
a = [1,6,36,216,1296,7776,46656,9,81,729,6561,59049]
b = a.sort(reverse=True)
while N > 0:
  if a[j] > N:
    j += 1
  if a[j] = N:
    N = 0
    i += 1
    print(i)
  if a[j] < N:
    N = N-a[j]
    i += 1

Submission status: Runtime Error

Solution code:
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 87;
int dp[N];
int main()
{
    for (int i = 1; i < N; ++i) {
        dp[i] = dp[i-1];
        for (int k = 1; k <= i; k *= 6)
            dp[i] = min(dp[i],dp[i-k]);
        for (int k = 1; k <= i; k *= 9)
            dp[i] = min(dp[i],dp[i-k]);
        ++dp[i];
    }
    int n;
    cin >> n;
    cout << dp[n] << endl;
}