結果
| 問題 |
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 |
ソースコード
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()