結果
問題 |
No.3 ビットすごろく
|
ユーザー |
![]() |
提出日時 | 2022-03-11 20:38:58 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 62 ms / 5,000 ms |
コード長 | 492 bytes |
コンパイル時間 | 343 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 64,384 KB |
最終ジャッジ日時 | 2024-09-16 00:29:30 |
合計ジャッジ時間 | 3,359 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
from collections import deque n = int(input()) tansaku = [0] * (n+1) dp = [-1] * (n+1) tansaku[1] = 1 dp[1] = 1 mada = deque([1]) while mada: i = mada.popleft() t = i cnt = 0 while t: if t & 1: cnt += 1 t >>= 1 if i + cnt <= n: if tansaku[i + cnt] == 0: tansaku[i + cnt] = 1 dp[i + cnt] = dp[i] + 1 mada.append(i + cnt) if i - cnt >= 1: if tansaku[i - cnt] == 0: tansaku[i - cnt] = 1 dp[i - cnt] = dp[i] + 1 mada.append(i - cnt) #print(dp) print(dp[n])