#1055599 (PyPy3) No.1330 Multiply or Divide

• 問題: 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

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
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()
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX