結果
問題 | No.1330 Multiply or Divide |
ユーザー |
![]() |
提出日時 | 2021-01-10 00:53:30 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 127 ms / 2,000 ms |
コード長 | 632 bytes |
コンパイル時間 | 193 ms |
コンパイル使用メモリ | 82,160 KB |
実行使用メモリ | 116,352 KB |
最終ジャッジ日時 | 2024-11-19 00:32:19 |
合計ジャッジ時間 | 5,616 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 46 |
ソースコード
from collections import dequeINF = 10 ** 20N, M, P, *A = map(int, open(0).read().split())def f(x):c = 0while x % P == 0:c += 1x //= Preturn (x, c)max_A = max(A)if max_A > M:print(1)exit()b = {}for m, c in map(f, A):b.setdefault(c, 0)b[c] = max(b[c], m)t = 1for k in sorted(b):if b[k] <= t:del b[k]else:t = b[k]cs = sorted(b)if len(cs) == 0:print(-1)exit()q = deque([(0, 1)])while q:c, x = q.popleft()if x * max_A > M:print(c + 1)breakfor k in cs:q.append((c + 1 + k, x * b[k]))