408517: GYM103176 J Just A \$10 Note

Jane is working as a cashier at a grocery store in Hackerland. This grocery store is now offering a special discount, all the items are on sale, each with a positive integral price of no more than $10.

In the early morning, $$$N$$$ customers are queuing outside the store waiting for the store to open, but they have not decided what to purchase yet. When Jane arrives, people in the queue all ask the same question: "I have just a $10 note, do you have enough coins for changes?". What a coincidence! Unfortunately, Jane knows that there are no coins in the store, so she has to ask for some from the bank.

In Hackerland, there are only three types of coins, $5, $2 and $1, and they are of equal weight. Jane wants to minimize the number of coins to carry as the coins are too heavy! Jane predicts that no more customers will be coming. Therefore, she should prepare the least number of coins, so that no matter which item(s) eventually each of the $$$N$$$ customers choose to purchase (of course, not more than $10 per person), she has enough amount of coins for changes.

You may assume that when Jane gets back to the store again, every customer has decided what to purchase so she will be able to know the amount of changes needed for every customer, then decide how to distribute the coins for giving the changes. Please note that she must give the exact amount of changes to every customer.

A single integer $$$N$$$, denoting the number of customers queuing outside the store ($$$1\le N\le 50$$$).

A single integer, denoting the minimum number of coins Jane carries, such that she has enough amount of coins for changes no matter what item(s) the $$$N$$$ customers purchase.

1

4

There is only one customer, one of the optimal ways is: Jane can prepare four coins: one $5 coin, one $2 coin, two $1 coins. There are ten possible situations:

• The customer purchase items that worth $10 in total, no changes needed!
• The customer purchase items that worth $9 in total, Jane can give one $1 coin back.
• The customer purchase items that worth $8 in total, Jane can give one $2 coin back.
• The customer purchase items that worth $7 in total, Jane can give one $2 coin and one $1 coin back.
• The customer purchase items that worth $6 in total, Jane can give one $2 coin and two $1 coins back.
• The customer purchase items that worth $5 in total, Jane can give one $5 coin back.
• The customer purchase items that worth $4 in total, Jane can give one $5 coin and one $1 coin back.
• The customer purchase items that worth $3 in total, Jane can give one $5 coin and one $2 coin back.
• The customer purchase items that worth $2 in total, Jane can give one $5 coin, one $2 coin and one $1 coin back.
• The customer purchase items that worth $1 in total, Jane can give one $5 coin, one $2 coin and two $1 coins back.