問題一覧 > 通常問題

No.15 カタログショッピング

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 184
作問者 : なおなお
4 ProblemId : 39 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2015-11-14 17:48:17
(writer告知)
2014/12/16 17:45 テストケースの入力形式に誤りがあったため修正しました。

問題文

太郎君はカタログショッピングが大好き。

今日もカタログから商品を選んで購入したのだが、
太郎君はとてもお金持ちなので適当に商品を選んでしまい、
何を購入したかいつも忘れてしまいます。

幸い、クレジットカードの明細は手元にあるので、
購入した合計金額だけはわかりました。

太郎君が何を購入したのかを計算し、その商品番号を太郎君に教えてあげてください。
ただし、一つの商品を複数買うことはないものとします。

入力

\(N\ S\)
\(P_1\)
\(P_2\)
\(\dots\)
\(P_N\)

\(1\)行目に、カタログに載っている商品の数を表す整数\(N\ (1 \leq N \leq 31)\)と、
購入した合計金額を表す整数\(S\ (1 \leq S \leq 310000000)\)がスペース区切りで与えられる。
続く\(N\)行に、商品番号\(i\ (1 \leq i \leq N)\) の価格を表す整数\(P_i\ (1 \leq P_i \leq 10000000)\)が与えられる。

出力

購入した商品の商品番号を\(1\)行に、昇順で、\(1\)つのスペース区切りで出力してください。
行の最後に改行してください。
購入した商品の組み合わせが複数あり得る場合、昇順となるようすべて出力してください。
(組み合わせ内で、より小さい商品番号が先に来る組み合わせを先に出力してください。出力例はsample4,sample5を参照)

出力が50行以上になるような入力が与えられることはありません。

サンプル

サンプル1
入力
3 220
180
220
280
出力
2

太郎君は\(3\)つの商品の中から、\(2\)番の商品だけを購入しました。

サンプル2
入力
5 150
10
30
40
20
50
出力
1 2 3 4 5

太郎君は\(5\)つの商品をすべて購入しました。

サンプル3
入力
12 348940
47250
76500
9520
29960
19520
70960
91390
35610
71190
25840
10150
35000
出力
2 3 4 6 7 8 12

サンプル4
入力
15 445566
13075
16966
20695
21052
25917
25917
28431
31001
44064
47151
59372
63934
63934
66757
88888
出力
4 5 7 9 10 11 12 14 15
4 5 7 9 10 11 13 14 15
4 6 7 9 10 11 12 14 15
4 6 7 9 10 11 13 14 15

同じ値段の商品が複数存在する場合があります。
あり得る\(4\)つの組み合わせを、昇順に出力してください。

サンプル5
入力
4 20000
10000
10000
10000
10000
出力
1 2
1 3
1 4
2 3
2 4
3 4

すべて同じ値段なので、どれか\(2\)つを購入したようです。
あり得る\(6\)つの組み合わせをすべて出力してください。

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