結果

問題 No.2146 2 Pows
コンテスト
ユーザー lam6er
提出日時 2025-03-26 15:50:34
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,803 bytes
コンパイル時間 242 ms
コンパイル使用メモリ 82,540 KB
実行使用メモリ 74,420 KB
最終ジャッジ日時 2025-03-26 15:51:45
合計ジャッジ時間 5,590 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 3 TLE * 1 -- * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    A = int(data[1])
    B = int(data[2])
    C = int(data[3])
    
    m_max = 60  # Sufficiently large to cover possible exponents
    s = [pow(2, m, N) for m in range(m_max)]
    
    INF = float('inf')
    dist = [[INF] * m_max for _ in range(N)]
    heap = []
    
    # Initialize for each possible exponent m
    for m in range(m_max):
        sm = s[m]
        cost = A + B + C * m
        if dist[sm][m] > cost:
            dist[sm][m] = cost
            heapq.heappush(heap, (cost, sm, m))
    
    while heap:
        current_cost, r, m = heapq.heappop(heap)
        if current_cost > dist[r][m]:
            continue
        
        # Transition a: add another element of current exponent m
        new_r = (r + s[m]) % N
        new_cost = current_cost + A
        if new_cost < dist[new_r][m]:
            dist[new_r][m] = new_cost
            heapq.heappush(heap, (new_cost, new_r, m))
        
        # Transition b: add a new exponent m' > m
        for m_prime in range(m + 1, m_max):
            sm_p = s[m_prime]
            new_r_b = (r + sm_p) % N
            added_cost = A + B + C * (m_prime - m)
            new_cost_b = current_cost + added_cost
            if new_cost_b < dist[new_r_b][m_prime]:
                dist[new_r_b][m_prime] = new_cost_b
                heapq.heappush(heap, (new_cost_b, new_r_b, m_prime))
    
    # Compute the minimal cost for each residue
    ans = [INF] * N
    for r in range(N):
        min_val = min(dist[r][m] for m in range(m_max))
        ans[r] = min_val if min_val != INF else -1  # Ensure no -1 as problem guarantees a solution
    
    for k in range(N):
        print(ans[k])

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