結果

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

ソースコード

diff # 

import math

def main():
    import sys
    N = int(sys.stdin.readline())
    if N == 0:
        print("")
        return
    
    INF = float('inf')
    dp = [INF] * (N + 1)
    dp[0] = 0
    prev = [0] * (N + 1)  # To track the previous j used for each i
    
    for i in range(1, N + 1):
        max_j = int(math.sqrt(i))
        for j in range(1, max_j + 1):
            if i - j * j >= 0 and dp[i] > dp[i - j * j] + j:
                dp[i] = dp[i - j * j] + j
                prev[i] = j
    
    # Reconstruct the parts
    current = N
    parts = []
    while current > 0:
        j = prev[current]
        parts.append(j)
        current -= j * j
    
    # Build the binary string
    result = []
    current_char = '0'
    for length in parts:
        segment = []
        for i in range(length):
            if i % 2 == 0:
                segment.append(current_char)
            else:
                segment.append('1' if current_char == '0' else '0')
        result.append(''.join(segment))
        current_char = segment[-1]
    
    print(''.join(result))

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