結果

問題 No.3 ビットすごろく
コンテスト
ユーザー aimBULL
提出日時 2016-06-17 01:25:29
言語 Python2
(2.7.18)
結果
TLE  
実行時間 -
コード長 551 bytes
コンパイル時間 274 ms
コンパイル使用メモリ 7,040 KB
実行使用メモリ 22,076 KB
最終ジャッジ日時 2024-10-09 16:42:59
合計ジャッジ時間 13,873 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 9 TLE * 2 -- * 22
権限があれば一括ダウンロードができます

ソースコード

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