1. Homepage
2. Programming
3. CSC3100 Data Structures Fall 2022 Programming Assignment II: Special Shortest Path, Median Search Tree, Football Match and Prefix

# CSC3100 Data Structures Fall 2022 Programming Assignment II: Special Shortest Path, Median Search Tree, Football Match and Prefix

Hong KongCUHKCSC3100Data StructuresSpecial Shortest Path Median Search Tree Football Match and PrefixJava

CSC3100 Data Structures Fall 2022 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.

2 Problem 2: Median Search Tree 2.1 Statement

If the sorted array of all the values in the set is {ai}ni=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.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.

4 Problem 4: Prefix 4.1 Statement

You are given n strings s1, s2, · · · , sn and q queries. In ith 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 ith line contains the answer of ith query. 4.4 Sample Input/Output

4.5 Constraints

All strings only contain lowercase letters.

Since the input might be very large, fast input method such as BufferedReader in Java is required.

A. Requirements

Code (90%)

The distribution of programming grade is 20%, 20%, 25%, 25% for the four problems respectively.

You can write your code in Java, Python, C, or C++. The time limit may vary among different languages, depending on the performance of the language. Your code must be a complete runnable program instead of only a function. We guarantee test data strictly compliance with the requirements in the description, and you do not need to deal with cases where the input data is invalid.

We provide a example problem to better illustrate the information above.

Report (10%)

You also need to write a report to explain the following: What are the possible solutions for the problem? How do you solve this problem?
Why is your solution better than others?

Please note that the maximum number of pages allowed for your report is 5 pages.

Remember that the report is to illustrate your thinking process. Keep in mind that your report is supposed to show your ideas and thinking process. We expect clear and precise textual descriptions in your report, and we do not recommend that you over-format your report.

B. Example Problem: A + B Problem Description

Given 2 integers A and B, compute and print A + B

Input

Two integers in one line: A, and B

Output

One integer: A + B

Sample Input I Sample Output I

123

Problem Scale & Subtasks

For 100% of the test cases, 0 A,B 106

Solutions

Java

import java.util.*;

public class Example {
public static void main(String[] args) {

int a, b;
Scanner scanner = new Scanner(System.in); a = scanner.nextInt();
b = scanner.nextInt();
scanner.close();
System.out.println(a + b);

} }

Python

AB = input (). split ()

A, B = int(AB[0]), print(A + B)

C

#include <stdio.h>

int main(int argc, {

int(AB[1])

char *argv[])

int A, B; scanf("%d%d", &A, &B); printf("%d\n", A + B); return 0;

}

C++

#include <iostream >

int main(int argc, char *argv[]) {

int A, B;
std::cin>> A >> B;
std::cout<< A + B << std::endl; return 0;

}

## Get Expert Help On This Assignment

#### Scan above qrcode with Wechat

Hong Kong代写,CUHK代写,CSC3100代写,Data Structures代写,Special Shortest Path代写, Median Search Tree代写, Football Match and Prefix代写,Java代写,Hong Kong代编,CUHK代编,CSC3100代编,Data Structures代编,Special Shortest Path代编, Median Search Tree代编, Football Match and Prefix代编,Java代编,Hong Kong代考,CUHK代考,CSC3100代考,Data Structures代考,Special Shortest Path代考, Median Search Tree代考, Football Match and Prefix代考,Java代考,Hong Konghelp,CUHKhelp,CSC3100help,Data Structureshelp,Special Shortest Pathhelp, Median Search Treehelp, Football Match and Prefixhelp,Javahelp,Hong Kong作业代写,CUHK作业代写,CSC3100作业代写,Data Structures作业代写,Special Shortest Path作业代写, Median Search Tree作业代写, Football Match and Prefix作业代写,Java作业代写,Hong Kong编程代写,CUHK编程代写,CSC3100编程代写,Data Structures编程代写,Special Shortest Path编程代写, Median Search Tree编程代写, Football Match and Prefix编程代写,Java编程代写,Hong Kongprogramming help,CUHKprogramming help,CSC3100programming help,Data Structuresprogramming help,Special Shortest Pathprogramming help, Median Search Treeprogramming help, Football Match and Prefixprogramming help,Javaprogramming help,Hong Kongassignment help,CUHKassignment help,CSC3100assignment help,Data Structuresassignment help,Special Shortest Pathassignment help, Median Search Treeassignment help, Football Match and Prefixassignment help,Javaassignment help,Hong Kongsolution,CUHKsolution,CSC3100solution,Data Structuressolution,Special Shortest Pathsolution, Median Search Treesolution, Football Match and Prefixsolution,Javasolution,