結果

問題 No.1352 Three Coins
コンテスト
ユーザー lam6er
提出日時 2025-03-20 21:06:29
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,055 bytes
コンパイル時間 193 ms
コンパイル使用メモリ 82,336 KB
実行使用メモリ 71,536 KB
最終ジャッジ日時 2025-03-20 21:06:36
合計ジャッジ時間 3,021 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 32 WA * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

def compute_gcd(a, b, c):
    return math.gcd(a, math.gcd(b, c))

A, B, C = map(int, input().split())

d = compute_gcd(A, B, C)

if d != 1:
    print("INF")
else:
    m = min(A, B, C)
    # Use a maximum size to avoid memory issues. 1e6 is chosen based on problem constraints
    max_n = 10**6
    dp = [False] * (max_n + 1)
    dp[0] = True  # base case: 0 can be formed
    consecutive = 0
    result = 0

    for i in range(1, max_n + 1):
        # Check if current i can be formed by any of the coins
        can_form = False
        if i >= A and dp[i - A]:
            can_form = True
        if not can_form and i >= B and dp[i - B]:
            can_form = True
        if not can_form and i >= C and dp[i - C]:
            can_form = True

        dp[i] = can_form

        if can_form:
            consecutive += 1
            if consecutive >= m:
                break  # All subsequent numbers can be formed
        else:
            consecutive = 0
            result += 1  # Count numbers that cannot be formed

    print(result)
0