Description
Task 1 Puppies
(10 points)
Here you will use C++ to solve the problem. Note that the input / output requirements are
different though.
Queenie is living together with n puppies. Queenie is worried to lose sight of her puppies.
Write a C++ program that let Queenie know which of her puppies are too far away from
Queenie. A puppy p at position(px, py) is too far away from Queeny at (qx, qy) if
Sqrt ((px – qx)
2
+ (py – qy)
2
) > 10,
where Sqrt (x) denotes the square root of x
The position of Queenie, the number n, and the puppy positions are given by the user and you
can assume all positions are given with Integers.
The input containsmultiple lines: the firstline containstwo integers qx and qy representing
the position of Queenie, the second line containsfirst an integer n for the number of puppies
and then n pairs ofintegers(px and py) indicating the locations ofPuppy 1 toPuppy n.
Your program should output the puppy numbers (in the range of 1 to n) of the puppies
which are too far away from Queeny on the first output line, and then the total number of
puppies which are too far away on the second output line. Check the sample test cases below
for the required outputformat.
Note: You may use sqrt(n) defined in the header
integer n.
3
Sample test case 1.1
2 1
4 10 1 14 -2 1 3 0 4
Puppy 2 too far away
Total 1 puppy too far away
Sample test case 1.2
2 1
4 15 15 14 -2 1 3 0 4
Puppy 1 and Puppy 2 too far away
Total 2 puppies too far away
Sample test case 1.3
2 1
4 15 15 14 -2 16 16 0 4
Puppy 1 and Puppy 2 and Puppy 3 too far away
Total 3 puppies too far away
Sample test case 1.4
2 1
0
No puppies too far away
Sample test case 1.5
0 0
2 5 1 6 1
No puppies too far away
Task 2 Exponential Calculation
(15 points)
Write a C++ program which takestwo user input integers x (0 ≤� ≤ 30) and n, and calculate
an estimation of �# using theformula:
�# = 1 +
�
1!
+
�)
2!
+
�+
3!
+ ⋯�
.
�! , −∞ < � < ∞
where n in this question assumes the range from 0 to 100, �! = 1 × 2 × 3 × … ×� denote the
factorial of i.
Your program should output the estimations of �
#
as n increases. Specifically, your program
should
l Output the values of n and e on the subsequent lines as n increases. The values n
and e on each line are separated by a space. The value e is printed as a fixed
floating number with 8 decimal places.
l Use the double data type for floating point calculations.
4
Note:
l Check carefully your results against the same test outputs. Divisions
involving some large numbers can easily run into numerically inaccuracy issues
(you will learn more about this in the machine organization course).Try to
implement the given formula in different ways to testout.
l You may use setprecision(n) defined in the header
parameter of theoutput stream. Or you may use the C-style printfto format
your output if you like.
Sample test case 2.1
0 0
0 1.00000000
Sample test case 2.2
1 4
0 1.00000000
1 2.00000000
2 2.50000000
3 2.66666667
4 2.70833333
Sample test case 2.3
3 20
0 1.00000000
1 4.00000000
2 8.50000000
3 13.00000000
4 16.37500000
5 18.40000000
6 19.41250000
7 19.84642857
8 20.00915179
9 20.06339286
10 20.07966518
11 20.08410308
12 20.08521256
13 20.08546859
14 20.08552346
15 20.08553443
16 20.08553649
17 20.08553685
18 20.08553691
19 20.08553692
20 20.08553692
Task 3 Digits Permutations
(20 points)
5
Write a C++ program that will read one positive integer M supplied by the user, and your
program should output the number of all permutations of the digits, and the list of the
permutations in an increasing order. If given input is 123 then your program should print
an integer 6 with all 6 permutations in an increasing order e.g. 6 123 132 213 231 312 321
Note:
l If there are duplicated permutations, eliminate the duplicated one and only keep one
permutations. For example, 121, will have 3 permutations which are 112 121 211.
l If there are leading 0(s) in any permutation, eliminate the 0(s). For example, 120, will
have permutations which are 12 21 102 120 201 210
Sample test case 3.1
1
1 1
Sample test case 3.2
123
6 123 132 213 231 312 321
Sample test case 3.3
121
3 112 121 211
Sample test case 3.4
120
6 12 21 102 120 201 210
Sample test case 3.5
100
3 1 10 100
Task 4 Bounding Boxes
(20 points)
Write a C++ program to compute a minimum-sized axis-aligned bounding box (AABB) for a
set of input geometries. An AABB is a rectangle with sides parallel to the x-, y-axes which
encloses some given geometries. The input and output of your program are as follows:
Input. Each line of the user input begins with a character indicating the type of geometry,
followed by some parameters of thegeometric object. The input line can be one of the
followings:
l R x y width height
where R represents an input rectangle, x, y are floating-point numbers for the x-,
y-
6
coordinates of the rectangle center, width and height are floating-point numbers
for the rectangle size along the x- and y-axes, respectively.
l C x y radius
where C represents an input circle, x, y are floating-point numbers for the x-, ycoordinates of the circle center, and radius is a floating-point number for the radius of
the center
l P n x1 y1 x2 y2… xn yn
where P represents an input point set, n is an integer indicating the number of points
in the set, and xi, yi, i = 1, …, n, are floating point numbers for the x-, y-coordinates of
the n points
l #
indicates end of input
Output. A single line
x y width height
where x and y are floating-point numbers for the x-, y-coordinates of the center of the
minimum-sized AABB, width and height are floating-point numbers giving the sizes
of the AABB along the x-, y-axes, respectively.
Use the double data type for floating point calculations
Note: The questions assume no bound for the floating-point parameters (x, y, width,
height, radius) of the input geometries and therefore they can be any values that a
double data type can hold. You may use std::numeric_limits
std::numeric_limits
the smallest and the largest possible values, respectively, for the double data type.
Sample test case 4.1
R 0 0 3 2
#
0 0 3 2
Sampletest case 4.2
C -0.5 3.2 1.6
#
-0.5 3.2 3.2 3.2
Sampletest case 4.3
P 2 3 -2 -1 4
#
1 1 4 6
Sample test case 4.4
P 3 -1.5 3 3 3 5 3
#
1.75 3 6.5 0
Sample test case 4.6
P 2 3 -2 -1 4
C -0.5 3.2 1.6
P 3 -1.5 3 3 3 5 3
R 0 0 3 2
#
1.45 1.4 7.1 6.8
7
Task 5 One-shot Stock Trader
(10 points)
Suppose you are a Stock Trader. Given an array of daily Stock Price, you are supposed to
make at most one transaction (firstly buy one and then sell one share of stock) so that you
can find the maximum profit.
Input: A list of Integers which are the daily Stock Prices
Output: The maximum profit you can gain (Integer).
Sample test case 5.1 (Note: there is no output in this test case)
1 2 3 4 5
4
Sample test case 5.2
5 4 3 2 1
0
Sample test case 5.3
9 8 7 6 2 3 4 3 2 7 8
6
Task 6 Multi-shots Stock Trader
(20 points)
Suppose you are a Stock Trader. Given an array of daily Stock Price, you are supposed to
make as many as you like transactions (firstly buy one and then sell one share of stock) so
that you can find the maximum profit. Note that a new transaction must be made before the
previous transaction ends (i.e. you can only hold at most one share of stock all the time).
Input: A list of Integers which is the daily Stock Prices
Output: The maximum profit you can gain (Integer)
Sample test case 5.1 (Note: there is no output in this test case)
1 2 3 4 5
4
Sample test case 5.2
5 4 3 2 1
0
Sample test case 5.3
9 8 7 6 2 3 4 3 2 7 8
8
8
