結果

問題 No.1330 Multiply or Divide
ユーザー lam6er
提出日時 2025-04-16 16:01:43
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 4,327 bytes
コンパイル時間 254 ms
コンパイル使用メモリ 81,800 KB
実行使用メモリ 148,172 KB
最終ジャッジ日時 2025-04-16 16:06:40
合計ジャッジ時間 7,488 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 38 WA * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import math
from collections import defaultdict

def main():
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx]); idx +=1
    M = int(input[idx]); idx +=1
    P = int(input[idx]); idx +=1
    A = list(map(int, input[idx:idx+N]))
    
    # Preprocess A into a_i and B_i
    a_list = []
    B_list = []
    maxB = 0
    has_B_gt1 = False
    for a in A:
        x = a
        ai = 0
        while x % P == 0:
            ai +=1
            x = x // P
        Bi = x
        a_list.append(ai)
        B_list.append(Bi)
        if Bi > maxB:
            maxB = Bi
        if Bi > 1:
            has_B_gt1 = True
    
    # Handle the case where all B_i are 1
    if not has_B_gt1:
        # Check if there exists a k where P^k > M, and steps to reach k
        # But in this case, steps_to_reach_k would require multiply and divide steps
        # but Q remains 1, leading to possible loops
        # So if there's a way to reach k where P^k > M, then steps is steps_to_reach_k
        # Else, -1
        steps_to_k = defaultdict(lambda: float('inf'))
        steps_to_k[0] = 0  # initial state
        for i in range(N):
            ai = a_list[i]
            Bi = B_list[i]
            # Compute max d
            max_d = 0
            current_max_d = -1
            for d in range(ai+1):
                valid = True
                for d_prime in range(d+1):
                    k_prime = ai - d_prime
                    x_val = (P ** k_prime) * Bi
                    if x_val > M:
                        valid = False
                        break
                if valid:
                    current_max_d = d
                else:
                    break
            if current_max_d == -1:
                continue
            max_d = current_max_d
            for d in range(max_d +1):
                k_candidate = ai - d
                steps_candidate = 1 + d
                if steps_candidate < steps_to_k[k_candidate]:
                    steps_to_k[k_candidate] = steps_candidate
        
        min_steps = float('inf')
        for k in steps_to_k:
            if steps_to_k[k] == float('inf'):
                continue
            pk = P ** k
            if pk > M:
                if steps_to_k[k] < min_steps:
                    min_steps = steps_to_k[k]
        if min_steps != float('inf'):
            print(min_steps)
        else:
            print(-1)
        return
    
    # Compute steps_to_reach_k
    steps_to_k = defaultdict(lambda: float('inf'))
    steps_to_k[0] = 0  # initial state
    for i in range(N):
        ai = a_list[i]
        Bi = B_list[i]
        # Compute max d that can be performed after multiplying this A_i
        max_d = 0
        current_max_d = -1
        for d in range(ai +1):
            valid = True
            for d_prime in range(d +1):
                k_prime = ai - d_prime
                x_val = (P ** k_prime) * Bi
                if x_val > M:
                    valid = False
                    break
            if valid:
                current_max_d = d
            else:
                break
        if current_max_d == -1:
            continue
        max_d = current_max_d
        for d in range(max_d +1):
            k_candidate = ai - d
            steps_candidate = 1 + d
            if steps_candidate < steps_to_k[k_candidate]:
                steps_to_k[k_candidate] = steps_candidate
    
    min_total = float('inf')
    # Iterate over all possible k in steps_to_k
    for k in steps_to_k:
        steps_k = steps_to_k[k]
        if steps_k == float('inf'):
            continue
        pk = P ** k
        if pk ==0:
            continue
        Q_min = (M // pk) +1
        if Q_min <=1:
            if pk > M:
                # x = pk *1 > M
                if steps_k < min_total:
                    min_total = steps_k
            continue
        # Compute steps_needed to reach Q >= Q_min
        if maxB ==1:
            continue
        steps_needed = 0
        product =1
        while product < Q_min:
            product *= maxB
            steps_needed +=1
        total = steps_k + steps_needed
        if total < min_total:
            min_total = total
    
    if min_total != float('inf'):
        print(min_total)
    else:
        print(-1)

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