結果
問題 | No.3 ビットすごろく |
ユーザー |
![]() |
提出日時 | 2020-11-22 06:24:18 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 64 ms / 5,000 ms |
コード長 | 359 bytes |
コンパイル時間 | 172 ms |
コンパイル使用メモリ | 82,688 KB |
実行使用メモリ | 68,224 KB |
最終ジャッジ日時 | 2024-07-01 10:00:25 |
合計ジャッジ時間 | 3,098 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
def popcount(x):r = 0while x:r += x%2x //= 2return rn = int(input())dp = [-1]*(n+1)dp[1] = 1from collections import dequeq = deque()q.append(1)while q:v = q.popleft()c = popcount(v)for i in [v-c,v+c]:if 0 < i <= n and dp[i]==-1:dp[i] = dp[v]+1q.append(i)print(dp[n])