結果

問題 No.3 ビットすごろく
コンテスト
ユーザー aimBULL
提出日時 2016-06-17 01:25:29
言語 PyPy2
(7.3.15)
結果
TLE  
実行時間 -
コード長 551 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 130 ms
コンパイル使用メモリ 77,284 KB
最終ジャッジ日時 2025-12-03 20:52:22
ジャッジサーバーID
（参考情報） 		judge4 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 14 TLE * 2 -- * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from collections import deque

N = input()
table = [9999999999] * (N + 1)

q = deque()
q.append([1,1])

while len(q) > 0:
	p = q.popleft()
	current = p[0]
	cost = p[1]
	if current == N:
		print cost
		exit()
	
	next = (current + bin(current).count('1'))
	if 0 < next and next <= N:
		if cost + 1 <= table[next]:
			q.append([next, cost + 1])
			table[next] = cost + 1
	
	prev = (current - bin(current).count('1'))
	if 0 < prev:
		if cost + 1 <= table[prev]:
			q.append([current - bin(current).count('1'), cost + 1])
			table[prev] = cost + 1
print -1
0