Divide and Divide

AtCoder

IDabc340_c

Time2000ms

Memory256MB

Difficulty—

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$ [samples]

Samples

Input #1

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 $1$s 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$.

Input #2

Output #2

Input #3

100000000000000000

Output #3

5655884811924144128

API Response (JSON)

{
  "problem": {
    "name": "Divide and Divide",
    "description": {
      "content": "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 ",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc340_c"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There is a single integer $N$ written on a blackboard.  \nTakahashi will repeat the following series of operations until all integers not less than $2$ are removed from the blackboard:\n\n*   Choose one ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments