結果

問題 No.303 割れません
ユーザー qwewe
提出日時 2025-04-24 12:25:44
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,972 bytes
コンパイル時間 237 ms
コンパイル使用メモリ 82,752 KB
実行使用メモリ 53,788 KB
最終ジャッジ日時 2025-04-24 12:26:32
合計ジャッジ時間 12,405 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other TLE * 1 -- * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**18  # To handle large numbers, but in this problem, we just need to compute the values without modulo.

def main():
    L = int(input().strip())
    if L == 0:
        print("INF\n0")
        return
    
    if L % 2 == 1:
        # For odd L, compute the number of compositions into odd integers
        dp = [0] * (L + 1)
        dp[0] = 1
        for i in range(1, L + 1):
            for j in range(1, i + 1, 2):
                if i - j >= 0:
                    dp[i] += dp[i - j]
        min_cost = L
        patterns = dp[L]
        print(min_cost)
        print(patterns)
    else:
        half = L // 2
        # Compute dp_even and dp_odd
        max_n = L
        dp_even = [0] * (max_n + 1)
        dp_odd = [0] * (max_n + 1)
        dp_even[0] = 1
        dp_odd[0] = 0
        
        for i in range(1, max_n + 1):
            for j in range(1, i + 1, 2):
                if i - j >= 0:
                    dp_even[i] += dp_odd[i - j]
                    dp_odd[i] += dp_even[i - j]
        
        if dp_even[L] == 0:
            print("INF")
            print(0)
            return
        
        if half % 2 == 1:
            # Check if half can be composed of odd numbers
            # Compute dp_odd_half
            dp_odd_half = [0] * (half + 1)
            dp_odd_half[0] = 0
            dp_even_half = [0] * (half + 1)
            dp_even_half[0] = 1
            for i in range(1, half + 1):
                for j in range(1, i + 1, 2):
                    if i - j >= 0:
                        dp_even_half[i] += dp_odd_half[i - j]
                        dp_odd_half[i] += dp_even_half[i - j]
            invalid = dp_odd_half[half] * dp_odd_half[half]
            patterns = dp_even[L] - invalid
        else:
            patterns = dp_even[L]
        
        if patterns <= 0:
            print("INF")
            print(0)
        else:
            print(L)
            print(patterns)
    
if __name__ == "__main__":
    main()
0