Exact Change
Jack wants to pay for an item at the convenient store.
However, this particular store does not give change, so the amount he pays must be the exact price of the item he is buying.
Additionally, he must pay for the item using exactly three coins. Luckily, Jack brought a lot of coins, in fact, he brought n coins.
Jack would like to use exactly three of his coins to produce the exact change required for a given item with price p cents.
Write a program exact_change.c which scans a line containing p, then a line containing n,
then n lines containing the values (in cents) of each coin Jack brought.
Your program should then output 1 if Jack's wish can be fulfilled, and 0 if it cannot.
For example, if p is 150 and Jack brings three coins valued at 50 cents each,
then Jack's wish can be fulfilled by using those three coins. Hence, given
150\n3\n50\n50\n50 as input, your program should output 1.
For example, if p is 500 and Jack brings three coins valued at 200 cents each,
and one coin valued at 50 cents,
then Jack's wish cannot be fulfilled as he cannot produce exactly 500 cents.
Hence, given 500\n4\n200\n200\n200\n50 as input, your program should output 0.
Assumptions/Restrictions/Clarifications
- You may assume the each line of input will be a valid positive integer.
- You may assume that
nis at least 3 and at most 10. - You may assume that the value of each coin is at least 1 and at most 200.
CSE Autotest
When you think your program is working, you can use CSE autotest to test your solution.
$ 1511 autotest exact_changeSolution
You can view the solution code to this problem here.