Caracal vs Monster

题目描述

Caracal 正在与一只怪物战斗。 怪物的 生命值 为 $H$。 Caracal 可以通过选择一个怪物来进行攻击。当一个怪物被攻击时，根据该怪物的生命值，会发生以下情况：

如果怪物的生命值为 $1$，它会降到 $0$。 如果怪物的生命值 $X$ 大于 $1$，该怪物消失。然后，出现两个新的怪物，每个怪物的生命值为 $\lfloor X/2 \rfloor$。

（$\lfloor r \rfloor$ 表示不超过 $r$ 的最大整数。） 当所有存在的怪物的生命值变为 $0$ 或更低时，Caracal 获胜。 求 Caracal 在获胜前需要进行的最少攻击次数。

输入格式

输入从标准输入给出，格式如下： $H$

输出格式

求 Caracal 在获胜前需要进行的最少攻击次数。

2

3

4

7

1000000000000

1099511627775

提示

$1 \leq H \leq 10^{12}$ 输入中的所有数值均为整数。当 Caracal 攻击初始怪物时，它消失，出现两个生命值为 $1$ 的怪物。 然后，Caracal 可以分别攻击这两个新怪物一次，总共三次攻击即可获胜。

标签: AtCoder|abc153D

来源

AtCoder|abc153D