結果

問題 No.1330 Multiply or Divide
ユーザー gew1fw
提出日時 2025-06-12 13:16:08
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,537 bytes
コンパイル時間 416 ms
コンパイル使用メモリ 82,188 KB
実行使用メモリ 722,440 KB
最終ジャッジ日時 2025-06-12 13:18:36
合計ジャッジ時間 4,280 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 1 MLE * 1 -- * 44
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    N, M, P = map(int, sys.stdin.readline().split())
    A = list(map(int, sys.stdin.readline().split()))
    
    # Preprocess each A_i to get a_i and B_i
    a_list = []
    B_list = []
    for a in A:
        ai = 0
        tmp = a
        while tmp % P == 0:
            ai += 1
            tmp = tmp // P
        Bi = tmp
        a_list.append(ai)
        B_list.append(Bi)
    
    # Check if any A_i has B_i == 1 and a_i == 0
    for i in range(N):
        if B_list[i] == 1 and a_list[i] == 0:
            print(-1)
            return
    
    # BFS setup
    visited = {}
    queue = deque()
    initial_B = 1
    visited[initial_B] = 0
    queue.append((initial_B, 0))
    min_answer = float('inf')
    
    while queue:
        B, steps = queue.popleft()
        
        all_exceed = True
        for i in range(N):
            Bi = B_list[i]
            ai = a_list[i]
            new_B = B * Bi
            x_new = new_B * (P ** ai)
            if x_new <= M:
                all_exceed = False
                new_steps = steps + ai + 1
                if new_B not in visited or new_steps < visited.get(new_B, float('inf')):
                    visited[new_B] = new_steps
                    queue.append((new_B, new_steps))
        
        if all_exceed:
            if steps + 1 < min_answer:
                min_answer = steps + 1
    
    if min_answer != float('inf'):
        print(min_answer)
    else:
        print(-1)

if __name__ == "__main__":
    main()
0