编程代写|CSC3100 Data Structures Fall 2022 Programming Assignment II

这是一篇关于数据结构的Programming Assignment II编程代写

 

1 Problem 1: Special Shortest Path

1.1 Statement

City C consists of n nodes, representing different places. There are m edges between these nodes. For the edge ei = (ui , vi , wi), there is a bidirectional(undirected) trail connecting ui and vi with length of wi .

For a path P = {pi}, consisting of edges p1, p2, p3, · · · , pk, the length of each edge is li = wpi . Normally,passing the edge pi with length li will cost li units of energy. Specially, if li = K · li1, then passing this edge will only cost (K 1) · li1 units of energy.

Alice is starting from the node 1. Alice wants to know how many units of energy it will take at least to visit the node x, for any x. If x is unreachable from the start point(node 1), you should output 1 as the result.

1.2 Input Format

The first line consists of three integer numbers n, m, K. The following m lines each consists of three integer numbers u, v, w to describe a bidirectional trail.

1.3 Output Format

You need to output a line consisting of n integers, each representing the minimum units of energy to reach node i from node 1.

1.4 Example

Input 1 Output 1

4 3 0 0 2 5 -1

1 2 2

2 3 4

3 1 5

Input 2 Output 2

3 3 2 0 2 4

1 2 2

2 3 4

3 1 5

1.5 Constraints

Case Score Constraints

1 3 30 pts n 105 m 2 × 105 K = 0

1 wi 104 4 5 20 pts n 103 m 2 × 105 K = 1

6 7 20 pts n 105 m 2 × 105 K = 2

8 10 30 pts n 105 m 2 × 105 K 105

1.6 Hints

  • Hint: You can modify(or add) some edges to the original graph to fit this problem into the algorithm you know.

2 Problem 2: Median Search Tree

2.1 Statement

If the sorted array of all the values in the set is {ai} i=1, let t = n/2, then the median 2k values are {atk+1, · · · , at+k}.

Barbara has got a set of values with size of 2k initially. Barbara wants to do m operations on it. Each operation belongs to the following 3 types:

  • 1 w: insert a value w.
  • 2: output all the median 2k values, i.e. atk+p, 1 p 2k.
  • 3 p: delete the p-th value among median 2k values, i.e. atk+p.

We guarantee that all the values will be distinct and the size of the set is always at least 2k.

2.2 Input Format

The first line consists of two integer numbers m, k. The second line consists of the 2k values in the initial set. Then, the following m lines each consists of the command of an operation.

2.3 Output Format

You need to output one line for each query(operation 2). Each line consists of 2k positive integers, the median 2k values of the set at that time in ascending order.

2.4 Example

Input 1 Output 1

3 1 2 4

2 3

1 4

3 1

2

Input 2 Output 2

5 2 2 4 6 8

8 4 2 6 4 5 6 8

2 3 4 5 6

1 5

2

1 3

2

2.5 Constraints

Case Score Constraints

1 3 30 pts n 2 × 103 k 25 1 w 106

4 5 20 pts n 105 k 25 no operation 3

6 7 20 pts n 105 k = 1

8 10 30 pts n 105 k 25

2.6 Hints

You can solve this problem with heaps.

3 Problem 3: Football Match

3.1 Statement

While the FIFA World Cup is being held in Qatar, BLGG is organizing a football tournament in LGU,too.

There are n teams in this tournament, numbered from 1 to n. Each team has its popularity, and the popularity of team i is ai . A match between i and j will gain ai × aj MOD M attractions.

When a football team loses a match, it will be eliminated from the tournament. At the end, the team left standing will be the champion of this tournament.

BLGG is wondering that what the maximum sum of the attractions of the (n 1) matches.

3.2 Input Format

The first line contains two integers n and M.

The second line contains n integers a1, · · · , an.

3.3 Output Format

Output one integer representing the maximum sum of the attractions of the (n 1) matches.

3.4 Sample Input/Output

Input 1 Output 1

3 114514 9

1 2 3

3.5 Constraints

Case Score Constraints

1 10 pts n 10 0 ai , M 2 × 109 For all i, j, ai × aj < M

2 5 40 pts n 10 0 ai , M 2 × 109

6 10 pts n 2000 0 ai , M 2 × 109 For all i, j, ai × aj < M

7 10 40 pts n 2000 0 ai , M 2 × 109

3.6 Hints

You can try to solve this problem using the graph algorithms we learn in classes.

4 Problem 4: Prefix

4.1 Statement

You are given n strings s1, s2, · · · , sn and q queries. In i th query, you are given a string ti , please find out how many strings in s1, s2, · · · , sn begins with ti .

4.2 Input Format

The first line is an integer n.

Each of the next n lines contains a string, respectively. The (i + 1)th line of input is si .

The (n + 2)th line of input is an integer q.

Each of the next q lines contains a string, respectively. The (n + 2 + i) th line of input is ti .

4.3 Output Format

Output q lines. The i th line contains the answer of i th query.