問題一覧 > 通常問題

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

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

問題文

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

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

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

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

入力

N

1N1012

出力

最短の移動数、または -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もしくは右上の雲マークをクリックしてアカウントを作成してください。