結果

問題 No.1352 Three Coins
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:28:12
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,594 bytes
コンパイル時間 280 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 68,480 KB
最終ジャッジ日時 2025-03-31 17:29:49
合計ジャッジ時間 2,832 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 30 WA * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import math

def main():
    A, B, C = map(int, sys.stdin.readline().split())

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

    # Compute overall GCD
    overall_gcd = gcd(gcd(A, B), C)
    if overall_gcd != 1:
        print("INF")
        return

    # Check if any pair is coprime
    pairs = [(A, B), (A, C), (B, C)]
    any_coprime = False
    for a, b in pairs:
        if gcd(a, b) == 1:
            any_coprime = True
            break
    if not any_coprime:
        print("INF")
        return

    min_coin = min(A, B, C)
    max_limit = 200000  # Arbitrary large enough limit

    dp = [False] * (max_limit + 1)
    dp[0] = True

    for i in range(1, max_limit + 1):
        if i >= A and dp[i - A]:
            dp[i] = True
        if i >= B and dp[i - B]:
            dp[i] = True
        if i >= C and dp[i - C]:
            dp[i] = True

    # Find the first sequence of min_coin consecutive True
    consecutive = 0
    first_pos = -1
    for i in range(1, max_limit + 1):
        if dp[i]:
            consecutive += 1
            if consecutive == min_coin:
                first_pos = i - min_coin + 1
                break
        else:
            consecutive = 0

    if first_pos == -1:
        # If even after max_limit, no such sequence found (unlikely for problem constraints)
        print("INF")
        return

    # Count all non-formable numbers up to first_pos -1
    count = 0
    for i in range(1, first_pos):
        if not dp[i]:
            count += 1

    print(count)

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