Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

Language: Margaritas on the River Walk
Description One of the more popular activities in San Antonio is to enjoy margaritas in the park along the river know as the Given the price of a single margarita (including applicable taxes and gratuities) at each of the various establishments and the amount allocated to sampling the margaritas, find out how many different maximal combinations, choosing at most one margarita from each establishment, you can purchase. A valid combination must have a total price no more than the allocated amount and the unused amount ( For example, suppose you have $25 to spend and the prices (whole dollar amounts) are:
Then possible combinations (with their prices) are: ABC(25), ABD(24), ABJ(22), ACD(23), ACJ(21), ADJ( 20), AH(24), BCD(24), BCJ(22), BDJ(21), BH(25), CDJ(20), CH(24), DH(23) and HJ(21). Thus the total number of combinations is 15. Input The input begins with a line containing an integer value specifying the number of datasets that follow, ≤ 1000). Each dataset starts with a line containing two integer values N and V representing the number of vendors (1 ≤ D ≤ 30) and the dollar amount to spend (1 ≤ V ≤ 1000) respectively. The two values will be separated by one or more spaces. The remainder of each dataset consists of one or more lines, each containing one or more integer values representing the cost of a margarita for each vendor. There will be a total of D cost values specified. The cost of a margarita is always at least one (1). Input values will be chosen so the result will fit in a 32 bit unsigned integer.VOutput For each problem instance, the output will be a single line containing the dataset number, followed by a single space and then the number of combinations for that problem instance. Sample Input 2 6 25 8 9 8 7 16 5 30 250 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 Sample Output 1 15 2 16509438 Hint
Source |

[Submit] [Go Back] [Status] [Discuss]

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator