B18 - Subset Sum with Restoration
Editorial
/
Time Limit: 1 sec / Memory Limit: 1024 MB
配点 : 1000 点
問題文
N 枚のカードが一列に並べられており、左から i 番目のカード(以下、カード i とする)には整数 A_i が書かれています。カードの中からいくつかを選んで、書かれた整数の合計が S となるようにする方法が存在するか判定し、存在する場合はその方法を 1 つ求めてください。
制約
- 1 \leq N \leq 60
- 1 \leq S \leq 10\,000
- 1 \leq A_i \leq 10\,000
- 入力される値はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N S A_1 A_2 \cdots A_N
出力
カードの中からいくつかを選んで、書かれた整数の合計が S となるようにする方法が存在する場合、選ぶカードの番号を P_1, P_2, …, P_K として以下の形式で出力してください。
K P_1 P_2 \cdots P_K
そのような方法が存在しない場合、-1
を出力してください。
入力例 1
3 7 2 2 3
出力例 1
3 1 2 3
カード 1・カード 2・カード 3 を選んだ場合、書かれた整数の合計は 2+2+3=7 となります。
入力例 2
3 10 1 2 4
出力例 2
-1
入力例 3
10 100 14 23 18 7 11 23 23 5 8 2
出力例 3
6 2 3 6 7 8 9