結果
問題 |
No.3 ビットすごろく
|
ユーザー |
|
提出日時 | 2019-06-25 11:07:00 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 55 ms / 5,000 ms |
コード長 | 770 bytes |
コンパイル時間 | 181 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 12,160 KB |
最終ジャッジ日時 | 2024-07-01 09:22:56 |
合計ジャッジ時間 | 2,532 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
from collections import deque def main(): N = int(input()) queue = deque() L = [(False, i, 0) for i in range(N)] L[0] = (True, 1, 1) queue.append(L[0]) while len(queue) > 0: now = queue.popleft() if now[1] == N: print(now[2]) exit() d = count(now[1]) if (now[1] - d) > 0 and not L[now[1]-d-1][0]: L[now[1]-d-1] = (True, now[1] - d, now[2]+1) queue.append(L[now[1]-d-1]) if (now[1] + d) <= N and not L[now[1]+d-1][0]: L[now[1]+d-1] = (True, now[1] + d, now[2]+1) queue.append(L[now[1]+d-1]) print(-1) def count(i): return len(list(filter(lambda x: x == '1', str(bin(i))[2:]))) if __name__ == '__main__': main()