結果
問題 | No.262 面白くないビットすごろく |
ユーザー |
![]() |
提出日時 | 2020-04-08 20:45:54 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 37 ms / 2,000 ms |
コード長 | 1,107 bytes |
コンパイル時間 | 203 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 11,776 KB |
最終ジャッジ日時 | 2024-07-19 05:43:11 |
合計ジャッジ時間 | 922 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 4 |
ソースコード
#!/usr/bin/ python3.8import sysread = sys.stdin.buffer.readreadline = sys.stdin.buffer.readlinereadlines = sys.stdin.buffer.readlinesfrom functools import lru_cachepopcount = [0]for _ in range(10):popcount = popcount + [x + 1 for x in popcount]@lru_cache(None)def simu(B, n, add):assert n < (1 << B)if B < 10:step = 0while n < (1 << B):n += popcount[n] + addstep += 1return step, nstep, n = simu(B - 1, n, add)m = n - (1 << (B - 1))step1, n = simu(B - 1, m, add + 1)n += 1 << (B - 1)return step + step1, ndef simu_naive(B, n, add):step = 0while n < 1 << B:n += bin(n).count('1') + addstep += 1return step, nN = int(read())add = 0total_step = 1n = 1for B in range(60, 10, -1):if N - n < (1 << B):continueq, r = divmod(n, 1 << B)step, next_n = simu(B, r, bin(q).count('1'))n = (q << B) + next_ntotal_step += stepwhile n < N:total_step += 1n += bin(n).count('1')answer = -1 if n != N else total_stepprint(answer)