結果

問題 No.1330 Multiply or Divide
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 13:18:43
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,338 bytes
コンパイル時間 574 ms
コンパイル使用メモリ 82,228 KB
実行使用メモリ 143,152 KB
最終ジャッジ日時 2025-06-12 13:20:50
合計ジャッジ時間 6,403 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 44 WA * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    M = int(data[1])
    P = int(data[2])
    A = list(map(int, data[3:3+N]))
    
    k_list = []
    B_list = []
    for a in A:
        k = 0
        temp = a
        while temp % P == 0:
            k += 1
            temp = temp // P
        k_list.append(k)
        B_list.append(temp)
    
    x = 1
    steps = 0
    
    while x <= M:
        # Check if any A_i can directly exceed M
        found = False
        for a in A:
            if x * a > M:
                print(steps + 1)
                return
        
        best_steps = float('inf')
        best_new_x = -1
        
        for i in range(N):
            a = A[i]
            k = k_list[i]
            x_new = x * a
            
            if x_new > M:
                steps_i = 1
                new_x_i = x_new
            else:
                val = (x_new - 1) // M
                if val == 0:
                    j_max = -1
                else:
                    current = 1
                    j = 0
                    while current * P <= val:
                        current *= P
                        j += 1
                    j_max = j
                    j_max = min(j_max, k)
                
                if j_max >= 0:
                    steps_i = 1 + j_max
                    p_j = 1
                    for _ in range(j_max):
                        p_j *= P
                    new_x_i = x_new // p_j
                else:
                    steps_i = 1 + k
                    p_k = 1
                    for _ in range(k):
                        p_k *= P
                    new_x_i = x_new // p_k
            
            if new_x_i > M:
                if steps_i < best_steps:
                    best_steps = steps_i
                    best_new_x = new_x_i
            else:
                if new_x_i > x and steps_i < best_steps:
                    best_steps = steps_i
                    best_new_x = new_x_i
        
        if best_steps == float('inf'):
            print(-1)
            return
        
        if best_new_x <= x:
            print(-1)
            return
        
        steps += best_steps
        x = best_new_x
    
    print(steps)

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