結果

問題 No.1352 Three Coins
ユーザー lam6er
提出日時 2025-04-16 15:38:33
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 456 ms / 2,000 ms
コード長 1,174 bytes
コンパイル時間 271 ms
コンパイル使用メモリ 81,576 KB
実行使用メモリ 260,136 KB
最終ジャッジ日時 2025-04-16 15:43:51
合計ジャッジ時間 3,336 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

def main():
    A, B, C = map(int, input().split())
    
    # Compute GCD of A, B, C
    g = math.gcd(math.gcd(A, B), C)
    if g > 1:
        print("INF")
        return
    
    m = min(A, B, C)
    dp = [True]  # dp[0] is True
    current = 1
    consecutive = 0
    
    while True:
        # Extend dp array if current is out of bounds
        if current >= len(dp):
            needed = current + 1 - len(dp)
            dp.extend([False] * needed)
        
        can_form = False
        # Check each coin
        if current - A >= 0 and dp[current - A]:
            can_form = True
        elif current - B >= 0 and dp[current - B]:
            can_form = True
        elif current - C >= 0 and dp[current - C]:
            can_form = True
        
        if can_form:
            dp[current] = True
            consecutive += 1
            if consecutive == m:
                break
        else:
            consecutive = 0
        
        current += 1
    
    upper = current - m
    count = 0
    for i in range(1, upper + 1):
        if i >= len(dp) or not dp[i]:
            count += 1
    print(count)

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