結果

問題 No.2039 Copy and Avoid
ユーザー gew1fw
提出日時 2025-06-12 16:00:54
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,645 bytes
コンパイル時間 196 ms
コンパイル使用メモリ 82,688 KB
実行使用メモリ 78,464 KB
最終ジャッジ日時 2025-06-12 16:01:19
合計ジャッジ時間 5,362 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 5 WA * 7 TLE * 1 -- * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import bisect

def main():
    N, M, A, B = map(int, sys.stdin.readline().split())
    C = list(map(int, sys.stdin.readline().split()))
    C.sort()
    forbidden_set = set(C)
    
    # Find the minimal forbidden number >=2
    F = None
    for c in C:
        if c >= 2:
            F = c
            break
    if F is not None:
        S_max = F - 1
    else:
        S_max = N
    
    # Generate all possible S from 1 to S_max and check if valid
    valid_S = []
    for S in range(1, S_max + 1):
        # Check if any forbidden number is in [2, S]
        # Use binary search on C
        left = bisect.bisect_left(C, 2)
        right = bisect.bisect_right(C, S)
        if left < right:
            # There is a forbidden number in [2, S]
            continue
        valid_S.append(S)
    
    min_total = float('inf')
    
    for S in valid_S:
        if N % S != 0:
            continue
        Q = N // S
        if Q == 1:
            cost = (S - 1) * A
            if cost < min_total:
                min_total = cost
            continue
        
        # BFS to find minimal cost to factorize Q
        from collections import deque
        visited = {}
        queue = deque()
        queue.append((1, 0))
        visited[1] = 0
        found = False
        
        while queue:
            current_product, current_cost = queue.popleft()
            if current_product == Q:
                if current_cost < min_total:
                    min_total = current_cost + (S - 1) * A
                found = True
                break
            remaining = Q // current_product
            if remaining == 1:
                continue
            # Find all divisors of remaining >=2
            # Try all possible factors k from 2 to remaining
            # To find factors, iterate up to sqrt(remaining)
            factors = set()
            for k in range(2, int(remaining**0.5) + 1):
                if remaining % k == 0:
                    factors.add(k)
                    if remaining // k != k:
                        factors.add(remaining // k)
            factors.add(remaining)  # k=remaining
            
            for k in factors:
                next_product = current_product * k
                if next_product > Q:
                    continue
                if Q % next_product != 0:
                    continue
                # Check if this k is valid
                valid = True
                for c in C:
                    if c % S != 0:
                        continue
                    q = c // S
                    if 2 <= q <= k:
                        valid = False
                        break
                if not valid:
                    continue
                new_cost = current_cost + B + (k - 1) * A
                if next_product in visited:
                    if new_cost >= visited[next_product]:
                        continue
                visited[next_product] = new_cost
                queue.append((next_product, new_cost))
        
        # Also check the case where Q is a single factor
        # This is already handled in BFS, but to optimize
        # Check if k=Q is valid
        valid = True
        for c in C:
            if c % S != 0:
                continue
            q = c // S
            if 2 <= q <= Q:
                valid = False
                break
        if valid:
            cost = (S - 1) * A + B + (Q - 1) * A
            if cost < min_total:
                min_total = cost
    
    if min_total == float('inf'):
        print(-1)
    else:
        print(min_total)

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