白俊1094号:棒


1.質問




2.例


問題の条件は少し厳しいように見える.
例を見てください.
例1:入力23
[繰り返し1]
1.64を半分に切ると32,32になります.
2.32は、x(23)よりも大きいので、カットされた32を廃棄する.
(長さ:32)
[繰り返し2]
1.32を半分に切ると、16、16になります.
2.16はx(23)より小さいので、切った16は捨てられません.
(長さ:16、16)
[繰り返し3]
1.16を半分に切ると、8、8になります.
2.24(16+8)はx(23)より大きいので、切り取った8を取り除きます.
(長さ:16、8)
[繰り返し4]
1.8を半分に切ると4,4になります.
2.20(16+4)はx(23)より小さく、切り取った4を捨てることはできない.
(長さ:16、4、4)
[繰り返し5]
1.4を半分に切ると2.2になります.
2.22(16+4+2)はx(23)より小さく、切った2を捨てることはできない.
(長さ:16、4、2、2)
[繰り返し6]
1.2を半分に切ると1.1になります.
2.23(16+4+2+1)はx(23)に等しいので、カットした1を捨てます.
(長さ:16、4、2、1)
裁断長さの総和が23であるため、演算終了後、レバーの総数4が正解となる.

3.解除


問題を解く過程は上と同じ長さですが、最終的には各段階で作られた棒を使うか、バイナリで表現すればいいです.
すなわち,入力値をバイナリ数とした後,1個の数を漏らすとよい.
そこで、入力値を2に分け、残り値が1の場合をチェックします.
#include <iostream>
using namespace std;

int main()
{
    int n, ans = 0;
    cin >> n;

    n *= 2;
    while (n /= 2)
    {
        if (n % 2 == 1)
            ans++;
    }

    cout << ans << endl;
}