結果

問題 No.1330 Multiply or Divide
ユーザー lam6er
提出日時 2025-03-20 20:27:16
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 2,764 bytes
コンパイル時間 232 ms
コンパイル使用メモリ 82,328 KB
実行使用メモリ 624,664 KB
最終ジャッジ日時 2025-03-20 20:28:56
合計ジャッジ時間 4,092 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1 MLE * 1 -- * 44
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq
from collections import defaultdict

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    N = int(data[idx]); idx +=1
    M = int(data[idx]); idx +=1
    P = int(data[idx]); idx +=1
    A = list(map(int, data[idx:idx+N]))
    idx +=N
    
    # Preprocess A into B_i and m_i (A_i = B_i * P^m_i)
    B_list = []
    m_list = []
    for a in A:
        if a == 0:
            m = 0
            B = 0
        else:
            m = 0
            tmp = a
            while tmp % P == 0:
                m +=1
                tmp = tmp // P
            B = tmp
        B_list.append(B)
        m_list.append(m)
    
    heap = []
    visited = defaultdict(lambda: float('inf'))
    
    initial_k = 1
    initial_e = 0
    initial_steps = 0
    heapq.heappush(heap, (initial_steps, initial_k, initial_e))
    visited[(initial_k, initial_e)] = initial_steps
    
    answer = -1
    
    while heap:
        steps, k, e = heapq.heappop(heap)
        
        # Check if current steps is higher than recorded
        if steps > visited[(k, e)]:
            continue
        
        # Check division possibility
        if e > 0:
            # must divide
            new_e = e -1
            new_k = k
            new_x = new_k * (P ** new_e)
            new_steps = steps +1
            
            if new_x > M:
                answer = new_steps
                print(answer)
                return
            else:
                if new_steps < visited[(new_k, new_e)]:
                    visited[(new_k, new_e)] = new_steps
                    heapq.heappush(heap, (new_steps, new_k, new_e))
        else:
            # e == 0: can multiply by any A_i
            for i in range(N):
                B_i = B_list[i]
                m_i = m_list[i]
                
                # Compute new_x after multiplying by B_i and P^m_i
                new_x_multiply = k * B_i * (P ** m_i)
                
                if new_x_multiply > M:
                    current_candidate = steps +1
                    if answer == -1 or current_candidate < answer:
                        answer = current_candidate
                        print(answer)
                        return
                    continue
                else:
                    new_k_after = k * B_i
                    new_steps_after = steps + m_i +1
                    new_e_after = 0
                    
                    if new_steps_after < visited.get((new_k_after, new_e_after), float('inf')):
                        visited[(new_k_after, new_e_after)] = new_steps_after
                        heapq.heappush(heap, (new_steps_after, new_k_after, new_e_after))
    
    print(answer)

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