[SOLVED] Cmput 274 assignment 5

Overview: The Iron Bank of Braavos has called in its debts, and as the Master of Coin for the realm,
you must repay a sum of S gold dragons. You have unlimited access to a set of coin denominations
minted by various houses across the Seven Kingdoms.Your goal is to try to gather coins that total exactly S gold dragons. You can use as many coins as
needed from any denomination, including multiple coins of the same value. However, the Iron Bank
values efficiency; they demand that you use the minimum number of coins to settle the debt.
Input: The input consists of 2 lines. The first line contains a list of available denominations. The
second line contains a single integer, S.1. Every coin denomination, di, is within the range: 1 ≤ di ≤ 103
2. 1 ≤ S ≤ 105
– the total sum you need to repay.Output: Output a single integer – the minimum number of coins required to accumulate exactly S
gold dragons. Or, if you cannot make exactly the sum S, return -1.
Example Input #1:
2 4 7
11
Example Output #1:
2
Example Input #2:
7 9
12
Example Output #2:
-1
Example Input #3:
3 7
12
1
Example Output #3:Specifications:
• Do not modify the main() function.
Marking Rubric: This question will be marked out of 90 for correctness (pass test cases):
• 90/90: Pass all 5 of the test cases
• 72/90: Pass any 4 of the test cases
• 54/90: Pass any 3 of the test cases
• 36/90: Pass any 2 of the test cases
• 18/90: Pass any of the test cases2 Writing and testing your solution
For the programming questions, you should edit the provided files and add your solution. You can
check your solution by running driver.py. You can see the output of your program in the Output/
folder, and any errors in the Error/ folder.Please do not change the driver file, only edit the solution file.
You can run the driver in a terminal as follows (assuming your working directory is the assignment
folder):
$ cd a s si gnmen t 5
$ cd Que s ti on 1
$ python3 d r i v e r . py
All t e s t s p a s sed !
$
Please add your name, student number, ccid, operating system and python version at the top of each
solution file by replacing the provided comments.3 Submission Instructions ( 10 points )
Please follow these submission instructions carefully. Correctly submitting all files is worth 10 points.
In these files, you must replace ccid with your own ccid. Your ccid is the first part of your UAlberta
email (ccid@ualberta.ca). Do not zip any of these files. Please submit the following files to eclass:
• ccid solutionQuestion1.py : Edit the provided file for question 1. After your solution passes
all test cases (which you must test using the driver), rename the file to include your ccid, that
is, ccid solutionQuestion1.py and submit it to eclass.