COP 3502h Assignment 4 Board Meeting

$30.00

Category: You will Instantly receive a download link for .zip solution file upon Payment

Description

5/5 - (2 votes)

Your teacher is demonstrating his students’ Martial Arts capabilities by breaking boards at the
local mall. He wants the demonstration to be interesting, but he has a limited number of boards.
Each board can be represented as a rectangle with an integral width and height. When broken it
requires some amount of effort, and will become two new boards. The board will always break
along the length of the board. Each break will be a straight line parallel to one side of the board.
The break will occur at an integral distance from the parallel side and as close to the center as
possible.
As an example, a board of length 7 and height 2 will break into two, one of length 4 and height 2
and the other of length 3 and height 2. Additionally a board of length 4 and height 18, will break
into two boards for length 2 and height 18.
Your teacher will initially have each board he has brought held by an audience member. Each
audience member will form their own line. When a board is broken the board holder and the
student that the broke the board each pick up a part and go back into line the board came from.
Only the board at the front of their respective line can be broken.
The teacher wants the audience members to get a lot of action, so instead of going to the back
of the line these new board holders will go to the front, where the original board holder will be
the first in line and the board breaker will be second. The resulting front most board holder will
always have the board piece that has the largest surface area (i.e. 𝐿 Γ— 𝐻 is maximized). If a
board is ever non-breakable (i.e. 1 Γ— 𝐻), then the board holder will leave the line and watch the
demonstration from the sidelines.
Each student is different and has a limit to the amount of effort they can expend when breaking a
board. These students will also line up.
When given the signal the first student in line tries to break a board. When a student tries to
break a board they go to the line where the first board in the line has the highest effort board,
which the student can break. If no such line exists, the student goes to the end of the student line.
If multiple line options have the same effort the student will go into the first one by index.
If no student in line can break a board, the demonstration ends. Additionally, if no boards are left
to break, the demonstration ends.
The effort (𝐸) it takes to break a board with length, 𝐿, and height, 𝐻, is the following,
𝐸(𝐿, 𝐻) = max(1, 2 Γ— 𝐻 βˆ’ 𝐿)
Your teacher wants to know both the sum of the effort the students will expend, the total number
of boards left, and the number of students that do not break any boards. Your teacher will fiddle
with the order of students and the boards brought to make the demonstration as cool as possible,
so you should design your program such that it can handle a variety of test cases.
Input specification
Input will begin with 2 positive integers, 𝒃 and 𝒔 (𝒃 Γ— 𝒔 ≀ 100,000), representing the number of
boards and the number of students respectively. The next 𝒃 lines contains a single pair of spaceseparated, positive integers, 𝒍 and 𝒉 (2 ≀ 𝒍, 𝒉 ≀ 100,000,000), representing the length and
height of the board brought by your teacher. The earlier the board occurs in input the smaller the
index of its line. The last line contains 𝒔 space-separated, positive integers, π’‚πŸ, π’‚πŸ, … , 𝒂𝒔
, where
π’‚π’Š
(π’‚π’Š ≀ 100,000,000) represents the maximum board breaking effort for the π’Š-th student in
line.
Output Specification
Output should contain 3 integers on their own line, 𝐸, 𝐡, and 𝑆, representing the sum of the
effort, the number of remaining boards, and the number of students that did not break a board
respectively.
Input Output Example
Input Output
3 7
10 5
3 9
5 5
8 6 10 10 3 2 10
29
3
2
2 3
5 5
3 5
5 8 7
19
3
0
1 1
2 2
1
0
1
1
Explanation
Case 1
The effort for the first three boards are the following
ο‚· The effort to break 10 by 5 is either (2 x 5 – 10) = 0 or 1. Therefore, 1 is the effort to
break the 10 by 5 board.
ο‚· The effort to break 3 by 9 is either (2 x 9 – 3) = 15 or 1. Therefore, 15 is the effort to
break the 3 by 9 board.
ο‚· The effort to break 5 by 5 is either (2 x 5 – 5) = 5 or 1. Therefore, 5 is the effort to break
the 5 by 5 board.
1
st Student (skill of 8)
The initial board set up looks like the following
110×5
1 23×9
55×5
The 5 board is broken by the student, because it is the highest effort board they can break
110×5
1 23×9 82×5 73×5
When broken we get two boards a 2 by 5 and a 3 by 5. The efforts are 2 x 5 – 2 and 2 x 5 – 3.
The 2 by 5 will be behind the 3 by 5 board which will be the start of the line for the given
example.
110×5
1 23×9
73×5
82×5
2
nd Student (skill of 6)
The second student will break the 10 by 5 board in the first line.
55×5
1 23×9
73×5
82×5 55×5
Since the boards are the same the order does not really matter
55×5
1 23×9
73×5
55×5 82×5
3
rd Student (skill of 10)
The third student will break the 7 effort 3 by 5 board at the front of the third line
55×5
1 23×9
55×5 82×5 82×5
Part of the broken board will be tossed since it’s length be comes 1. The remaining piece can be
reused and will go on the top of the stack.
55×5
1 23×9
55×5 82×5
82×5
4
th Student (skill of 10)
The fourth student will break the 8 effort 2 by 5 board at the front of the third line. Both pieces
are unusable and will be tossed.
55×5
1 23×9
55×5 82×5
Resulting in the following
55×5
1 23×9
55×5 82×5
The 5th and 6th student (skill of 3 and 2)
The next two students cannot break anything. They will go to the end of the line hoping that the
7
th student will allow for easier boards.
The 8th student (skill of 10)
The 8th student will break the hardest board he can, the 8 effort 2 by 5 board in the third line.
This board when broken will have both pieces discarded.
55×5
1 23×9
55×5
Resulting in the following board setup,
55×5
1 23×9
55×5
The remaining students cannot break any boards, so the demonstration ends.
The total effort was 5 + 1 + 7 + 8 + 8, which totals to 29. There was 3 boards left and 2 students
that did not break anything.
Case 2
There are only two boards the first board is a 5 by 5 which has an effort of 5 to break. The
second board is a 3 by 5 which has an effort of 7 to break.
The first student has a skill of 5 so he can break the first board. This break creates two usable
boards. The board that will be at the front of the line will be a 3 by 5 and has an effort of 7 to
break. The other board behind this first one will be a 2 by 5 and has an effort of 8 to break.
The next student has a skill of 8 and can break either board, both have an effort of 7. They
choose the board with the lowest line index (the first line). After breaking this board there are
now two 2 by 5 board with effort 8 in the first line and one board with effort 7 in the second line.
The other board had a length of 1 and was subsequently tossed.
The last student has a skill of 7, which allows them to break the board in line 2. This break
creates another 2 by 5 board with effort 8 in the second line. Another board with length of 1 is
tossed.
All three students have gone, so the demonstration ends. The students expended 5 + 7 + 7 = 19
effort, which is one less than the maximum they could have achieved given these boards. There
are 3 boards and 0 students left in this demonstration.
Case 3
The only board has an effort of 2 x 2 – 2 = 2, but the only student cannot break any boards harder
than 1, so no boards are broken. We have 0 effort, 1 board and 1 student left.
Grading Information
Read/write in from standard input/output – 5 points
Comments, variable names, whitespace usage – 15 points
Use an array (or some listing) of stack to represent the board lines – 10 points
Use a queue to represent the student line– 10 points
Use some simulation to determine the ultimate outcomes – 10 points
Your program will be tested on 25 test cases – 2 points each
No points will be awarded to programs that do not compile.
Solutions without linked lists based stacks/queues will receive a maximum of 50 points