結果
問題 | No.3 ビットすごろく |
ユーザー |
![]() |
提出日時 | 2019-07-11 21:41:58 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 61 ms / 5,000 ms |
コード長 | 786 bytes |
コンパイル時間 | 147 ms |
コンパイル使用メモリ | 82,212 KB |
実行使用メモリ | 70,616 KB |
最終ジャッジ日時 | 2024-07-01 09:24:53 |
合計ジャッジ時間 | 2,865 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
class Que: def __init__(self, li=[]): self.li = li def popleft(self): if not self.li: return -1 x = self.li[0] del self.li[0] return x def append(self, x): return self.li.append(x) def has_q(self): if self.li: return True else: return False N = int(input()) memory = [-1] * (N + 1) memory[1] = 1 q = Que([1]) while q.has_q(): i = q.popleft() ones = bin(i)[2:].count('1') forward = i + ones back = i - ones if 0 < forward <= N and memory[forward] == -1: memory[forward] = memory[i] + 1 q.append(forward) if 0 < back <= N and memory[back] == -1: memory[back] = memory[i] + 1 q.append(back) print(memory[N])