結果

問題 No.3 ビットすごろく
ユーザー fgshunfgshun
提出日時 2020-09-27 08:10:57
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 54 ms / 5,000 ms
コード長 895 bytes
コンパイル時間 89 ms
コンパイル使用メモリ 12,800 KB
実行使用メモリ 11,264 KB
最終ジャッジ日時 2024-07-01 09:56:22
合計ジャッジ時間 2,442 ms
ジャッジサーバーID
(参考情報)
judge1 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import sys
import itertools
import collections
def popcount(i):
c = 0
while i > 0:
i, m = divmod(i, 2)
if m:
c += 1
return c
def resolve(in_):
N = int(next(in_))
INF = 10 ** 9
costs = [INF] * (N + 1)
costs[1] = 1
used = [False] * (N + 1)
q = collections.deque()
q.append((1, 1))
while q:
pos, cost = q.pop()
if used[pos]:
continue
used[pos] = True
p = popcount(pos)
f = pos + p
if f <= N:
costs[f] = min(costs[f], cost + 1)
q.appendleft((f, cost + 1))
b = pos - p
if b > 0:
costs[b] = min(costs[b], cost + 1)
q.appendleft((b, cost + 1))
return costs[N] if costs[N] != INF else -1
def main():
ans = resolve(sys.stdin.buffer)
print(ans)
if __name__ == '__main__':
main()
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0