結果
問題 | No.873 バイナリ、ヤバいなり!w |
ユーザー |
![]() |
提出日時 | 2020-03-19 15:13:20 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 527 ms / 2,000 ms |
コード長 | 1,412 bytes |
コンパイル時間 | 238 ms |
コンパイル使用メモリ | 82,248 KB |
実行使用メモリ | 76,416 KB |
最終ジャッジ日時 | 2024-06-11 14:05:25 |
合計ジャッジ時間 | 6,086 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
#!/usr/bin/ python3.8import sysread = sys.stdin.buffer.readreadline = sys.stdin.buffer.readlinereadlines = sys.stdin.buffer.readlinesN = int(read())dp = [0] * (N + 1)for n in range(1, N + 1):x = nfor i in range(1, N + 1):m = n - i * iif m < 0:breaky = dp[m] + iif x > y:x = ydp[n] = xdef find_next_num_odd(N):for i in range(1, N + 1, 2):m = N - i * iif m < 0:breakif dp[N] == dp[m] + i:return ireturn Nonedef find_next_num_even(N, reverse=True):U = int((N + 1) ** .5)if U & 1:U += 1rng = range(2, U + 1, 2)if reverse:rng = reversed(rng)for i in rng:m = N - i * iif m < 0:continueif dp[N] == dp[m] + i:return inums = []while N:i = find_next_num_odd(N)if not i:breaknums.append(i)N -= i * irev = Truewhile N:i = find_next_num_even(N, rev)rev = not revnums.append(i)N -= i * idef to_word(N, next_ch):q, r = divmod(N, 2)w = '01' if next_ch == 0 else '10'if r == 0:return w * qelse:return w * q + str(next_ch)words = []next_ch = 0for n in nums:words.append(to_word(n, next_ch))if not (n & 1):next_ch ^= 1answer = ''.join(words)print(answer)