Contest Duration: - (local time) (120 minutes)

Submission #15217590

Source Code Expand

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

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()
q = [-N]  # 作れる数。
maxsize = 500

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:
d = par[x]
if d > 0:
expressions.append(f'*{d}')
x *= d
else:
d = -d
expressions.append(f'/{d}')
x //= d
expression = ''.join(expressions)
return expression

print(main(N))```

#### Submission Info

Submission Time 2020-07-13 14:08:00+0900 H - 整数をつくろう！ maspy Python (3.8.2) 143.59 1313 Byte AC 1913 ms 234736 KB

#### Judge Result

Score / Max Score 0 / 0 5 / 5 10 / 10 128.59 / 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 175 ms 20772 KB
mid_02.txt AC 183 ms 20884 KB
mid_03.txt AC 188 ms 20620 KB
mid_04.txt AC 174 ms 20580 KB
mid_05.txt AC 197 ms 21088 KB
sample_01.txt AC 25 ms 9112 KB
sample_02.txt AC 25 ms 9392 KB
sample_03.txt AC 24 ms 9184 KB
score_01.txt AC 1913 ms 234736 KB
score_02.txt AC 1863 ms 232504 KB
score_03.txt AC 1881 ms 233396 KB
score_04.txt AC 1897 ms 234476 KB
score_05.txt AC 1844 ms 231756 KB
score_06.txt AC 1877 ms 233060 KB
score_07.txt AC 1874 ms 232044 KB
score_08.txt AC 1875 ms 233372 KB
score_09.txt AC 1823 ms 230036 KB
score_10.txt AC 1911 ms 232968 KB
small_01.txt AC 47 ms 11668 KB
small_02.txt AC 45 ms 10196 KB
small_03.txt AC 55 ms 11652 KB
small_04.txt AC 48 ms 10400 KB
small_05.txt AC 56 ms 11548 KB