No.15 Catalog Shopping
なお2014/12/16 17:45 The input format of the test cases contained an error and has been corrected.
Problem Statement
Taro loves catalog shopping.
Today he again chose items from a catalog and purchased them, but
since Taro is very rich, he picks items carelessly,
and he always forgets what he purchased.
Fortunately, he has his credit card statement at hand,
so at least the total amount of his purchase is known.
Compute what Taro purchased and tell him the item numbers.
Note that he never buys more than one of the same item.
Input
\(N\ S\) \(P_1\) \(P_2\) \(\dots\) \(P_N\)
The \(1\)st line contains an integer \(N\ (1 \leq N \leq 31)\), the number of items in the catalog, and
an integer \(S\ (1 \leq S \leq 310000000)\), the total amount of the purchase, separated by a space.
Each of the following \(N\) lines contains an integer \(P_i\ (1 \leq P_i \leq 10000000)\), the price of item number \(i\ (1 \leq i \leq N)\).
Output
Print the item numbers of the purchased items on \(1\) line, in ascending order, separated by \(1\) space.
Print a newline at the end of the line.
If multiple combinations of purchased items are possible, print all of them in ascending order.
(Print first the combination in which a smaller item number comes earlier within the combination. See sample4 and sample5 for output examples.)
No input will be given for which the output would be 50 lines or more.
Sample
Sample 1
Input
3 220 180 220 280
Output
2
Out of the \(3\) items, Taro purchased only item number \(2\).
Sample 2
Input
5 150 10 30 40 20 50
Output
1 2 3 4 5
Taro purchased all \(5\) items.
Sample 3
Input
12 348940 47250 76500 9520 29960 19520 70960 91390 35610 71190 25840 10150 35000
Output
2 3 4 6 7 8 12
Sample 4
Input
15 445566 13075 16966 20695 21052 25917 25917 28431 31001 44064 47151 59372 63934 63934 66757 88888
Output
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
There may be multiple items with the same price.
Print the \(4\) possible combinations in ascending order.
Sample 5
Input
4 20000 10000 10000 10000 10000
Output
1 2 1 3 1 4 2 3 2 4 3 4
All the items have the same price, so it seems he purchased some \(2\) of them.
Print all \(6\) possible combinations.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。