D - Caracal vs Monster

分数: 400 分

问题描述

Caracal正在与怪物战斗。

怪物的初始健康值为 $H$。

Caracal可以通过选择一只怪物来进行攻击。当攻击一只怪物时，根据该怪物的健康值发生以下情况：

• 如果怪物的健康值为 $1$，那么它的健康值变为 $0$。
• 如果怪物的健康值 $X$ 大于 $1$，那么这个怪物消失，然后会出现两只新的怪物，每只怪物的健康值都是 $\lfloor X/2 \rfloor$。

($\lfloor r \rfloor$ 表示不超过 $r$ 的最大整数。)

当所有存在的怪物的健康值都变为 $0$ 或更低时，Caracal获胜。

请找出Caracal在获胜之前需要攻击的最小次数。

约束

• $1 \leq H \leq 10^{12}$
• 输入中的所有值均为整数。

---

输入

从标准输入中以以下格式给出：

$H$

输出

找出Caracal在获胜之前需要攻击的最小次数。

---

2  

3  

当Caracal攻击初始怪物时，它消失了，然后出现了两个怪物，每个怪物的健康值为 $1$。

然后，Caracal可以攻击这两个新的怪物中的每一个一次，以总共三次攻击获胜。

---

4  

7  

---

1000000000000  

1099511627775