AT_abc153_d [ABC153D] Caracal vs Monster

题目描述

カラカル正在与怪物战斗。

怪物的体力为 $H$。

カラカル每次可以选择一只怪物进行攻击。攻击怪物时，根据被攻击怪物的体力，会发生以下两种情况之一：

• 如果怪物的体力为 $1$，则该怪物的体力变为 $0$。
• 如果怪物的体力为 $X > 1$，则该怪物消失，并新出现 $2$ 只体力为 $\lfloor X/2 \rfloor$ 的怪物。

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

如果所有怪物的体力都降为 $0$ 或以下，カラカル就获胜。

请你求出カラカル获胜所需的最少攻击次数。

输入格式

输入以以下格式从标准输入给出。

$H$

输出格式

输出カラカル获胜所需的最少攻击次数。

输入输出样例 #1

输入 #1

2

输出 #1

3

输入输出样例 #2

输入 #2

4

输出 #2

7

输入输出样例 #3

输入 #3

1000000000000

输出 #3

1099511627775

说明/提示

限制条件

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

样例解释 1

攻击怪物后，原本的怪物消失，出现 $2$ 只体力为 $1$ 的怪物。分别攻击这 $2$ 只怪物各 $1$ 次，总共攻击 $3$ 次即可获胜。

由 ChatGPT 4.1 翻译