結果

問題 No.2099 [Cherry Alpha B] Time Machine
コンテスト
ユーザー lam6er
提出日時 2025-04-16 00:01:24
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,906 bytes
コンパイル時間 205 ms
コンパイル使用メモリ 81,968 KB
実行使用メモリ 74,616 KB
最終ジャッジ日時 2025-04-16 00:03:30
合計ジャッジ時間 5,405 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 30 WA * 42
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

def extended_gcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = extended_gcd(b % a, a)
        return (g, x - (b // a) * y, y)

def mod_inverse(a, m):
    g, x, y = extended_gcd(a, m)
    if g != 1:
        return None  # no inverse exists
    else:
        return x % m

def compute_min_cost(T, X, A, Y, B):
    min_cost = float('inf')
    
    # Cost using only waiting steps if T is positive
    if T > 0:
        min_cost = min(min_cost, T)
    
    # Compute m0 and cost_m0
    if T > 0:
        m0 = T // A
        cost_m0 = T + (X - A) * m0
        min_cost = min(min_cost, cost_m0)
    else:
        m0 = 0
        cost_m0 = float('inf')
    
    # Consider m in the range [m0, m0 + B] for T > 0
    if T > 0:
        upper = m0 + B
        for m in range(m0, min(m0 + B + 1, m0 + 2 * 10**6)):
            numerator = A * m - T
            if numerator <= 0:
                n = 0
                k = T - (A * m - B * n)
                if k < 0:
                    continue
                cost = X * m + Y * n + k
                min_cost = min(min_cost, cost)
            else:
                q = (numerator + B - 1) // B  # ceil division
                n = q
                k = T - (A * m - B * n)
                if k < 0:
                    continue
                cost = X * m + Y * n + k
                min_cost = min(min_cost, cost)
    
    # Solve for congruence-based m_candidate
    if T > 0:
        d = math.gcd(A, B)
        if T % d != 0:
            pass
        else:
            A_prime = A // d
            B_prime = B // d
            T_prime = T // d
            inv = mod_inverse(A_prime, B_prime)
            if inv is not None:
                m_min = (T_prime * inv) % B_prime
                k = (m0 + 1 - m_min + B_prime - 1) // B_prime
                m_candidate = m_min + k * B_prime
                for delta in [-1, 0, 1]:
                    m = m_candidate + delta
                    if m < m0 + 1:
                        continue
                    numerator = A * m - T
                    if numerator < 0:
                        n = 0
                        k_val = T - (A * m - B * n)
                        if k_val < 0:
                            continue
                        cost = X * m + Y * n + k_val
                        min_cost = min(min_cost, cost)
                    else:
                        q = (numerator + B - 1) // B
                        n = q
                        k_val = T - (A * m - B * n)
                        if k_val < 0:
                            continue
                        cost = X * m + Y * n + k_val
                        min_cost = min(min_cost, cost)
    
    return min_cost

# Read input
T = int(input())
X, A = map(int, input().split())
Y, B = map(int, input().split())

# Compute and print the result
print(compute_min_cost(T, X, A, Y, B))
0