[AtCoder] ABC 153 D – Caracal vs Monster
問題
方針
モンスターの体力が \( 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; }
ディスカッション
コメント一覧
まだ、コメントがありません