問題一覧 > 通常問題

No.3 ビットすごろく

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 1053
作問者 : yuki2006yuki2006
27 ProblemId : 11 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2016-01-20 02:32:29

問題文

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つしかマスがないときは到達することは出来ません。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。