結果

問題 No.3 ビットすごろく
ユーザー tookunn_1213
提出日時 2015-08-16 11:52:39
言語 Python2
(2.7.18)
結果
TLE  
実行時間 -
コード長 706 bytes
コンパイル時間 41 ms
コンパイル使用メモリ 6,912 KB
実行使用メモリ 13,604 KB
最終ジャッジ日時 2024-07-18 09:49:17
合計ジャッジ時間 6,503 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 TLE * 1 -- * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

def dfs(now,count,path,N):
	if now == N:return count
	if str(bin(now)).count('1') == 0:
		return 10000 + 1
	next1 = now + str(bin(now)).count('1')
	next2 = now - str(bin(now)).count('1')
	ret1,ret2 = 10000 + 1,10000 + 1
	if not(next1 > N or path[next1 - 1]):
		path[next1 - 1] = True
		ret1 = min(ret1,dfs(now + str(bin(now)).count('1'),count + 1,path,N))
		path[next1 - 1] = False
	if not(next2 <= 0 or path[next2 - 1]):
		path[next2 - 1] = True
		ret2 = min(ret2,dfs(now - str(bin(now)).count('1'),count + 1,path,N))
		path[next2 - 1] = False
	return min(ret1,ret2)
N = int(raw_input())
path = [False for i in range(N)]
path[0] = True
ans = dfs(1,1,path,N)
if ans == 10000 + 1:
	print -1
else:
	print ans
0