Problem: 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.

Submission attempts (in order):
# -*- coding: utf-8 -*-

import os
import sys

def main():
    n = int(input())
    l1 = lis(n, 9)
    l2 = lis(n, 6)
    print(l1)
    print(l2)
    l1.extend(l2)
    l1 = list(set(l1))
    l1.sort(key=int, reverse=True)
    print(minus(n, l1))

def lis(n, i):
    count = 0
    res = []
    oi = i
    while i < n:
        res.append(i)
        i = i * oi
        count = count + 1
    return res

def minus(n, l):
    minus_count = 0
    for i in l:
        while n > i:
            if n - i > 0:
                n = n - i
                minus_count = minus_count + 1
            else:
                break
        print(i, n)
    return minus_count, n

if __name__ == '__main__':
    main()

# -*- coding: utf-8 -*-

import os
import sys

def main():
    n = int(input())
    l1 = lis(n, 9)
    l2 = lis(n, 6)
    l1.extend(l2)
    l1 = list(set(l1))
    l1.sort(key=int, reverse=True)
    print(minus(n, l1))

def lis(n, i):
    count = 0
    res = []
    oi = i
    while i < n:
        res.append(i)
        i = i * oi
        count = count + 1
    return res

def minus(n, l):
    minus_count = 0
    for i in l:
        while n > i:
            if n - i > 0:
                n = n - i
                minus_count = minus_count + 1
            else:
                break
    return minus_count, n

if __name__ == '__main__':
    main()

# -*- coding: utf-8 -*-

def main():
    n = int(input())
    li = dp(n)
    print(li)
    print(li[n])

def dp(n):
    inf=float('inf')
    dp = [inf for i in range(n+1)]
    dp[0] = 0
    money_list = get_money_list()
    for i in range(1, n + 1):
        for pay in money_list:
            if pay > i:
                continue
            else:
                dp[i] = min(dp[i - pay] + 1, dp[i])
    return dp

def create_list(n):
    i = 1
    money_list = []
    while i < 100000:
        money_list.append(i)
        i = i * n
    return money_list

def get_money_list():
    li = create_list(9)
    li.extend(create_list(6))
    li = list(set(li))
    li.sort(key=int, reverse=True)
    return li

if __name__ == '__main__':
    main()

# -*- coding: utf-8 -*-

def main():
    n = int(input())
    li = dp(n)
    print(li[n])

def dp(n):
    inf=float('inf')
    dp = [inf for i in range(n+1)]
    dp[0] = 0
    money_list = get_money_list()
    for i in range(1, n + 1):
        for pay in money_list:
            if pay > i:
                continue
            else:
                dp[i] = min(dp[i - pay] + 1, dp[i])
    return dp

def create_list(n):
    i = 1
    money_list = []
    while i < 100000:
        money_list.append(i)
        i = i * n
    return money_list

def get_money_list():
    li = create_list(9)
    li.extend(create_list(6))
    li = list(set(li))
    li.sort(key=int, reverse=True)
    return li

if __name__ == '__main__':
    main()

Verdicts: Wrong Answer

Wrong Answer

Wrong Answer

Accepted