Submission #8802316

---

Source Code Expand

#!/usr/bin/env python3
import sys
import numpy as np

def solve(N: int):
    #9 ** 5 == 59049 < 10 ** 5
    #6 ** 6 == 46656 < 10 ** 5
    dp = [float("inf")]*(N + 1)
    dp[0] = 0
    pull_list_9 = [9**i for i in range(1, 6)]
    pull_list_6 = [6**i for i in range(1, 7)]
    pull_list = np.array(pull_list_9 + pull_list_6 + [1])
    p_s = sorted(pull_list)
    for i in range(1, N + 1):
        for j in p_s:
            if i - j < 0:
                break
            dp[i] = min(dp[i], dp[i-j] + 1)
    print(dp[-1])

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

if __name__ == '__main__':
    main()

Submission Info

Judge Result