Luffy Wants a Bike
All submissions for this problem are available.
The Straw Hat Pirates are on Sabaody Archipelago. Luffy sees a bubble bike. As usual, he insists on buying one for himself but the shopkeeper is very stubborn and accepts only exact amount of money.
Nami gave Luffy only certain values of coins.
We all know that Luffy doesn’t like to study so he is weak in maths. You have to help him decide on the minimum number of coins he should use in order to pay for the bike. In case you cannot form the exact amount using the given coins give the output as -1.
Assume you have infinite supply of coins of the given value.
The first line of the input contains a single integer T, denoting the number of test cases. The description of T test cases follows. The first line of each test case contains two space-separated integers N and M, denoting the number of different values of coins he has and number of types of bike, respectively. The second line of each test case contains N space separated integers Vi’s denoting the value of coins Nami gave Luffy. The third line of each test case contains M space separated integers Pi’s denoting the price of different types of bike.
For each test case output M space separated integers denoting the minimum number of coins needed to pay for that bike. In case it is not possible to form the exact price, output -1.
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 50
- 1 ≤ M ≤ 500
- 1 ≤ Vi ≤ 500
- 1 ≤ Pi ≤ 10000
3 6 9
15 16 21 22
2 -1 3 -1
Example case 1. Here, 15 can be made using 1 coin of value 6 and 1 value of coin 9. So, the solution is 2.
For 16, there are no such combinations of the given values, that add upto 16. So, the solution is -1.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP 4.3.2, CPP 6.3, CPP14, GO|
Fetching successful submissions
If you are still having problems, see a sample solution here.