[SOLVED] Csc3100  programming assignment 3 1 tree (40% of this assignment)1.1 description warrior has two important attributes, magic point(mp) and health point(hp).

1.1 Description
Warrior has two important attributes, magic point(MP) and health point(HP). These two values
are determined by the warrior at the beginning.

The magic city can be regarded as an undirected simple connected tree (data structure) with n nodes
and m edges. the warrior will walk in the city, from any starting leaf node to destination t which is
the root node. Every time the warrior passes an edge, the magic point of the warrior will be reduced
by 1. At the same time, there is a monster with attack power on each edge, and the warrior will fight
with it. If the magic point of the warrior before passing this edge is k, and the attack power of the
monster on this edge is w, then the battle when passing this edge will consume max(0, w − k) healthy
points.

The warrior wants to ensure that his magic point and health point are both zero when reaching node
t at this time. Please find the minimum health point that the warrior needs at any beginning nodes.
For example, let’s take n = 2, m = 1, and t = 1, there is only one edge (1, 2) with a monster whose
attack power is 9. The warrior needs at least 8 healthy points as the warrior will spend 8 = max(0, 9−1)
healthy points to cross this edge.

Input
1 2 1
1 2 9
Output
8
Figure 1: Example.
4
1.2 Input
• The first line has three integers n, m, t where n and m present the number of nodes and edges
respectively.
• The next m lines, each with three integers u, v, w, means there is an edge between the nodes u
and v, and the attack power of the monster on the edge is w.(u and v = 1, 2, …, n)
1.3 Output
• The minimum health point that the warrior needs at the beginning.
Sample Input 1
8 7 1
1 2 5
2 3 5
3 4 5
4 5 5
5 6 5
6 7 5
7 8 5
Sample Output 1

You can build a new tree and find the minimal health point that the warrior needs at the leaf node.
Figure 2: The new tree of Sample 1
Sample Input 2
8 7 1
1 2 5
2 3 1
2 4 7
1 5 4
5 6 1
6 7 2
5 8 3
Sample Output 2

Same with Sample 1, the maximal minimal health point is 8 at leaf node 4.
Sample Input 3
See attached q1sample . in
Sample Output 3
See attached q1sample . out
Problem Scale & Subtasks
• t = 1, m = n − 1, and 0 ≤ w
Test Case No. Constraints
1-4 2 ≤ n < 10
5-8 10 ≤ n < 100
9-10 100 ≤ n ≤ 1000
5
Figure 3: The new tree of Sample 2

2.1 Description
You are an outstanding employee of a supermarket. There are n items in the supermarket, each with
a unique ID; there are also k shelves, which form a ring by connecting the first and last shelf.
Your bag has a limited capacity, and you can only take a series of items whose total number is smaller
or equal to bag size.
Let’s take n=6, k=4, bag size=3 for example.

Then ’n=6’ means there are 6 pieces of items in total,
’k=4’ stands for that there are 4 shelves in total and the selves’ ids are 0, 1, 2, 3 respectively.
The four shelves are placed in a ring, such that shelf 0 is placed is right in front of shelf 1
and right behind shelf 3.

Your bag has the size of 3, so you can take things whose whole number is smaller or equal to
3.
The supermarket categorizes items using a hashing method: each item’s ID determines its assigned
shelf number, calculated by id%k. The shelves are numbered from 0 to k − 1, and on each shelf the
items are placed in descending order of their IDs, from front to back.
6 4 3
15 23.6
23 3.6
198 4.2
7 5.3
9 15.6
1453 31.1

Here ,you can record them in tuples (shelf num, id, value), and you will get the following
tuples:
(3, 15, 23.6), (3, 23, 3.6), (2, 198, 4.2), (3, 7, 5.3), (1, 9, 15.6), (1, 1453, 31.1)
After the hashing function and the sorting procedure, the final result is shown on the upper right, we can find out which shelf each item belongs to.

Today, your boss is in a great mood and has given you the opportunity to take any continuous
sequence of items from the shelves for free. However, there are two important restrictions:
• You are only allowed to take thing continously, and the continuous sequence of items whose
total number must be smaller or equal to bag size.

Here you are not allowed to take (1,9,15.6), (1,1453,31.1) and (3,15,23.6) simultaneously.
• You cannot take an equal number of items from any two shelves. The number of items taken
from each shelf must be different.
Here you are not allowed to take (1,9,15.6), (2, 198, 4.2) and (3,23,3.6) simultaneously,
because that is illegal.

• If there exists one and only one empty shelf between any two shelves with goods, we can skip
it and consider the goods between the two non-empty shelves to be continuous; but if there are
multiple continuous empty shelves between any two shelves with goods, we cannot connect them
and consider them to be disconnected.

Here, since there is nothing on shelf 0, we can ignore the shelf 0 and assume that (3, 7,
5.3) and (1, 1453, 31.1) are items placed next to each other and can be taken together.
One optimal solution is taking 2 items from the third shelf and 1 item from the first
shelf, yielding 23.6 + 5.3 + 31.1 = 60.0.
In normal cases, what is the maximum total value of the items you can take for free? Please try to
write a code to solve it.

2.2 Input
The first line contains three integers: n, k (the base for the hash operation), bag size (representing the
total number of items you can take). In the next n lines, each line contains two values:
• id[i] (a positive integer where 1 ≤ i ≤ n),
• value[i] (the value of item i, a positive floating-point number where 1 ≤ i ≤ n).

2.3 Output
Output the maximum sum of values in a subinterval of size bag size, rounded to one decimal place,
ensuring that the number of items taken from each shelf is unequal.
7
Sample Input 1
6 4 2
15 3.6
23 93.6
198 4.2
7 5.3
9 15.6
1453 41.1
Sample Output 1
97.2
Sample Input 2
9 6 5
3289 6652.7
7803 3590.7
659 5622.2
1542 7875.3
4563 3198.4
8757 2979.0
7777 8263.7
1068 387.7
7134 4324.3
Sample Output 2
27503.7
Sample Input 3
See attached q2sample . in
Sample Output 3
See attached q2sample . out
2.4 Problem Scale & Subtasks
Hint: bag size might be larger than n, k.
k> 0, id > 0, value > 0
Test Case No. Constraints
1-3 0 < n ≤ 10
4-5 0 < n ≤ 100
6-7 0 < n ≤ 1000
8-10 0 < n ≤ 5000
11-12 0 < n ≤ 100000, bag size = 1