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

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

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

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 186
作問者 :

なお

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$ つの商品の中から、 $2$ 番の商品だけを購入しました。

サンプル2

入力

出力

1 2 3 4 5

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

サンプル3

入力

出力

2 3 4 6 7 8 12

サンプル4

入力

出力

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

入力

出力

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

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

yukicoder

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

問題文

入力

出力

サンプル

サンプル1

入力

出力

サンプル2

入力

出力

サンプル3

入力

出力

サンプル4

入力

出力

サンプル5

入力

出力