the voucher
Statement
Goal
Given a voucher and a list of products, find the number of combinations of products that match with the exact amount of money available on the voucher.Rule : product can be picked 0, 1, 2 or 3 times.
Output : print the number of different combinations of products.
Example:
Given the list of products:
- bread 90
- green salad 115
- sugar 750g 95
- rice 500g 299
If I have an amount of 300 cents on my voucher, I can only buy:
1 bread + 1 green salad + 1 bag of sugar => 90 + 115 + 95 = 300 cents
So the answer is 1 combination of products.
All prices are in cents .
Input
Line 1: An integer v for the voucher value in cents
Line 2: An integer n for the number of products
Next n lines: string l and p for the label and price of each product in cents
Line 2: An integer n for the number of products
Next n lines: string l and p for the label and price of each product in cents
Output
c Number of different combinations of products that you can buy.
Constraints
1 <= n <= 16
Example
Input
300 4 bread 90 green salad 115 sugar 750g 95 rice 500g 299
Output
1
Tags
Recursion, Backtracking
Difficulty
Medium
Test cases
1) Example Test
Input
300
4
bread 90
green salad 115
sugar 750g 95
rice 500g 299
Output
1
1) Example Validator
Input
300
4
bread 95
green salad 110
sugar 850g 95
rice 500g 278
Output
3
2) 3 copies of each Test
Input
900
4
bread 90
green salad 115
sugar 750g 95
rice 500g 299
Output
1
2) 3 copies of each Validator
Input
900
4
bread 89
green salad 120
sugar 750g 91
rice 500g 297
Output
1
3) many solutions Test
Input
900
4
bread 89
green salad 120
sugar 750g 91
rice 500g 299
Output
2
3) many solutions Validator
Input
900
5
bread 89
green salad 120
pasta 500g 190
rice 500g 299
sugar 750g 91
Output
2
4) different products with same price Test
Input
500
4
cucumber 100
pepper 100
zucchini 100
onion 100
Output
40
4) different products with same price Validator
Input
400
5
cucumber 100
pepper 100
zucchini 100
onion 100
potato 100
Output
65
5) more money Test
Input
800
16
pack of 6 eggs 155
Nutri-Grain Breakfast Bar 900
Salted Kaju 175 gms 456
soya milk vanilla 1LTR 780
low-fat cheese 760
dark chocolate bar 230
milk chocolate bar 180
pepper 100
tomato sauce 250ml 220
mustard 200g 250
pasta 500g 190
quinoa 500g 350
steak 200g 850
lamb 250g 530
ham 100g 380
pork 200g 650
Output
13
5) more money Validator
Input
1000
10
pack of 6 eggs 155
Nutri-Grain Breakfast Bar 1000
Salted Kaju 175 gms 456
soya milk vanilla 1LTR 780
low-fat cheese 760
dark chocolate bar 230
milk chocolate bar 180
pepper 100
tomato sauce 250ml 220
mustard 200g 250
Output
10
Solution language
Solution
Stub generator input