Submission #15218616


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, d
        for d in range(2, 6):
            for a in range(d):
                yield x * d + a, -d

    par = dict()
    maxsize = 550
    q = [N]  # 作れる数。
    q1 = [N]  # まだ足し算やっていい状態。
    low = N

    for step in range(1000):
        if q[0] <= 5:
            break

        newq = []

        low -= 5
        for k in range(low, low + 5):
            if k in par:
                continue
            par[k] = 0
            newq.append(k)

        for x in q:
            for y, string in f(x):
                if y in par:
                    continue
                par[y] = string
                newq.append(y)
        newq.sort()
        q = newq[:maxsize]

    # 復元する
    x = q[0]
    expressions = [str(x)]
    while x != N:
        d = par[x]
        if d > 0:
            expressions.append(f'*{d}')
            x *= d
        elif d < 0:
            d = -d
            expressions.append(f'/{d}')
            x //= d
        else:
            #  あとは足し算
            q, r = divmod(N - x, 5)
            expressions += ['+5'] * q
            if r:
                expressions.append(f'+{r}')
            x = N
    expression = ''.join(expressions)
    return expression

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

Submission Info

Submission Time
Task H - 整数をつくろう!
User maspy
Language Python (3.8.2)
Score 144.19
Code Size 1659 Byte
Status AC
Exec Time 1866 ms
Memory 237424 KB

Judge Result

Set Name Sample Subtask1 Subtask2 Subtask3
Score / Max Score 0 / 0 5 / 5 10 / 10 129.19 / 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 163 ms 20556 KB
mid_02.txt AC 174 ms 21104 KB
mid_03.txt AC 184 ms 21108 KB
mid_04.txt AC 169 ms 20620 KB
mid_05.txt AC 175 ms 21284 KB
sample_01.txt AC 23 ms 9148 KB
sample_02.txt AC 23 ms 9344 KB
sample_03.txt AC 20 ms 9048 KB
score_01.txt AC 1866 ms 237424 KB
score_02.txt AC 1845 ms 235780 KB
score_03.txt AC 1837 ms 235868 KB
score_04.txt AC 1858 ms 236248 KB
score_05.txt AC 1819 ms 235428 KB
score_06.txt AC 1848 ms 236512 KB
score_07.txt AC 1817 ms 234996 KB
score_08.txt AC 1835 ms 236444 KB
score_09.txt AC 1773 ms 233576 KB
score_10.txt AC 1865 ms 234824 KB
small_01.txt AC 44 ms 10108 KB
small_02.txt AC 47 ms 9936 KB
small_03.txt AC 44 ms 10344 KB
small_04.txt AC 42 ms 10448 KB
small_05.txt AC 49 ms 11232 KB