/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
黒板に整数 N が 1 個書かれています。
高橋君は黒板に書かれている 2 以上の整数が全て無くなるまで以下の一連の操作を繰り返します。
- 黒板に書かれている 2 以上の整数を 1 つ選び x とする。
- 黒板から x を 1 個消す。そして、2 個の整数 \left \lfloor \dfrac{x}{2} \right\rfloor, \left\lceil \dfrac{x}{2} \right\rceil を新たに黒板に書く。
- この一連の操作を行うために高橋君は x 円払う必要がある。
ここで \lfloor a \rfloor は a 以下の整数のうち最大のものを、\lceil a \rceil は a 以上の整数のうち最小のものを意味します。
操作を行えなくなった時点で高橋君が払った金額の総和は何円ですか？
なお、どのような順番で操作を行っても高橋君が払う金額の総和は一定であることが証明できます。
制約
- 2 \leq N \leq 10^{17}
入力
入力は以下の形式で標準入力から与えられる。
N
出力
高橋君が払った金額の総和が何円であるかを出力せよ。
入力例 1
3
出力例 1
5
高橋君が行う操作の一例を挙げると次のようになります。
- はじめ、黒板には 3 が 1 個書かれている。
- 高橋君は 3 を選ぶ。高橋君は 3 円を払い、黒板から 3 を 1 個消して \left \lfloor \dfrac{3}{2} \right\rfloor = 1, \left\lceil \dfrac{3}{2} \right\rceil = 2 を新たに黒板に書く。
- 黒板には 2 が 1 個と 1 が 1 個書かれている。
- 高橋君は 2 を選ぶ。高橋君は 2 円を払い、黒板から 2 を 1 個消して \left \lfloor \dfrac{2}{2} \right\rfloor = 1, \left\lceil \dfrac{2}{2} \right\rceil = 1 を新たに黒板に書く。
- 黒板には 1 が 3 個書かれている。
- 黒板から 2 以上の整数が全て無くなったので操作を終了する。
操作全体で高橋君は 3 + 2 = 5 円払ったので、5 を出力します。
入力例 2
340
出力例 2
2888
入力例 3
100000000000000000
出力例 3
5655884811924144128
Score: 300 points
Problem Statement
There is a single integer N written on a blackboard.
Takahashi will repeat the following series of operations until all integers not less than 2 are removed from the blackboard:
- Choose one integer x not less than 2 written on the blackboard.
- Erase one occurrence of x from the blackboard. Then, write two new integers \left \lfloor \dfrac{x}{2} \right\rfloor and \left\lceil \dfrac{x}{2} \right\rceil on the blackboard.
- Takahashi must pay x yen to perform this series of operations.
Here, \lfloor a \rfloor denotes the largest integer not greater than a, and \lceil a \rceil denotes the smallest integer not less than a.
What is the total amount of money Takahashi will have paid when no more operations can be performed?
It can be proved that the total amount he will pay is constant regardless of the order in which the operations are performed.
Constraints
- 2 \leq N \leq 10^{17}
Input
The input is given from Standard Input in the following format:
N
Output
Print the total amount of money Takahashi will have paid, in yen.
Sample Input 1
3
Sample Output 1
5
Here is an example of how Takahashi performs the operations:
- Initially, there is one 3 written on the blackboard.
- He chooses 3. He pays 3 yen, erases one 3 from the blackboard, and writes \left \lfloor \dfrac{3}{2} \right\rfloor = 1 and \left\lceil \dfrac{3}{2} \right\rceil = 2 on the blackboard.
- There is one 2 and one 1 written on the blackboard.
- He chooses 2. He pays 2 yen, erases one 2 from the blackboard, and writes \left \lfloor \dfrac{2}{2} \right\rfloor = 1 and \left\lceil \dfrac{2}{2} \right\rceil = 1 on the blackboard.
- There are three 1s written on the blackboard.
- Since all integers not less than 2 have been removed from the blackboard, the process is finished.
Takahashi has paid a total of 3 + 2 = 5 yen for the entire process, so print 5.
Sample Input 2
340
Sample Output 2
2888
Sample Input 3
100000000000000000
Sample Output 3
5655884811924144128