4135. ABC340_C
时间限制：1000 MS 内存限制：256 MB
题目描述
There is a single integer NNN written on a blackboard. Takahashi will repeat the following series of operations until all integers not less than 222 are removed from the blackboard: * Choose one integer xxx not less than 222 written on the blackboard. * Erase one occurrence of xxx from the blackboard. Then, write two new integers ⌊x2⌋\left \lfloor \dfrac{x}{2} \right\rfloor⌊2x⌋ and ⌈x2⌉\left\lceil \dfrac{x}{2} \right\rceil⌈2x⌉ on the blackboard. * Takahashi must pay xxx yen to perform this series of operations. Here, ⌊a⌋\lfloor a \rfloor⌊a⌋ denotes the largest integer not greater than aaa, and ⌈a⌉\lceil a \rceil⌈a⌉ denotes the smallest integer not less than aaa. 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≤N≤10172 \leq N \leq 10^{17}2≤N≤1017 --- ### Input The input is given from Standard Input in the following format: ``` NNN ``` ### Output Print the total amount of money Takahashi will have paid, in yen. --- ### Sample Input 1Copy Copy ``` 3 ``` ### Sample Output 1Copy Copy ``` 5 ``` Here is an example of how Takahashi performs the operations: * Initially, there is one 333 written on the blackboard. * He chooses 333. He pays 333 yen, erases one 333 from the blackboard, and writes ⌊32⌋=1\left \lfloor \dfrac{3}{2} \right\rfloor = 1⌊23⌋=1 and ⌈32⌉=2\left\lceil \dfrac{3}{2} \right\rceil = 2⌈23⌉=2 on the blackboard. * There is one 222 and one 111 written on the blackboard. * He chooses 222. He pays 222 yen, erases one 222 from the blackboard, and writes ⌊22⌋=1\left \lfloor \dfrac{2}{2} \right\rfloor = 1⌊22⌋=1 and ⌈22⌉=1\left\lceil \dfrac{2}{2} \right\rceil = 1⌈22⌉=1 on the blackboard. * There are three 111s written on the blackboard. * Since all integers not less than 222 have been removed from the blackboard, the process is finished. Takahashi has paid a total of 3+2=53 + 2 = 53+2=5 yen for the entire process, so print 555. --- ### Sample Input 2Copy Copy ``` 340 ``` ### Sample Output 2Copy Copy ``` 2888 ``` --- ### Sample Input 3Copy Copy ``` 100000000000000000 ``` ### Sample Output 3Copy Copy ``` 5655884811924144128 ```