A. RequirementsCode (90%)You can write your code in Java, Python, C, or C++. The time limit may vary among differentlanguages, depending on the performance of the language. Your code must be a complete excutableprogram instead of only a function. We guarantee test data strictly compliance with the requirementsin the description, and you do not need to deal with cases where the input data is invalid.Libraries in this assignment:• For C/C++, you can only include standard library.• For Java, you can only import java.util.*• For Python, you can only import standard library. In other words, you cannot import librariessuch as numpy.We provide an example problem to illustrate the information above better.Report (10%)You also need to write a report in pdf type 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 issupposed to show your ideas and thinking process. We expect clear and precise textual descriptionsin your report, and we do not recommend that you over-format your report.B. Example Problem: A + B ProblemDescriptionGiven 2 integers A and B, compute and print A + BInputTwo integers in one line: A, and BOutputOne integer: A + BSample Input 11 2Sample Output 13Problem Scale & SubtasksFor 100% of the test cases, 0 ≤ A, B ≤ 1061SolutionsJavaimport 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 );}}PythonAB = input (). split ()A , B = int ( AB [0]) , int ( AB [1])print (A + B )C# include < stdio .h >int main ( int argc , 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;}C. SubmissionAfter finishing this assignment, you are required to submit your code to the Online Judge System(OJ), and upload your .zip package of your code files and report to BlackBoard.C.1 Online JudgeOnce you have completed one problem, you can submit your code on the page on the Online Judgeplatform (oj.cuhk.edu.cn, campus only) to gain marks for the code part. You can submit yoursolution of one problem for no more than 80 times.After you have submitted your program, OJ will test your program on all test cases and give you agrade. The grade of your latest submission will be regarded as the final grade of the correspondingproblem. Each problem is tested on multiple test cases of different difficulty. You will get a part ofthe score even if your algorithm is not the best.2Note: The program running time may vary on different machines. Please refer to the result ofthe online judge system. OJ will show the time and memory limits for different languages on thecorresponding problem page.If you have other questions about the online judge system, please refer to OJ wiki (campus networkonly). If this cannot help you, feel free to contact us.C.2 BlackBoardYou are required to upload your source codes and report to the BlackBoard platform. You needto name your files according to the following rules and compress them into A1_<Student ID>.zip :A1_ < Student ID >. zip|-- A1_P1_ < Student ID >. java / py /c/ cpp|-- A1_P2_ < Student ID >. java / py /c/ cpp|-- A1_Report_ < Student ID >. pdfFor Java users, you don’t need to consider the consistency of class name and file name.For example, suppose your ID is 123456789, and your problem 1 is written in Python, problem 2 iswritten in Java then the following contents should be included in your submitted A1_123456789.zip:A1_123456789 . zip|-- A1_P1_123456789 . py|-- A1_P2_123456789 . java|-- A1_Report_123456789 . pdfC.3 Late SubmissionsSubmissions after Feb 7 2024 23:59:00(UTC+8) would be considered as LATE.The LATE submission page will open after deadline on OJ.Submisson time = max{latest submisson time for every problem, BlackBoard submisson time}There will be penalties for late submission:• 0–24 hours after deadline: final score = your score×0.8• 24–72 hours after deadline: final score = your score×0.5• 72+ hours after deadline: final score = your score×0FAQsQ: I cannot access to Online Judge.A: First, please ensure that you are using the campus network. If you are not on campus, please usethe university VPN. Second, please delete cookies and refresh browser or use other browser. If youstill cannot access to Online Judge, try to visit it via the IP address 10.26.200.13.Q: My program passes samples on my computer, but not get AC on OJ.A: Refer to OJ Wiki Q&AAuthorsIf you have questions for the problems below, please contact:• Problem 1. Yingli Zhou: yinglizhou@link.cuhk.edu.cn Yuyang Xia: yuyangxia@link.cuhk.edu.cn• Problem 2. Yingli Zhou: yinglizhou@link.cuhk.edu.cn Yuyang Xia: yuyangxia@link.cuhk.edu.cn3CSC3100 Data Structures Spring 2024Programming Assignment 1Due: Feb 7 2024 23:59:00Assignment Link: http://oj.cuhk.edu.cn/contest/csc310024spa1Access code: WaaaghQuestion1 weighs 40% and question2 weighs 50%.We extend the time limitation for Python from 1 second to 2 seconds.1 Let us sort (40% of this assignment)1.1 DescriptionLittle X has a list A and a factor k. There are n positive integers in A. Little X wants to constructsome 2D points (xi, yi) by assigning xi = ⌊aik⌋ and yi = ai%k, and he wants to sort these points inseveral methods.Method one, sort all points by the x-coordinates from smallest to largest, and for those with the samex-coordinate, sort by the y-coordinates from smallest to largest.Method two, sort all points by the x-coordinates from largest to smallest, and for those with the samex-coordinate, sort by the y-coordinates from smallest to largest.Method three,sort all points by the x-coordinates from smallest to largest, and for those with the samex-coordinate, sort by the y-coordinates from largest to smallest.Method four, sort all points by the x-coordinates from largest to smallest, and for those with the samex-coordinate, sort by the y-coordinates from largest to smallest.1.2 InputEach test contains multiple test cases. The first line contains a single integer T(1 ≤ T ≤ 10) thenumber of test cases. The description of the test cases follows.The first line of each test case contains three integers n, k, id(1 ≤ n, k ≤ 105, 1 ≤ id ≤ 4), separatingby one space, where n represents the length of the list and id represents the method Little X hopesyou to use.The second line of each test case will be the list A (1 ≤ ai ≤ 109).The sum of n over all test cases in one test won’t exceed 5 × 105.1.3 OutputFor each test case, output n lines, the ith line containing two integers xi, yi, separating by one space,indicating the coordinate of the ith point of the constructed list sorted according to the given order.The output of each test case is separated by one empty line.4Sample Input 142 65 17917 12921 41 160982 57 17920 40923 3 18596 1849 5806Sample Output 119 57121 52148 3071 45138 54616 11935 12865 1There are four test cases in the example test, the first test case’s converted points list is [(121, 52),(19, 57)]and Little X wants us to sort it according to the first method.So the resulting list of the first test case is [(19, 57),(121, 52)]. The processes of the other test casesare similar.You can find more samples in the attached file on BB.Problem Scale & SubtasksThere are 5 tests in total, with the same weight.Test Case No. Constraints1 1 ≤ n ≤ 5, id = 1.2 1 ≤ n ≤ 100, 1 ≤ k ≤ 105, 1 ≤ id ≤ 23 1 ≤ n ≤ 1000, 1 ≤ k ≤ 105, 1 ≤ id ≤ 44 1 ≤ n ≤ 104, 1 ≤ k ≤ 105, 1 ≤ id ≤ 45 1 ≤ n ≤ 105, 1 ≤ k ≤ 105, 1 ≤ id ≤ 4HintTry to define the relationship between the points by the requirement.2 Detecting Tyranids (50% of this assignment)2.1 DescriptionThere is a galaxy map with n × m grids in it, and there are p Tyranid squads, each squad has kTyranids and is located in grid (i, j).Suppose each grid (i, j) contains ki,j Tyranids. Now, as a commander of Space Marine, you want toknow the expected number of Tyranids in any rectangle on the map.Formally speaking, you want to know the result of the following expression given the information of pTyranid squads.nXa=1mXb=1nXc=amXd=bcXi=adXj=bki,jNote this number may be very large, you only need to output the remainder of the result mod998244353.52.2 InputThe first line contains 3 integers n, m, and p(1 ≤ n, m, p ≤ 105).For the following p lines, each line contains 3 integers i(1 ≤ i ≤ n), j(1 ≤ j ≤ m), and k(1 ≤ k ≤ 109).2.3 OutputOne line contains one integer representing the remainder of the result mod 998244353.Sample Input 14 3 12 1 1Sample Output 118For the first example, there is only one non-zero ki,j , k2,1 = 1.Note that for n = 4, m = 3, there are 18 rectangles containing the grid (2, 1).Figure 1: explanation of example 1The orange portion has 6 grids and the blue area has 3, while 18 = 6 × 3.Sample Input 25 5 53 4 24 5 64 4 22 3 13 4 3Sample Output 2800For the second example, we can list every non-zero ki,j .k2,3 = 1, k3,4 = 5, k4,4 = 2, k4,5 = 6. Then the target expression has a result of 800.You can find more samples in the attached file on BB.Problem Scale & SubtasksThere are 10 tests in total, with the same weight.Test Case No. Constraints1-3 1 ≤ n, m, p ≤ 10, 1 ≤ k ≤ 104-6 1 ≤ n, m, p ≤ 100, 1 ≤ k ≤ 1007 1 ≤ n, m, p ≤ 105, k = 18-10 1 ≤ n, m, p ≤ 105, 1 ≤ k ≤ 1096HintFor C/C++ and Java users, an int type stores integers range from -2,147,483,648 to 2,147,483,647. Itmay be too small for this problem. You need other data types, such as long long for C/C++ and longfor Java. They store integers ranging from -9,223,372,036,854,775,808 to 9,223,372,036,854,775,807.Use scanf("%lld",&n) for C, cin>>n for C++ and n = scanner.nextLong() for Java to get theinput n. And the other operations for long and long long are quite same as int.Consider the number of grids containing one Tyranid, then consider how to combine all these numbers.Remember to take modular after doing any arithmetic operations.For instance, make sure for any a = b + c, you write it as a = (b + c) mod 998244353.2.4 ExtensionWhat if we want to calculate the variance?7