時間制限:$2.0sec$ / メモリ制限:$256MB$ / tester:square1001
わてれさんは、たまねぎをK個もらいました。一つ当たりの量はBグラムです。
そこで、n人いる友達のどうぶつに、玉ねぎ料理をふるまうことにしました。(焼くだけ)
わてれさんは、1回こたまねぎを切ることによって、1つのこたまねぎ(のかけらでもよい)を任意の割合で重さの二つに分割できます。
i番目の動物は、少なくともAiグラムのこたまねぎがないと満足しません。ただし、2つ以上のこたまねぎを一匹に与えることは可能です。
そのこたまねぎを動物たちに分けることにより、すべての動物が満足するようにしたいです。
ただし、こたまねぎは切ると涙が出てくるので、こたまねぎを切る回数を最小化したいです。
その時の、切る回数を求めなさい。
ただし、こたまねぎが不足することはないとします。
入力は以下の形式で標準入力から与えられる。
n K B
A1
A2
...
An
こたまねぎを切る最小回数を出力してください。
3 2 100
20 90 60
1
この場合、一つの玉ねぎを30グラムと70グラムに切ります。 そして、1番の動物には30グラム 2番には丸ごと1個 3番には70グラムわたせばよいです。
5 2 100
50 20 40 30 50
3
この場合、1つの玉ねぎを30と30と40に分けて、もうひとつを50と50に分けます