結果
問題 | No.3 ビットすごろく |
ユーザー |
|
提出日時 | 2020-06-22 18:22:38 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 48 ms / 5,000 ms |
コード長 | 633 bytes |
コンパイル時間 | 88 ms |
コンパイル使用メモリ | 13,056 KB |
実行使用メモリ | 12,672 KB |
最終ジャッジ日時 | 2024-07-01 09:51:25 |
合計ジャッジ時間 | 2,309 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
from collections import deque n = int(input()) l = n.bit_length() g = [[] for _ in range(n + 1 + l)] if n == 1: print(1) exit() for i in range(n + 1): x = bin(i).count("1") g[i].append(i + x) g[i].append(i - x) par = [0] * (n + 1 + l) chk = [False] * (n + 1 + l) chk[0] = True stk = deque() stk.append(1) while stk: v = stk.popleft() for y in g[v]: if chk[y]: continue if y == par[v]: continue chk[y] = True par[y] = v stk.append(y) if not chk[n]: print(-1) exit() cnt = 1 while n > 1: n = par[n] cnt += 1 print(cnt)