結果
問題 |
No.2039 Copy and Avoid
|
ユーザー |
![]() |
提出日時 | 2025-06-12 15:58:53 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,193 bytes |
コンパイル時間 | 165 ms |
コンパイル使用メモリ | 82,508 KB |
実行使用メモリ | 93,548 KB |
最終ジャッジ日時 | 2025-06-12 15:59:02 |
合計ジャッジ時間 | 6,629 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | TLE * 1 -- * 30 |
ソースコード
def factorize(n): factors = {} i = 2 while i * i <= n: while n % i == 0: factors[i] = factors.get(i, 0) + 1 n = n // i i += 1 if n > 1: factors[n] = 1 return factors def get_divisors(factors): divisors = [1] for p in factors: exponents = [p**e for e in range(1, factors[p] + 1)] new_divisors = [] for d in divisors: for e in exponents: new_divisors.append(d * e) divisors += new_divisors divisors = list(set(divisors)) divisors.sort() return divisors def main(): import sys from collections import defaultdict import heapq N, M, A, B = map(int, sys.stdin.readline().split()) C = list(map(int, sys.stdin.readline().split())) forbidden = set(C) if 1 in forbidden or N in forbidden: print(-1) return factors = factorize(N) divisors = get_divisors(factors) D = divisors adj = defaultdict(list) for d in D: if d == N: continue for m in D: if m > d and m % d == 0: f = m // d if f < 2: continue valid = True for c in forbidden: if c % d == 0: q = c // d if 1 <= q <= f: valid = False break if valid: cost = (f - 1) * A if m != N: cost += B adj[d].append((m, cost)) INF = float('inf') dist = {d: INF for d in D} dist[1] = 0 heap = [] heapq.heappush(heap, (0, 1)) visited = set() while heap: current_dist, u = heapq.heappop(heap) if u in visited: continue if u == N: print(current_dist) return visited.add(u) for v, cost in adj[u]: if dist[v] > current_dist + cost: dist[v] = current_dist + cost heapq.heappush(heap, (dist[v], v)) print(-1) if __name__ == "__main__": main()