ABC153 D - Caracal vs Monster
問題はこちら atcoder.jp
方針
体力 のモンスターを倒すのに必要な攻撃回数を求めるアルゴリズムを とすると,
times(H){ if H=1 1 を出力 else if H>=2 2*times([H/2])+1 を出力 }
と再帰的に表せます( は最初の攻撃)。] (ガウス記号,床関数)の処理がありますが,整数型は小数点以下切り捨てなので実際には何もする必要がありません。
コード
#include <bits/stdc++.h> using namespace std; long times(long h){ if(h==1){ return 1; }else{ return 2*times(h/2)+1; } } int main(){ long h; cin>>h; cout<<times(h)<<endl; }