結果
問題 |
No.3 ビットすごろく
|
ユーザー |
|
提出日時 | 2021-12-04 17:13:25 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 49 ms / 5,000 ms |
コード長 | 598 bytes |
コンパイル時間 | 293 ms |
コンパイル使用メモリ | 12,672 KB |
実行使用メモリ | 11,008 KB |
最終ジャッジ日時 | 2024-07-06 23:25:57 |
合計ジャッジ時間 | 2,566 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
from collections import deque N = int(input()) num = [N+1] * (N+1) num[1] = 1 k = 1 while 2 ** k < N: k += 1 def keta(x): count = 0 for i in range(k + 1): if x & (1 << i): count += 1 return count q = deque() q.append(1) while len(q): x = q.popleft() c = keta(x) if x - c > 0: if num[x] + 1 < num[x - c]: num[x-c] = num[x] + 1 q.append(x - c) if x + c <= N: if num[x] + 1 < num[x + c]: num[x + c] = num[x] + 1 q.append(x + c) if num[N] == N+1: print(-1) else: print(num[N])