結果

問題 No.3 ビットすごろく
コンテスト
ユーザー kuromook
提出日時 2016-06-02 22:36:01
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 997 bytes
コンパイル時間 358 ms
コンパイル使用メモリ 12,928 KB
実行使用メモリ 498,268 KB
最終ジャッジ日時 2024-10-08 06:01:23
合計ジャッジ時間 6,865 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 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))
	else:
		print(-1)

main()
0