結果

問題 No.873 バイナリ、ヤバいなり！ｗ
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 17:08:17
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,337 bytes
コンパイル時間 249 ms
コンパイル使用メモリ 82,228 KB
実行使用メモリ 83,316 KB
最終ジャッジ日時 2025-06-12 17:08:28
合計ジャッジ時間 6,744 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 16 WA * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import math

def main():
    N = int(sys.stdin.readline().strip())
    
    # Initialize DP array
    max_n = N
    dp = [float('inf')] * (max_n + 1)
    dp[0] = 0
    prev = [0] * (max_n + 1)
    
    for i in range(1, max_n + 1):
        max_j = int(math.isqrt(i))
        for j in range(1, max_j + 1):
            j_sq = j * j
            if i >= j_sq and dp[i - j_sq] + j < dp[i]:
                dp[i] = dp[i - j_sq] + j
                prev[i] = j
    
    # Collect the ai's
    ai_list = []
    current = N
    while current > 0:
        j = prev[current]
        ai_list.append(j)
        current -= j * j
    
    # Sort the ai's in non-decreasing order
    ai_list.sort()
    
    # Construct the binary string
    s = []
    start_char = '0'
    for ai in ai_list:
        # Generate the 01 sequence
        seq = []
        current_char = start_char
        for _ in range(ai):
            seq.append(current_char)
            current_char = '1' if current_char == '0' else '0'
        s.append(''.join(seq))
        
        # Determine the next start_char
        if ai % 2 == 1:
            last_char = start_char
        else:
            last_char = '1' if start_char == '0' else '0'
        start_char = last_char
    
    binary_str = ''.join(s)
    print(binary_str)

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