結果

問題 No.294 SuperFizzBuzz
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:28:37
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 40 ms / 5,000 ms
コード長 2,397 bytes
コンパイル時間 169 ms
コンパイル使用メモリ 82,296 KB
実行使用メモリ 54,052 KB
最終ジャッジ日時 2025-03-20 20:29:40
合計ジャッジ時間 1,440 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().strip()
    N = int(input)
    
    # Initialize DP table for m=0
    dps = [ [1, 0, 0] ]  # dps[0] is for m=0
    prev_dp = dps[0]
    sum_cum = 0
    required_m = None
    required_k = None
    m = 1

    # Find required_m and required_k
    while True:
        current_dp = [0] * 3
        for r_prev in range(3):
            if prev_dp[r_prev] == 0:
                continue
            # Try adding 3
            new_r = (r_prev + 3) % 3
            current_dp[new_r] += prev_dp[r_prev]
            # Try adding 5
            new_r = (r_prev + 5) % 3
            current_dp[new_r] += prev_dp[r_prev]
        
        # Calculate count for current_m (m)
        c_m = current_dp[1]
        new_sum_cum = sum_cum + c_m
        if new_sum_cum >= N:
            required_m = m
            required_k = N - sum_cum
            break
        sum_cum = new_sum_cum
        dps.append(current_dp.copy())
        prev_dp = current_dp
        m += 1

    # Append the current_dp for required_m
    dps.append(current_dp.copy())
    
    # Generate the pattern for required_m and required_k
    pattern = []
    current_mod = 0
    for pos in range(required_m):
        remaining_digits = required_m - pos - 1
        for digit in [3, 5]:
            mod_add = digit % 3
            new_mod = (current_mod + mod_add) % 3
            if remaining_digits == 0:
                # Check if new_mod is 1 to satisfy the total sum mod 3 == 1
                count = 1 if new_mod == 1 else 0
            else:
                needed_mod = (1 - new_mod) % 3
                # Ensure needed_mod is non-negative
                if needed_mod < 0:
                    needed_mod += 3
                # Access dps for remaining_digits
                if remaining_digits >= len(dps):
                    raise ValueError("Insufficient DP entries")
                count = dps[remaining_digits][needed_mod]
            
            if required_k <= count:
                pattern.append(str(digit))
                current_mod = new_mod
                break
            else:
                required_k -= count
        else:
            raise RuntimeError("Unexpected error: no digit could be chosen")
    
    # Append the final '5' to make it a valid SuperFizzBuzz
    result = ''.join(pattern) + '5'
    print(result)

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