Back to Category
d061: [2005] B - Payment Efficiency
Keyword: NCPC 2005

Difficulity: 2 | Test Data Sets: 1 (Hidden) | Judging: Traditional Judge
Accepted : 25 Times | Submit :51 Times | Clicks : 923
Accepted : 15 Users | Submit : 15 Users | Accepted rate : 100%
Time Limit :1000 ms | Memory Limit : 64000 KBytes
Update : 2009-09-13 15:55

Content:

Consider k kinds of coins with different values in dollars, and a toy of P dollars. The problem asks to calculate the minimum number of coins involved in the payment process for buying the toy. It is assumed that both parties, i.e., the buyer and the seller, have sufficient numbers of each kind of coin at their disposal. For example, suppose that there are 6 kinds of coins with values 1, 2, 5, 10, 20, 50 dollars, and the price of the toy is 83 dollars. If a father wants to buy the toy for his child, one possible payment process is that he pays for the toy with one 50-dollar coin, one 20-dollar coin, one 10-dollar coin and one 5-dollar coin, and receives one 2-dollar coin in change. That is, 50 + 20 + 10 + 5 - 2 = 83, which has 5 coins involved. Another possible payment process is: 50 + 20 +20 - 5 - 2. For this example, any possible payment process will have at least 5 coins involved, and hence 5 is the desired answer.

Input:

The first line of the input file contains the number of test cases. For each test case, there are integers on a line. The first integer is k (1 ≤ k ≤ 10), denoting the number of different kinds of coins. The second integer is P (1 ≤ P ≤ 100), denoting the price of the toy. There are k different positive integers in the rest of the line, denoting the values of the coins. Among the k integers, the smallest number is always 1, and the largest number is not greater than 100.

Output:

For each test case, the output is a single line containing the minimum number of coins involved in the payment process for buying the toy.

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
3
6 83 1 2 5 10 20 50
6 36 1 24 34 39 46 50
6 42 1 2 3 7 19 72

Sample Output :

5
3
4

Hint :

Author :

NCPC 2005

  Solve it!   Status Forum

C
C++
JAVA
PASCAL
13959. shadeel
(2ms, 196KB, 1773B)
39274. rabbit125
(0ms, 716KB, 831B)

Program running time may be affected by various factors. Check server system environment information here