結果

問題 No.1782 ManyCoins
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:25:02
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,999 bytes
コンパイル時間 202 ms
コンパイル使用メモリ 82,108 KB
実行使用メモリ 77,396 KB
最終ジャッジ日時 2025-03-20 20:26:25
合計ジャッジ時間 5,498 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 10 TLE * 1 -- * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math
from functools import reduce
import heapq
from collections import deque

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def multiple_gcd(lst):
    return reduce(gcd, lst, 0)

def main():
    import sys
    input = sys.stdin.read().split()
    N = int(input[0])
    L = int(input[1])
    W = list(map(int, input[2:2+N]))
    if N == 0:
        print(0)
        return
    # Compute GCD of all coins
    d = multiple_gcd(W)
    # Convert to transformed problem
    L_prime = L // d
    if L_prime == 0:
        print(0)
        return
    W_prime = [w // d for w in W]
    # Check if any coin is 1 in transformed
    if 1 in W_prime:
        print(L_prime)
        return
    # Otherwise, proceed with steps
    w_min = min(W_prime)
    mod = w_min
    # Dijkstra's algorithm to compute min_reach for each remainder
    min_reach = [float('inf')] * mod
    heap = []
    for w in W_prime:
        r = w % mod
        if w < min_reach[r]:
            min_reach[r] = w
            heapq.heappush(heap, (w, r))
    # Process the heap
    while heap:
        s, r = heapq.heappop(heap)
        if s > min_reach[r]:
            continue
        for w in W_prime:
            new_s = s + w
            new_r = new_s % mod
            if new_s < min_reach[new_r]:
                min_reach[new_r] = new_s
                heapq.heappush(heap, (new_s, new_r))
    # Verify all remainders are covered
    for r in range(mod):
        if min_reach[r] == float('inf'):
            print(0)
            return
    # Compute x = max(min_reach[r] - mod for all r)
    x = max([min_reach[r] - mod for r in range(mod)])
    # Determine the answer based on L_prime and x
    if L_prime <= x:
        # BFS to count reachable numbers up to L_prime
        count = 0
        reachable = set()
        queue = deque()
        for w in W_prime:
            if w <= L_prime and w not in reachable:
                reachable.add(w)
                queue.append(w)
        while queue:
            current = queue.popleft()
            count += 1
            for w in W_prime:
                new_val = current + w
                if new_val > L_prime:
                    continue
                if new_val not in reachable:
                    reachable.add(new_val)
                    queue.append(new_val)
        print(count)
    else:
        # BFS to count up to x
        count = 0
        reachable = set()
        queue = deque()
        for w in W_prime:
            if w <= x and w not in reachable:
                reachable.add(w)
                queue.append(w)
        while queue:
            current = queue.popleft()
            count += 1
            for w in W_prime:
                new_val = current + w
                if new_val > x:
                    continue
                if new_val not in reachable:
                    reachable.add(new_val)
                    queue.append(new_val)
        print(count + (L_prime - x))

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