Submission #15217464


Source Code Expand

Copy
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))

Submission Info

Submission Time
Task H - 整数をつくろう!
User maspy
Language Python (3.8.2)
Score 141.98
Code Size 1320 Byte
Status AC
Exec Time 479 ms
Memory 86736 KB

Judge Result

Set Name Sample Subtask1 Subtask2 Subtask3
Score / Max Score 0 / 0 5 / 5 10 / 10 126.98 / 85
Status
AC × 3
AC × 8
AC × 13
AC × 10
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
Subtask1 sample_01.txt, sample_02.txt, sample_03.txt, small_01.txt, small_02.txt, small_03.txt, small_04.txt, small_05.txt
Subtask2 sample_01.txt, sample_02.txt, sample_03.txt, small_01.txt, small_02.txt, small_03.txt, small_04.txt, small_05.txt, mid_01.txt, mid_02.txt, mid_03.txt, mid_04.txt, mid_05.txt
Subtask3 score_01.txt, score_02.txt, score_03.txt, score_04.txt, score_05.txt, score_06.txt, score_07.txt, score_08.txt, score_09.txt, score_10.txt
Case Name Status Exec Time Memory
mid_01.txt AC 70 ms 14572 KB
mid_02.txt AC 70 ms 14180 KB
mid_03.txt AC 64 ms 14576 KB
mid_04.txt AC 69 ms 14124 KB
mid_05.txt AC 73 ms 14472 KB
sample_01.txt AC 24 ms 9232 KB
sample_02.txt AC 28 ms 9404 KB
sample_03.txt AC 26 ms 9332 KB
score_01.txt AC 473 ms 86736 KB
score_02.txt AC 463 ms 86156 KB
score_03.txt AC 468 ms 86620 KB
score_04.txt AC 479 ms 86648 KB
score_05.txt AC 445 ms 65056 KB
score_06.txt AC 479 ms 86652 KB
score_07.txt AC 465 ms 86036 KB
score_08.txt AC 466 ms 86236 KB
score_09.txt AC 437 ms 64856 KB
score_10.txt AC 443 ms 65744 KB
small_01.txt AC 35 ms 9680 KB
small_02.txt AC 27 ms 9636 KB
small_03.txt AC 37 ms 9936 KB
small_04.txt AC 29 ms 9652 KB
small_05.txt AC 40 ms 10040 KB