結果

問題 No.2039 Copy and Avoid
ユーザー lam6er
提出日時 2025-04-16 00:19:44
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,341 bytes
コンパイル時間 180 ms
コンパイル使用メモリ 81,640 KB
実行使用メモリ 92,480 KB
最終ジャッジ日時 2025-04-16 00:21:38
合計ジャッジ時間 6,682 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq

def get_divisors(n):
    factors = {}
    temp = n
    i = 2
    while i * i <= temp:
        while temp % i == 0:
            factors[i] = factors.get(i, 0) + 1
            temp //= i
        i += 1
    if temp > 1:
        factors[temp] = 1

    divisors = [1]
    for prime, exp in factors.items():
        current_length = len(divisors)
        prime_power = 1
        for _ in range(exp):
            prime_power *= prime
            for j in range(current_length):
                divisors.append(divisors[j] * prime_power)
    divisors = list(set(divisors))
    divisors.sort()
    return divisors

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx]); idx +=1
    M = int(input[idx]); idx +=1
    A = int(input[idx]); idx +=1
    B = int(input[idx]); idx +=1
    C = list(map(int, input[idx:idx+M]))
    forbidden = set(C)
    
    # Check direct path
    direct_possible = True
    for c in C:
        if 2 <= c <= N-1:
            direct_possible = False
            break
    direct_cost = (N-1)*A if direct_possible else float('inf')
    
    divisors = get_divisors(N)
    cost_dict = {}
    heap = []
    
    if 1 not in forbidden:
        cost_dict[1] = 0
        heapq.heappush(heap, (0, 1))
    
    processed = set()
    while heap:
        current_cost, s = heapq.heappop(heap)
        if s in processed:
            continue
        processed.add(s)
        
        for d in divisors:
            if d % s != 0:
                continue
            t = d // s
            if t < 2:
                continue
            new_s = d
            # Check if s is allowed
            if s in forbidden:
                continue
            # Check intermediate steps
            valid = True
            for q in range(2, t + 1):
                candidate = s * q
                if candidate in forbidden:
                    valid = False
                    break
            if not valid:
                continue
            # Check new_s
            if new_s in forbidden:
                continue
            new_cost = current_cost + (t - 1) * A + B
            if new_s not in cost_dict or new_cost < cost_dict.get(new_s, float('inf')):
                cost_dict[new_s] = new_cost
                heapq.heappush(heap, (new_cost, new_s))
    
    min_cost = direct_cost
    for s in divisors:
        if s not in cost_dict:
            continue
        required = N // s
        if s * required != N:
            continue
        if required < 1:
            continue
        if s in forbidden:
            continue
        if required == 1:
            candidate_cost = cost_dict[s]
            if candidate_cost < min_cost:
                min_cost = candidate_cost
            continue
        # Check if any forbidden number is divisible by s and in [2s, N]
        valid = True
        for c in forbidden:
            if c % s == 0:
                q = c // s
                if 2 <= q <= required:
                    valid = False
                    break
        if valid:
            candidate_cost = cost_dict[s] + (required - 1) * A
            if candidate_cost < min_cost:
                min_cost = candidate_cost
    
    if min_cost == float('inf'):
        print(-1)
    else:
        print(min_cost)

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