# Python代写 | CS 602 Algorithm Design and Implementation

CS 602
Algorithm Design and Implementation
Assignment 3
[Question 1] Number of ways to make a change
There circulate m kinds of coins in the state of Temapura with denomination of 𝑑1, 𝑑2, … , 𝑑𝑚 in
cents. For example, given coin denominations {1, 2, 5}, the ways to make up n = 7 cents are {1,
1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 2, 1}, {5, 2}, {2, 1, 2, 1, 1}, {1, 5, 1}, {2, 2, 1, 2}, so there are 6 ways
to make up 7 cents. Note that the sequence of coins in each set does not matter, so each set is
considered one way to make up 7 cents. In this question, you are to compute the number of ways
to make a change of n cents given a set of denominations with unlimited supplies.
Inputs begin with a number indicating the number of test cases below. Each test consists of two
lines, where the first line describes the set of denominations and the second line describes the
sequence of changes to be computed. The denominations are all distinct between 1 and 99 both
inclusive, and there are at most 10 denominations in the set. Denominations always contain 1 cent
to ensure all changes can be made. The sequence of changes has a maximum length of 1000, and
the changes are between 1 and 1000. For each test case, output the number of ways to make the
change in the same sequence as the changes are given.
Sample code is provided in the file A3Q1.py. You need to modify the function
num_ways_to_change.
There will be 8 testcases with 1 mark each. The remaining 2 marks are awarded with the correct
justification of the time complexity of your algorithm.
Sample Input
3
1 2 5
7 8 3 8 6 10 6
1 5 4 3
29 25 4 30 20 11 20 9 10
1 5 7 9 3
30 13 20 8 12 10 25 23 13 21 22
Sample Output
6 7 2 7 5 10 5
123 86 3 134 51 14 51 10 12
138 16 45 6 14 10 82 65 16 52 58
The state of Temapura is one of the busiest ports for the last 20 years. To keep its competitiveness,
the efficiency of operations is a big concern from the management of the port authority. You are
hired by the management to study how to efficiently unload containers from a ship. Let us make
some simple assumptions:
1. There are multiple stacks of containers on one ship, these stacks are lined up with fixed
distance in between.
2. There are a fixed number of cranes assigned to each ship to unload all containers from a
ship.
3. The cranes can never cross their arms.
4. It takes 2 minutes to unload one container from the stack that is aligned to the crane, for
every stack further from the aligned stack, the crane will take extra 2 minutes to unload.
For example, if a crane is aligned to stack 3, it takes 2 minutes to unload one container in
stack 3, and 6 minutes to unload one container in stack 5 since stack 5 is 2 stacks away
from stack 3.
5. The cranes can move left or right, but it can only stop at the aligned positions or a position
right in the middle of two neighboring stacks. In the second case, to unload from the two
nearest stacks takes 1 extra minute. For example, if a crane is stopped right in the middle
of stack 3 and 4, it takes 3 minutes to unload a container from either stack 3 or stack 4, and
5 minutes to unload a container from either stack 2 or stack 5.
As shown in the picture, the left crane takes charge of 4 stacks of containers and stopped right in
the middle of stack 2 and stack 3. The right crane takes charge of the remaining 6 stacks, and
stopped at the aligned position of stack 7.
Inputs begin with a number indicating the number of lines below. Each line begins with the number
of cranes assigned to the ship, and followed by the number of containers in each stack on a ship.
You need to output the minimum amount of time to unload all containers from the ship in minutes.
Sample code is provided in the file A3Q2.py. You need to modify the function
minimum_duration.
There will be 8 testcases with 1 mark each. The remaining 2 marks are awarded with the correct
justification of the time complexity of your algorithm.
Sample Input
1
2 10 10 7 5 5 9 7 8 10 7
Sample Output
180
Running python skeleton with sample input:
1. Open “Anaconda Prompt”
2. Go to the directory where you put the file A3Q1.py and A3Q1.in, using command cd
3. Run command python A3Q1.py < A3Q1.in
4. You may want to create a test input called my_own_test.in to design a test case for your
own program, the command would then be python A3Q1.py < my_own_test.in
5. Same applies to Question 2, so you may run python A3Q2.py < A3Q2.in