はまやんはまやんはまやん

hamayanhamayan's blog

Packets [Manthan, Codefest 18 A]

http://codeforces.com/contest/1037/problem/A

[1,N]の数を作るために最小いくつの整数を用意すればよいか。
例) N = 6
1,2,3を用意すれば
1=1, 2=2, 3=3, 4=1+3, 5=2+3, 6=1+2+3
で全て作ることができるため、答えは3

解法

http://codeforces.com/contest/1037/submission/42452467

用意する数は1,2,4,8,16,...である。
ある数について2進数表記した場合にi桁目を1にするために2^iを使えばいい。
よって、Nを2進数表記した時に必要な桁数が必要な整数の個数となる。

int N;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;

    int ans = 0;
    while (0 < N) N /= 2, ans++;
    cout << ans << endl;
}