結果
問題 |
No.3 ビットすごろく
|
ユーザー |
|
提出日時 | 2018-02-05 17:28:04 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,391 bytes |
コンパイル時間 | 152 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 16,512 KB |
最終ジャッジ日時 | 2024-07-08 05:58:37 |
合計ジャッジ時間 | 8,804 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 8 TLE * 1 -- * 24 |
ソースコード
from collections import deque forward = [-1] backward = [-1] def count_one_bit(k): binary = bin(k)[2:] n_one_bit = 0 for b in binary: if b == "1": n_one_bit += 1 return n_one_bit def main(): global forward global backward N = int(input()) # 各セルにおいて,前後に動いたときの移動先の番号を計算する for cell_num in range(1, N+1): n_one_bit = count_one_bit(cell_num) # 前に進んだ場合のセル位置 if cell_num + n_one_bit <= N: forward.append(cell_num + n_one_bit) else: forward.append(-1) # 後ろに進んだ場合のセル位置 if cell_num - n_one_bit >= 0: backward.append(cell_num - n_one_bit) else: backward.append(-1) # ゴール(N)にいけるマスがないなら,-1を返す if N not in forward: print(-1) return cells = [] for i in range(N+1): cells.append(i) q = [] reached = [] for cell_num in range(1, N+1): if forward[cell_num] == N: q.append(cell_num) move = 1 while len(q) != 0: new_q = [] for item in q: if item in cells: cells.remove(item) if item == 1: print(move+1) return for cell_num in cells: if forward[cell_num] == item or backward[cell_num] == item: new_q.append(cell_num) q = new_q move += 1 print(-1) main()