結果

問題 No.1330 Multiply or Divide
ユーザー LyricalMaestro
提出日時 2025-01-20 20:38:08
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,399 bytes
コンパイル時間 1,113 ms
コンパイル使用メモリ 81,920 KB
実行使用メモリ 595,356 KB
最終ジャッジ日時 2025-01-20 20:38:21
合計ジャッジ時間 12,474 ms
ジャッジサーバーID
(参考情報)
judge2 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 44 TLE * 1 MLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

## https://yukicoder.me/problems/no/944
import heapq
def main():
N, M, P = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
p_array = []
for i in range(N):
a = A[i]
p_cnt = 0
while a % P == 0:
a //= P
p_cnt += 1
p_array.append((a, p_cnt))
p_set = {}
for a, p_cnt in p_array:
if a not in p_set:
p_set[a] = float("inf")
p_set[a] = min(p_set[a], p_cnt)
p_array = [(a, p_cnt) for a, p_cnt in p_set.items()]
queue = []
seen = {1:0}
fix = {}
heapq.heappush(queue, (0, 1))
answer = float("inf")
while len(queue) > 0:
cost, a = heapq.heappop(queue)
if a in fix:
continue
fix[a] = cost
if a * A[0] > M:
answer = min(answer, cost + 1)
break
for x, p_cnt in p_array:
new_x = a * x
if new_x > M:
continue
if new_x in fix:
continue
new_cost = cost + p_cnt + 1
if new_x not in seen or seen[new_x] > new_cost:
seen[new_x] = new_cost
heapq.heappush(queue, (new_cost, new_x))
if answer == float("inf"):
print(-1)
else:
print(answer)
if __name__ == "__main__":
main()
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0