結果

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

ソースコード

diff # 

def dfs(now,count,path,N):
	if now == N:return count
	s = str(bin(now)).count('1')
	if s == 0:
		return 10000 + 1
	next1 = now + s
	next2 = now - s
	ret1,ret2 = 10000 + 1,10000 + 1
	if not(next1 > N or path[next1 - 1]):
		path[next1 - 1] = True
		ret1 = min(ret1,dfs(now + s,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 - s,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