Divide and Divide

题目描述

黑板上写着一个整数 $N$。
Takahashi 将重复以下操作序列，直到黑板上所有不小于 $2$ 的整数都被移除为止：

选择黑板上写着的一个不小于 $2$ 的整数 $x$。 从黑板上擦去一个 $x$ 的出现。然后，在黑板上写下两个新整数 $\left \lfloor \dfrac{x}{2} \right\rfloor$ 和 $\left\lceil \dfrac{x}{2} \right\rceil$。 Takahashi 必须支付 $x$ 日元来执行该操作序列。

这里，$\lfloor a \rfloor$ 表示不大于 $a$ 的最大整数，$\lceil a \rceil$ 表示不小于 $a$ 的最小整数。 当不能再进行操作时，Takahashi 一共支付了多少？
可以证明，他支付的总金额与执行操作的顺序无关，为常数。

输入格式

输入从标准输入按以下格式给出： $N$

输出格式

打印 Takahashi 已支付的总金额，单位为日元。

3

5

340

2888

100000000000000000

5655884811924144128

提示

$2 \leq N \leq 10^{17}$下面是 Takahashi 执行该操作的一个例子：

最初，黑板上写着一个 $3$。 他选择 $3$。他支付 $3$ 日元，擦去一个 $3$，并写下 $\left \lfloor \dfrac{3}{2} \right\rfloor = 1$ 和 $\left\lceil \dfrac{3}{2} \right\rceil = 2$ 在黑板上。 黑板上有一个 $2$ 和一个 $1$。 他选择 $2$。他支付 $2$ 日元，擦去一个 $2$，并写下 $\left \lfloor \dfrac{2}{2} \right\rfloor = 1$ 和 $\left\lceil \dfrac{2}{2} \right\rceil = 1$ 在黑板上。 黑板上有三个 $1$。 由于黑板上所有不小于 $2$ 的整数都已被移除，过程结束。

Takahashi 在整个过程中共支付了 $3 + 2 = 5$ 日元，因此输出 $5$。

标签: AtCoder|abc340C

来源

AtCoder|abc340C