選択要素の復元 Python2編（paizaランク A 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ツイートする
問題
下記の問題をプログラミングしてみよう！
長さ N の数列 A = a_1, a_2, ..., a_N と正の整数 K が与えられます。
a_1, a_2, ..., a_N からいくつかの要素を選んでその和を K とすることはできますか。
ただし、1 つも選ばないときの和は 0 とします。
和を K とすることができない場合は -1 を出力してください。
もし可能な場合は和を K とするために選ぶ要素の個数 M が最小となるように選んだときの値を出力してください。
このとき、そのような選び方が複数ある場合はどの選び方を出力しても構いません。
入力例 1 では A の全ての要素を選択すると和を 6 にすることができます。
入力例 2 で和を 4 にすることができる要素の選び方は次の 3 種類あります。
(1) 1, 3
(2) 1, 2, 1
(3) 2, 2
これらのうち最小の選択数は 2 のため、(1) か (3) のどちらかを出力すればよいです。
入力例 3 では和を 5 にすることはできません。
- 入力される値
-
N K
a_1 a_2 ... a_N
・1 行目で N と K が与えられます。
・2 行目で a_1, a_2, ..., a_N が空白区切りで与えられます。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
出力は次の形式に従って行ってください。
M
b_1 b_2 ... b_M
1 行目に選ぶ要素数 M を出力してください。
2 行目に選択した要素を並べた数列 b_1, b_2, ..., b_M を空白区切りで一行で出力してください。
末尾に改行を入れ、余計な文字、空行を含んではいけません。
- 条件
-
すべてのテストケースにおいて, 以下の条件をみたします
・入力はすべて整数
・1 ≦ N ≦ 1,000
・1 ≦ K ≦ 2,000
・1 ≦ a_i ≦ 100 (1 ≦ i ≦ N)
- 入力例1
-
3 6
1 2 3
- 出力例1
-
3
3 2 1
- 入力例2
-
5 4
1 3 2 2 1
- 出力例2
-
2
1 2
- 入力例3
-
5 5
2 2 2 2 2
- 出力例3
-
-1
