結果

問題 No.1330 Multiply or Divide
コンテスト
ユーザー LyricalMaestro
提出日時 2025-01-20 20:38:08
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,399 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 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 #
raw source code 

## 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()
0