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):
def solve():
    n = int(input())
    dp = [0 for _ in range(n+1)] 

    for i in range(1, n+1):
        options = find_options(i)
        selected = min(map(lambda x: [x, dp[i - x]], options), key=lambda x: x[1])
        print(selected)
        dp[i] = dp[i-selected[0]] + 1

    print(dp[n])

def find_options(n):
    sixs = find_sixs(n)
    nines = find_nines(n)
    options = [1]
    options.extend(sixs)
    options.extend(nines)
    return options


def find_sixs(n):
    sixs = 1
    powers = [] 
    count = 0
    while n > sixs:
        count += 1
        sixs *= 6
        powers.append(sixs)
    
    if len(powers) == 0:
        return powers
    else:
        powers.pop()
    return powers

def find_nines(n):
    nines = 1
    powers = [] 
    count = 0
    while n > nines:
        count += 1
        nines *= 9
        powers.append(nines)
    
    if len(powers) == 0:
        return powers
    else:
        powers.pop()
    return powers

if __name__ == "__main__":
    solve()

def solve():
    n = int(input())
    dp = [0 for _ in range(n+1)] 
    print(find_options(91414))

    for i in range(1, n+1):
        options = find_options(i)
        selected = min(map(lambda x: [x, dp[i - x]], options), key=lambda x: x[1])
        dp[i] = selected[1] + 1

    print(dp[n])

def find_options(n):
    sixs = find_sixs(n)
    nines = find_nines(n)
    options = [1]
    options.extend(sixs)
    options.extend(nines)
    return options


def find_sixs(n):
    sixs = 1
    powers = [] 
    count = 0
    while n > sixs:
        count += 1
        sixs *= 6
        powers.append(sixs)
    
    if len(powers) == 0:
        return powers
    else:
        powers.pop()
    return powers

def find_nines(n):
    nines = 1
    powers = [] 
    count = 0
    while n > nines:
        count += 1
        nines *= 9
        powers.append(nines)
    
    if len(powers) == 0:
        return powers
    else:
        powers.pop()
    return powers

if __name__ == "__main__":
    solve()

def solve():
    n = int(input())
    dp = [0 for _ in range(n+1)] 

    for i in range(1, n+1):
        options = find_options(i)
        selected = min(map(lambda x: [x, dp[i - x]], options), key=lambda x: x[1])
        dp[i] = selected[1] + 1

    print(dp[n])

def find_options(n):
    sixs = find_sixs(n)
    nines = find_nines(n)
    options = [1]
    options.extend(sixs)
    options.extend(nines)
    return options


def find_sixs(n):
    sixs = 1
    powers = [] 
    count = 0
    while n > sixs:
        count += 1
        sixs *= 6
        powers.append(sixs)
    
    if sixs == n:
        return powers
    else:
        powers.pop()
    return powers

def find_nines(n):
    nines = 1
    powers = [] 
    count = 0
    while n > nines:
        count += 1
        nines *= 9
        powers.append(nines)
    
    if nines == n:
        return powers
    else:
        powers.pop()
    return powers

if __name__ == "__main__":
    solve()

Verdicts: Wrong Answer

Wrong Answer

Accepted