結果

問題 No.3 ビットすごろく
ユーザー kuromook
提出日時 2016-06-02 22:34:25
言語 Python2
(2.7.18)
結果
WA  
実行時間 -
コード長 999 bytes
コンパイル時間 605 ms
コンパイル使用メモリ 6,784 KB
実行使用メモリ 418,476 KB
最終ジャッジ日時 2024-10-08 06:00:48
合計ジャッジ時間 6,934 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1 WA * 2 TLE * 1 -- * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

def go(n):
	ary = list(format(n,'b'))
	g = sum([int(a) for a in ary])
	return g


def sugoroku_map(val,debug=False):
	dic = {a:[a+go(a), a-go(a)] for a in range(1,val)}
	if debug:
		print(dic)
	return dic

def update_tree(val,dic, ary=[[1]]):
	reary = []
	for a in ary:
		b =list(a) 
		last = a[-1]
		if last in dic:
			el = dic[last]
			if last == val:
				reary.append(a)
			else:
				# foward
				if (el[0] <= val) and (el[0] > 1) and (el[0] not in a):
					a.append(el[0])
					reary.append(a)
				# back
				if (el[1] <= val) and (el[1] > 1) and (el[1] not in b):
					b.append(el[1])
					reary.append(b)
		else:
			reary.append(a)
	return reary


def main(debug=False):
	val = input()
	val = int(val)
	# make tree
	tree = [[1]]
	sugo_map=sugoroku_map(val, debug)
	for i in range(1,val):
		tree = update_tree(val,sugo_map,tree)
		if debug:
			print(tree)
	# tree length 
	length = [len(el) for el in tree if el[-1] == val]
	if len(length) > 0:
		print(min(length)+2)
	else:
		print(-1)

main()
0