3. Gift Cards Description

TBank offers gift cards in three denominations: $10, $30, and $50. Jugg has collected a lot of them! He would like to use exactly N cards to purchase an item costing M dollars, without leaving any remaining balance on any cards he chooses. How many different ways can Jugg buy the item?

Input Format

The first line contains two integers, N and M.
- N is the number of cards Jugg wants to use.
- M is the total cost of the item.

Output Format

An integer representing the number of different ways to buy the item using exactly N cards.

Sample Input

```
4 80
```

Sample Output

```
2
```

Explanation

Jugg must use 4 cards to buy an $80 item. There are 2 ways to do this:
1) Two $10 gift cards and two $30 gift cards. (10 + 10 + 30 + 30 = 80)
2) Three $10 gift cards and one $50 gift card. (10 + 10 + 10 + 50 = 80)

Input Constraints

- 30%: $ N \leq 100 $
- 60%: $ N \leq 1000 $
- 100%: $ N \leq 5000, M \leq 250000 $

The constraints are N <= 5000 and M <= 250000. For the given sample input (N=4, M=80), there are two ways to buy the $80 item using 4 cards: (10+10+30+30) and (10+10+10+50).

To find the number of different ways Jugg can buy the item without leaving any remaining balance on the gift cards, we need to implement a dynamic programming approach. The dynamic programming table can be initialized with zeros, and then the number of ways to achieve each value from 0 to M using the given denominations can be calculated iteratively. Here's a summary of the steps:

Read the input values N and M.

Initialize a dynamic programming table of size (M+1) with all values set to zero.

Set dp[0] to 1, as there is one way to achieve a total of 0 (by not using any gift cards).

For each denomination (e.g., $10, $30, $50), iterate over the dp table and update the number of ways for each value that can be achieved using that denomination. The update formula is dp[i] += dp[i - denomination].

Finally, the value in dp[M] represents the number of different ways Jugg can buy the item using the exact number of cards required.

For the given sample input (N=4, M=80), there are two ways to buy the $80 item using 4 cards: (10+10+30+30) and (10+10+10+50).

The constraints for N are: 30%: N <= 100, 60%: N <= 1000, and 100%: N <= 5000. For M, it should be <= 250000.

To learn more about constraints visit :

https://brainly.com/question/14309521

#SPJ11