#1062202 (PyPy3) No.1330 Multiply or Divide

• 問題: No.1330 Multiply or Divide
• ユーザー: lam6er
• 提出日時: 2025-03-31 17:57:53
• 言語: PyPy3 (7.3.15)
• 結果: WA
• 実行時間: -
• コード長: 6,313 bytes
• コンパイル時間: 199 ms
• コンパイル使用メモリ: 82,380 KB
• 実行使用メモリ: 130,136 KB
• 最終ジャッジ日時: 2025-03-31 17:58:44
• 合計ジャッジ時間: 5,692 ms
• ジャッジサーバーID （参考情報）: judge5 / judge4

ファイルパターン	結果
other	AC * 39 WA * 7

ソースコード

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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
import sys
from collections import deque
def main():
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    M = int(input[ptr])
    ptr += 1
    P = int(input[ptr])
    ptr += 1
    A = list(map(int, input[ptr:ptr+N]))
    ptr += N
    # Case 1: Check if any Ai is a power of P
    case1_e = []
    other_A = []
    for a in A:
        e = 0
        temp = a
        while temp % P == 0:
            e += 1
            temp = temp // P
        if temp == 1:
            case1_e.append(e)
        else:
            other_A.append(a)
    case1_valid = len(case1_e) > 0
    # Solve case1 using BFS
    case1_min = None
    if case1_valid:
        max_log = 0
        if P == 1:
            pass  # impossible since P is a prime >=2
        else:
            max_e = 0
            current = 1
            count = 0
            while current <= M:
                current *= P
                count += 1
            max_e = count -1 if P !=1 else 0
            unique_e = sorted(list(set(case1_e)))
            visited = dict()
            q = deque()
            visited[0] = 0
            q.append((0, 0))
            min_steps = float('inf')
            while q:
                k, steps = q.popleft()
                if steps >= min_steps:
                    continue
                # Check if current x = P^k is exceeding M (steps must be minimal)
                if pow(P, k) > M:
                    if steps < min_steps:
                        min_steps = steps
                    continue
                # Check if there is a multiplier that can directly exceed M in one step
                if k == 0:
                    for e in unique_e:
                        if P**e > M:
                            if steps +1 < min_steps:
                                min_steps = steps +1
                # Operation 1: divide if possible
                if k > 0:
                    new_k = k -1
                    new_steps = steps +1
                    if new_k not in visited or new_steps < visited.get(new_k, float('inf')):
                        visited[new_k] = new_steps
                        q.append((new_k, new_steps))
                # Operation 2: multiply (k==0)
                if k ==0:
                    for e in unique_e:
                        new_k = e
                        new_x = P**new_k
                        new_steps = steps +1
                        if new_x > M:
                            if new_steps < min_steps:
                                min_steps = new_steps
                        else:
                            if new_k not in visited or new_steps < visited.get(new_k, float('inf')):
                                visited[new_k] = new_steps
                                q.append((new_k, new_steps))
            if min_steps != float('inf'):
                case1_min = min_steps
    # Solve case2: only use other_A (non-power elements)
    # But if case1 is valid, but there are other_A elements, then we can choose either path
    case2_min = None
    # Check if any Ai is non-power of P (other_A is not empty) or case1 is invalid
    case2_possible = len(other_A) > 0 or not case1_valid
    if case2_possible:
        current_x = 1
        steps = 0
        visited = set()
        has_large = False
        candidate = None
        while True:
            if current_x > M:
                candidate = steps
                break
            # Check if any Ai can make current_x * Ai > M
            found = False
            max_ai = 0
            max_ai_val = 0
            for a in A:
                if current_x * a > M:
                    if candidate is None or (steps +1) < candidate:
                        candidate = steps +1
                    found = True
                if a > max_ai_val:
                    max_ai_val = a
                    max_ai = a
            if found:
                # At least one Ai can exceed M in next step
                if candidate is None:
                    candidate = steps +1
                else:
                    candidate = min(candidate, steps +1)
                break
            # If no Ai can exceed M, proceed with the largest Ai
            if max_ai_val == 0:
                candidate = -1
                break
            if max_ai_val ==1:
                # All ai is 1, which can't increase x. So infinite loop
                candidate = -1
                break
            # Check if current_x repeats, leading to a loop
            if current_x in visited:
                candidate = -1
                break
            visited.add(current_x)
            # Check if after adding, it would loop forever
            if current_x > M // max_ai_val:
                # Can't multiply as it would exceed M in next step? Or can I?
                # current_x * max_ai_val <= M ?
                # Not sure
                pass
            current_x *= max_ai_val
            steps +=1
            if current_x > M:
                candidate = steps
                break
            if len(visited) > 40:
                # Consider practical infinite loop
                candidate = -1
                break
        case2_min = candidate
    # Now compare case1_min and case2_min
    min_ans = None
    if case1_valid and case1_min is not None:
        min_ans = case1_min
    if case2_min is not None:
        if case2_min != -1:
            if min_ans is None or case2_min < min_ans:
                min_ans = case2_min
    if case1_min is None and case2_min is None:
        print(-1)
    else:
        candidates = []
        if case1_min is not None:
            candidates.append(case1_min)
        if case2_min is not None and case2_min !=-1:
            candidates.append(case2_min)
        if len(candidates) ==0:
            print(-1)
        else:
            # Also consider if there is a way to combine case1 and case2
            # Like using case1 path and then case2 path
            # But this is complicated, for this problem, the answer is the minimum between case1 and case2, but maybe they can be combined
            # But given time constraints, proceed with the current logic
            final_ans = min(candidates)
            print(final_ans)
    return
if __name__ == "__main__":
    main()
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX