提出 #15217464

---

ソースコード 拡げる

import sys
from heapq import heappush, heappop, heappushpop
import itertools

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def main(N):
    def f(x):
        for d in range(2, 6):
            q, r = divmod(x, d)
            if r == 0:
                yield q, f'*{d}'
        for d in range(2, 6):
            for a in range(d):
                yield x * d + a, f'//{d}'

    par = dict()
    q = [-N]  # 作れる数。上位 100 件を持つ。
    maxsize = 100

    for _ in range(1000):
        if max(q) >= -5:
            break
        newq = []
        for x in q:
            x = -x
            for y, string in f(x):
                if y in par:
                    continue
                par[y] = string
                if len(newq) < maxsize:
                    heappush(newq, -y)
                else:
                    heappushpop(newq, -y)
        q = newq
    # 復元する
    x = -max(q)
    expressions = [str(x)]
    while x != N:
        string = par[x]
        expressions.append(string)
        x = eval(str(x) + string)
    expression = ''.join(expressions)
    assert eval(expression) == N, (N, expression)
    return expression.replace('//', '/')

N = int(read())
print(main(N))

提出情報

ジャッジ結果