結果

問題 No.1330 Multiply or Divide
コンテスト
ユーザー lam6er
提出日時 2025-04-15 22:59:26
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,471 bytes
コンパイル時間 416 ms
コンパイル使用メモリ 82,232 KB
実行使用メモリ 699,900 KB
最終ジャッジ日時 2025-04-15 23:01:09
合計ジャッジ時間 4,358 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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()))
    
    # Precompute a_i and b_i for each A_i
    a_list = []
    b_list = []
    for ai in A:
        a = 0
        temp = ai
        while temp % P == 0:
            a += 1
            temp = temp // P
        a_list.append(a)
        b_list.append(temp)
    
    # Precompute v_max and pow_p
    v_max = 0
    current_p = 1
    pow_p = [1]  # pow_p[0] = 1
    while True:
        next_p = current_p * P
        if next_p > M:
            break
        current_p = next_p
        v_max += 1
        pow_p.append(current_p)
    # Now, pow_p[v] = P^v for v up to v_max
    
    # BFS setup
    visited = {}
    queue = deque()
    initial_k = 1
    visited[initial_k] = 0
    queue.append((initial_k, 0))
    
    while queue:
        k, steps = queue.popleft()
        # Check if current steps in visited is the minimal
        if visited.get(k, float('inf')) < steps:
            continue
        # Process each A_i
        for i in range(N):
            a_i = a_list[i]
            b_i = b_list[i]
            new_k = k * b_i
            new_v = a_i
            # Check if this multiplication would exceed M
            if new_v > v_max:
                print(steps + 1)
                return
            else:
                if new_v >= len(pow_p):
                    pow_new_v = P ** new_v
                else:
                    pow_new_v = pow_p[new_v]
                # Check if new_k exceeds M / pow_new_v
                if pow_new_v > M:
                    print(steps + 1)
                    return
                max_k = M // pow_new_v
                if new_k > max_k:
                    print(steps + 1)
                    return
                # Check exact value to avoid division errors
                if pow_new_v * new_k > M:
                    print(steps + 1)
                    return
            # Now, collapse new_v to 0 and add steps
            new_steps = steps + 1 + new_v
            new_k_collapsed = new_k
            if new_k_collapsed in visited:
                if new_steps >= visited[new_k_collapsed]:
                    continue
            # Update visited and queue
            visited[new_k_collapsed] = new_steps
            queue.append((new_k_collapsed, new_steps))
    
    # If no solution found
    print(-1)

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