No.378 名声値を稼ごう
タグ : / 解いたユーザー数 478
作問者 : LayCurse / テスター : 37zigen
問題文
あるゲームのクエストは何回でもクリアすることができ,クリアすることで名声値を得ることができます.
そのゲームのあるクエストは,初回にクリアすると $N$ だけの名声値が得られ,クリアするごとに得られる名声値が(小数点以下切り捨てで)半分になっていきます.
つまり,初回に得られる名声値が $12$ であれば,$1$ 回目,$2$ 回目,…にクリアした時に得られる名声値は $12, 6, 3, 1, 0, 0, \ldots$ となります.
よって,合計では,$12 + 6 + 3 + 1 = 22$ の名声値を得られることになります.
ところが,あるスキルを持っているキャラクターを利用してクリアすると,得られる名声値の値が倍になり,その代わりに次回以降にクリアした時に得られる名声値は $0$ になります.
例えば,$1$ 回目は普通にクリアし,$2$ 回目はそのキャラクターを利用してクリアすると,得られる名声値は $12 + 2 \times 6 + 0 + 0 + \cdots = 24$ となります.
常にスキルを持ったキャラクターを利用しない場合と比べて,うまくスキルを持っているキャラクターを利用すると,いくらの名声値を余分に得ることができるか,最大値を求めるプログラムを書いてください.
入力
$N$
$1 \leq N \leq 10^{18}$
出力
余分に得られる名声値の最大値を出力してください.
サンプル
サンプル1
入力
12
出力
2
本文中に書かれている例です.
普通にクリアし続けると得られる名声値は $22$ ですが,うまくすれば $24$ の名声値が得られるので,答えは $24-22 = 2$ となります.
サンプル2
入力
123456789123456789
出力
31
入力が $32$ ビット整数型には収まらないことに注意してください.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。