CSC3100 Data Structures Fall 2023 Programming Assignment 2: Battle Game, Buried Treasure
CSC3100 Data Structures Fall 2023 Programming Assignment 2
Due: Nov 8 2023 23:59:00
Assignment Link: http://oj.cuhk.edu.cn/contest/csc310023falla2 Access Code: 7d2x0Zs8
1 Battle Game (40% of this assignment) 1.1 Description
Imagine a group of n players that are located in different floors. The i-th player (for each i such that 1 ≤ i ≤ n, where i is an integer) is characterized by the following:
• pi, a unique starting floor level
• hi, a starting HP (Health Points) value
• di, a direction of movement, either U indicating that the i-th player is going upward or D indicating that the i-th player is going downward
All players move simultaneously at the same speed in their respective directions. When two players meet, they engage in a battle. The player with the lower health is eliminated instantaneously, while the other continue to move in the same direction at the same speed but with a reduced HP by 1. In a case where two players have identical HP, they are both eliminated simultaneously after the battle.
Your task is to determine the final HP of the surviving players.
1.2 Input
The first line of input contains an integer n, representing the number of players.
The next n lines follow.
The i-th line contains three values: pi, hi, di - an integer representing the starting floor level for the i-th player, an integer representing the HP value for the i-th player, and a character representing the direction of movement for the i-th player.
1.3 Output
For each surviving player, output their remaining HP on a separate line, in the order of their input.
Sample Input 1
5 511U 415U 317U 277U 1 30 UThe following figures show the visual representations for both input samples in their initial positions, respectively.
Problem Scale & Subtasks
For 100% of the test cases:
• 1≤n≤106
• 1≤pi ≤108 (foreachisuchthat1≤i≤n)
• 1≤hi ≤100(foreachisuchthat1≤i≤n)
• di ∈{U,D}(foreachisuchthat1≤i≤n)
Test Case No. 1-4
5-8 9-10
2 Buried Treasure (50% of this assignment) 2.1 Description
Jack Sparrow, the legendary pirate of the Seven Seas, sets sail to an inhabited island in search of a buried treasure. Guided by his map, he believes the treasure lies within a weird-looking trench. The trench stretches across a width of n. For any given point from i − 1 to i on the trench’s x-coordinate, the depth is represented by di (for each i such that 1 ≤ i ≤ n, where i is an integer).
Jack is wondering about the size of the largest treasure that could possibly fit inside the trench. Wanting to maximize his haul, he turns to you, a trusted member of his crew, to make the calculations. By largest, Jack means the maximum area – the product of width and height – of the rectangular treasure chest that can be buried within the trench’s confines. For example, the following figure shows the largest possible treasure that can fit in a trench with n = 8 and d = [6, 2, 5, 4, 5, 1, 4, 4].
Could you give these calculations a look for our legendary pirate?
2.2 Input
The first line contains an integer T, representing the number of Jack Sparrow’s queries.
The descriptions of T queries follow.
Each query is described in the following format:
• The first line contains an integer n representing the width of the trench.
• The second line contains n integers separated by a space representing the depths of the trench.
2.3 Output
Output T lines. The j-th line contains the answer to the j-th query. Sample Input 1 Sample Output 1
Problem Scale & Subtasks
For 100% of the test cases: • 1 ≤ T ≤ 10
• 1≤n≤106
• 1≤di ≤106 (foreachisuchthat1≤i≤n)
• The sum of n over all queries, denoted as N, does not exceed 106 in each test case.
Test Case No. 1-2
3-4 5-8 9-10
Hint
Constraints
n ≤ 10
n ≤ 1 000
N ≤10000
No additional constraints
Hint 1: For C/C++ and Java users, an int type stores integers range from -2,147,483,648 to 2,147,483,647. It may be too small for this problem. You need other data types, such as long long for C/C++ and long for 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 output the answer query. And the other operations for long and long long are quite same as int.
Hint 2: Sailing through the vast expanse of the Seven Seas, Jack Sparrow found himself drawn to an intriguing map. Tantalized by the prospect of hidden riches, he anchored near a mysterious island with an unusual trench. As he examined the trench’s varying depths, he pondered the size of the treasure that might be buried within. Carefully, he sought the counsel of a trusted crew member to calculate the chest’s potential dimensions. Knowing the importance of this task, the crew member took to the challenge, hoping to maximize the treasure for their legendary captain.
