お菓子の詰め合わせ
(paizaランク A 相当)
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
下記の問題をプログラミングしてみよう！
A 君は学校の遠足に持っていくお菓子を買わなければなりません。しかし、学校のルールにより、お菓子の総額は指定範囲内に収めなければなりません。
そこで、指定金額ギリギリまで使って、なるべく色々な種類のお菓子を食べたいと思った A 君は買うお菓子を決めるために、学校のルールと自分の要望を踏まえて以下の基準を満たす買い方をすることにしました。
・お菓子の総額を指定範囲内
・種類の数を最大にする
・同じお菓子は複数買わない
・お釣りを最小
・お釣りを最小にすることよりも種類の数を最大にすることを優先する
お菓子の値段が書いてあるリストが与えられるので、A 君の代わりに、上記ルールを満たすお菓子の組み合わせを指定範囲内の最大の金額で買ったときのお釣りを求めてください。ただし、少なくとも一種類は指定範囲の値段で買えるものとします。
入力例 1 の場合は、以下のように、指定範囲の金額で最大 2 個買えます。そして、そのうち最小になるお釣りの金額は 20 円になります。
- 入力される値
-
入力は以下のフォーマットで与えられます。
N X
x_1
x_2
...
x_N
・ 1 行目にそれぞれ、選択できるお菓子の種類、指定制限金額を表す N, X が与えられます。
・ 続く N 行のうちの i 行目 (1 ≦ i ≦ N) には、i 番目のお菓子の値段を表す整数が与えられます。
・ 入力は合計で N + 1 行となり、入力値最終行の末尾に改行が １ つ入ります。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
お菓子の種類を最大に、お釣りを最小にした時のお釣りを整数で出力してください。末尾に改行を入れ、余計な文字、空行を含んではいけません。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・ 1 ≦ N ≦ 20
・ 0 < X ≦ 5000
・ 0 < x_i < 5000 (1 ≦ i ≦ N)
- 入力例1
-
3 300
150
120
130
- 出力例1
-
20
- 入力例2
-
4 1000
200
20
500
60
- 出力例2
-
220
