No.3 ビットすごろく
yuki2006問題文最終更新日: 2024-12-14 23:56:17
問題文
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もしくは右上の雲マークをクリックしてアカウントを作成してください。