問題一覧 > 通常問題

No.156 キャンディー・ボックス

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 640
作問者 : nmnmnmnmnmnmnmnmnmnmnmnmnmnm
4 ProblemId : 307 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2015-11-14 17:47:52

問題文

キャンディーが入っている箱が$N$個ある。
$i$番目の箱には$C_i$個のキャンディーが入っている。
A君は、その時の最もキャンディーの少ない箱から1つキャンディーを取っていく。
これを合計$M$個のキャンディーを取り終えるまで繰り返す。

$M$個のキャンディーを取り出した時に、空になった箱の数はいくつか?

入力

$N$ $M$
$C_1$ $C_2$ $\dots$ $C_N$

$1 \le N \le 10$
$1 \le M \le 1000000$
$1 \le C_i \le 100000$
$M$は最初のキャンディーの総数以下の数字が与えられる。

出力

$M$個のキャンディーを取ったあとに空になった箱の数を1行で答えよ。
最後に改行を忘れずに。

サンプル

サンプル1
入力
3 2
1 2 3
出力
1

キャンディーの箱が3つある。
1つ目の箱にはキャンディーが1つ。
2つめの箱にはキャンディーが2つ。
3つめの箱にはキャンディーが3つ。
A君はこれから合計2つのキャンディーを取る。
A君はまず1つのキャンディーが入った箱からキャンディーを1つ取る。
次に、キャンディーが2つ入った箱からキャンディーを1つ取る。
1つ目の箱にはキャンディーが0つ。
2つめの箱にはキャンディーが1つ。
3つめの箱にはキャンディーが3つ。
最後に残った空のキャンディーの箱の数は1個である。

サンプル2
入力
3 2
1 1 3
出力
2

キャンディーの箱が3つある。
1つ目の箱にはキャンディーが1つ。
2つめの箱にはキャンディーが1つ。
3つめの箱にはキャンディーが3つ。
A君はこれから合計2つのキャンディーを取る。
A君はまず1つのキャンディーが入った箱からキャンディーを1つ取る。
次に、もう1つのキャンディーが1つ入った箱からキャンディーを1つ取る。
1つ目の箱にはキャンディーが0つ。
2つめの箱にはキャンディーが0つ。
3つめの箱にはキャンディーが3つ。
最後に残った空のキャンディーの箱の数は2個である。

サンプル3
入力
4 10
3 2 4 1
出力
4

すべての箱が空になる。

サンプル4
入力
6 257109
53771 46578 31908 80435 62678 4327
出力
5

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。