[AtCoder] ABC 153 D – Caracal vs Monster

2020年12月15日

問題

方針

モンスターの体力が \( H \) から \( 1 \) になるまでのモンスターの体力の種類を考えます。このとき、\( i \) 番目に大きい体力を \( H_i \) とします。ここで、\( H_1 = H \) であり、\( H_2 = \left \lfloor \dfrac{H}{2} \right \rfloor \) です。

このとき、\( i \) 番目のモンスターの数は \( 2^{i – 1} \) となります。ここで、\( H_j = 1 \) を満たす \( j \) を \( n \) とすると、求める答えは、

\[\sum_{i = 1}^{n} 2^{i – 1}\]

となります。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    ll H;
    cin >> H;
    ll k = 1;
    ll t = 0;
    while (H > 0) {
        t += k;
        H /= 2;
        k *= 2;
    }
    cout << t << "\n";
    return 0;
}