No.3 ビットすごろく

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / タグ : / 解いたユーザー数 278
作問者 : yuki2006

5 ProblemId : 11

問題文

Carol は特殊なすごろくをしようとしている。

1からNの番号がふられている一直線に並べられているN個のマスがある。
1から開始のマスとして、ゴールはNが書かれているマスとする。

その場に書かれている数字の2進数で表現した時の1のビット数 だけ「前」または「後」に進めることができる。
(1未満とN+1以上のマスには移動することは出来ない、正確にNにならないとゴールできない)

自然数Nを与えられた時、ゴールに到達できる最短の移動数(開始のマスへも移動にカウントする)を求めてください。
到達できない場合は-1を出力してください。

開始のマスがすでにゴールになっている場合もあリます。

入力

N

マスの数を表す整数$N(1 \le N \le 10000)$が与えられます。

出力

最短の移動数、または -1

サンプル

サンプル1
入力
5
出力
4

1->2->3->5
という経路をたどります。

サンプル2
入力
11
出力
9

1->2->3->5->7->10->8->9->11

という経路をたどると9移動数で到達します。

サンプル3
入力
4
出力
-1

4つしかマスがないときは到達することは出来ません。

提出ページヘ