SRM439 Div2 500

問題

N本のいくらでも水が入るボトルがある．最初それぞれ1リットルずつ入っている．同じ水の量の2つのボトルは1つに合わせることができたとき，K本以下にするには1リットルのボトルを何個追加すればいいか．

考え方

すべてのボトルは最初全て１リットルであることと，同じ量の2つのボトルがあわせられることからボトルに入っている水の量は常に2^k(k=0,1,...)であることがわかる．さらにボトル数を減らすためになるべくボトルは少ない本数で保持しないといけない．
N本のボトルをK本以下にするために，Nを超えない2^kはまとめられる本数と同じなので，余った(N-2^k)本で(K-1)本にまとめられればいい．以下同様に，(N-2^k)本を(K-1)本以下にすることを考える．最後にK=1のとき，余った本数N'は1つのボトルにしないといけないので，N'が2のベキ乗なら追加は0本，そうでないならばN'が2のベキ乗になるまでボトルを追加する．

反省

提出後にミスに気づいたのはいいけど，何度も再提出してしまった．ちゃんと提出する前にソースを全部確認すること．