問題一覧 > 通常問題

No.262 面白くないビットすごろく

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 35
作問者 : LayCurseLayCurse
4 ProblemId : 402 / 出題時の順位表
問題文最終更新日: 2015-11-14 17:48:23

問題文

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

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

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

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

入力

$N$

$1 \leq N \leq 10^{12}$

出力

最短の移動数、または $\verb|-1|$

サンプル

サンプル1
入力
3
出力
3
サンプル2
入力
71623783
出力
5691592
サンプル3
入力
1000000000000
出力
-1

例えば,$N$ が十分大きい時は次のように進むしかありません.

移動数   1  2  3  4  5  6  7  8  9 ...
マス     1  2  3  5  7 10 12 14 17 ...

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