CodeIQ過去問集42：少ない重りで重さを量ろう
本稿はCodeIQで出題された 第1回プロコン：【雉】くそ生意気な雉を黙らせよう という問題を再編集したものです。 ※出題時と記述が一部異なる場合がありますがご了承ください。
第2問：少ない重りで重さを量ろう
【ストーリー】
じゃんけんにわざと負けてあげることで自信を取り戻した犬を仲間にしたあなた。
鬼が島にむかって旅路を急いでいると、後ろから声が。
雉 「桃太郎さん桃太郎さん、お腰につけたキビ団子ひとつ私にくださいな」
あなた「（お、これは確か仲間になるフラグのあの有名なセリフだな）
では、これをやるから私と一緒に鬼退治に行こうではないか」
雉 「…。このキビ団子って何グラムですかね？
重さによっては鬼退治に同行するより、自分で働いて買った方が早いんで」
あなた「…（雉以外の鳥じゃだめかな）」
とはいえ、犬、雉、猿をそろえなければ鬼には勝てません（と、童話に書いてあった）。
雉の前でキビ団子の重さを計って、大きな団子であることを証明しましょう。
雉 「あ、あと自分頭悪いやつにはついていきたくないんで、最少のおもりの数で計ってくださいね。」
あなた「…（そこにいる雀でなんとか鬼退治できねえかな）」
※この画像は私が用意したものではないので、問題が発生した場合はすぐに差し替えるか消します。
【問題】
てんびんが1つあります。これを1回だけ使い、1グラムからnグラムまで、1グラム刻みの重さn通りをすべて量ることができるようにします。使用するおもりの個数をできるだけ少なくなるようにすると、おもりは最低いくつ必要になるかを計算してください。
例えば4グラムまですべて量るには、1グラムのおもり(A)と3グラムのおもり(B)を用意すると、次のように1～4グラムすべて量ることができます。
1グラム…(A)をてんびんの片側に置く
2グラム…(A)をてんびんの片側に、(B)をその反対側に置く（3-1=2グラムを量ることができる）
3グラム…(B)をてんびんの片側に置く
4グラム…(A)と(B)の両方をてんびんの片側に置く（3+1=4グラムを量ることができる）
【入力】
標準入力から、整数n（1≦n≦300）が与えられます。
【出力】
標準出力に、入力nに対するおもりの個数の最小値のみを出力してください。行末の改行コードは有無を問いません。
【入出力例】
Case 1: Input
4
Case 1: Output
2
Case 2: Input
10
Case 2: Output
3
