Question #2: Game Design You are creating a game where the hero, called Hercules, has to fight n angry and magical birds with multiple heads. The ith bird has birds[i] total number of heads. Assume it takes your hero 1 second to behead all heads of a specific bird, but after that magically this bird gets back half of its heads. If the bird had initially b heads, then after it is beheaded it grows floor(b/2) heads back. You have m seconds to cut as many heads as possible from the birds. a) Describe an efficient algorithm that finds the maximum number of heads cut by Hercules. Hint: start with the bird that has the maximum number of heads, etc. b) Write a java class that implements your algorithms (copy paste implementation). c) What is the data structure you used? Hint: Some options arrays, sorted arrays, linked lists, heaps etc. Choose the best. d) What is the running time of your algorithm? //given an array @birds of size n, and @m the available seconds return the //maximum number of head cut by the hero int maxStymphBirds(int[] birds, int m) Output A single integer, the maximum number of heads you can cut in m seconds. Example 1 n = 3 m = 3 birds = [20, 1, 15] output = 45
Question #2: Game Design You are creating a game where the hero, called Hercules, has to fight n angry and magical birds with multiple heads. The ith bird has birds[i] total number of heads. Assume it takes your hero 1 second to behead all heads of a specific bird, but after that magically this bird gets back half of its heads. If the bird had initially b heads, then after it is beheaded it grows floor(b/2) heads back. You have m seconds to cut as many heads as possible from the birds. a) Describe an efficient algorithm that finds the maximum number of heads cut by Hercules. Hint: start with the bird that has the maximum number of heads, etc. b) Write a java class that implements your algorithms (copy paste implementation). c) What is the data structure you used? Hint: Some options arrays, sorted arrays, linked lists, heaps etc. Choose the best. d) What is the running time of your algorithm? //given an array @birds of size n, and @m the available seconds return the //maximum number of head cut by the hero int maxStymphBirds(int[] birds, int m) Output A single integer, the maximum number of heads you can cut in m seconds. Example 1 n = 3 m = 3 birds = [20, 1, 15] output = 45
Computer Networking: A Top-Down Approach (7th Edition)
7th Edition
ISBN:9780133594140
Author:James Kurose, Keith Ross
Publisher:James Kurose, Keith Ross
Chapter1: Computer Networks And The Internet
Section: Chapter Questions
Problem R1RQ: What is the difference between a host and an end system? List several different types of end...
Related questions
Question
How would the given function be implemented based on the given prompt?
![Question #2: Game Design
You are creating a game where the hero, called Hercules, has to fight n angry
and magical birds with multiple heads. The ith bird has birds[i] total number of
heads.
Assume it takes your hero 1 second to behead all heads of a specific bird, but
after that magically this bird gets back half of its heads. If the bird had initially b
heads, then after it is beheaded it grows floor(b/2) heads back.
You have m seconds to cut as many heads as possible from the birds.
a) Describe an efficient algorithm that finds the maximum number of heads cut
by Hercules. Hint: start with the bird that has the maximum number of heads,
etc.
b) Write a java class that implements your algorithms (copy paste
implementation).
c) What is the data structure you used? Hint: Some options arrays, sorted
arrays, linked lists, heaps etc. Choose the best.
d) What is the running time of your algorithm?
//given an array @birds of size n, and @m the available seconds return the
//maximum number of head cut by the hero
int maxStymphBirds(int[] birds, int m)
Output
A single integer, the maximum number of heads you can cut in m seconds.
Example 1
n = 3
m = 3
birds = [20, 1, 15]
output = 45
The 1st second, cut 20 heads of the 1st bird, and it gets floor(20/2) = 10 heads
back.
The 2nd second, cut 15 heads of the 3rd bird, and it gets floor(15/2) = 7 heads
back.
The 3rd second, cuts 10 heads of the 1st bird again, and it gets floor(10/2) = 5.
In total 20 + 15 + 10 = 45 heads cut.](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F346b36e0-a4d8-47d7-8bd1-1ad776cb1cf3%2Fe9efef61-d8a0-4237-8e93-fa2cb6da25e3%2Fos0jk0b_processed.png&w=3840&q=75)
Transcribed Image Text:Question #2: Game Design
You are creating a game where the hero, called Hercules, has to fight n angry
and magical birds with multiple heads. The ith bird has birds[i] total number of
heads.
Assume it takes your hero 1 second to behead all heads of a specific bird, but
after that magically this bird gets back half of its heads. If the bird had initially b
heads, then after it is beheaded it grows floor(b/2) heads back.
You have m seconds to cut as many heads as possible from the birds.
a) Describe an efficient algorithm that finds the maximum number of heads cut
by Hercules. Hint: start with the bird that has the maximum number of heads,
etc.
b) Write a java class that implements your algorithms (copy paste
implementation).
c) What is the data structure you used? Hint: Some options arrays, sorted
arrays, linked lists, heaps etc. Choose the best.
d) What is the running time of your algorithm?
//given an array @birds of size n, and @m the available seconds return the
//maximum number of head cut by the hero
int maxStymphBirds(int[] birds, int m)
Output
A single integer, the maximum number of heads you can cut in m seconds.
Example 1
n = 3
m = 3
birds = [20, 1, 15]
output = 45
The 1st second, cut 20 heads of the 1st bird, and it gets floor(20/2) = 10 heads
back.
The 2nd second, cut 15 heads of the 3rd bird, and it gets floor(15/2) = 7 heads
back.
The 3rd second, cuts 10 heads of the 1st bird again, and it gets floor(10/2) = 5.
In total 20 + 15 + 10 = 45 heads cut.
![public class Main{
static int maxHeads (int[] birds, int m){
return 0;
}
}
Run | Debug
public static void main(String[] args) {
int arr1[] = {20, 1, 15);
int arr2[] = {2, 1, 7, 4, 2};
int arr3[] = {4, 10, 6, 7, 3, 1);
HI
System.out.println("Test 1, Total Heads 20 = + maxHeads (arr1, m: 1)); //m =1, bird 1 cut 20 heads, arr1 is now {10,1,15}
2, Total Heads 35 = " + maxHeads (arr1, m: 2)); //m=2, bird 3 cut 15 head, arr1 is now {10,1,7}
bird 1 cut 10 heads, arr1 is now (5,1, 7}
System.out.println("Test
System.out.println("Test
3, Total Heads 45 = " + maxHeads (arr1, m: 3)); //m=3,
System.out.println("Test
System.out.println("Test
System.out.println("Test 6, Total Heads 14 = " +
4, Total Heads 7 = " + maxHeads (arr2, m: 1)); //m=1
5, Total Heads 11 = " + maxHeads (arr2, m: 2)); //m=2
maxHeads (arr2, m: 3)); //m=3
System.out.println("Test 7, Total Heads 10 = " + maxHeads (arr3, m: 1)); //m=1||
System.out.println("Test 8, Total Heads 17 = " + maxHeads (arr3, m: 2)); //m=2
System.out.println("Test 9, Total Heads 23 = " + maxHeads (arr3, m: 3)); //m=3
System.out.println("Test 10, Total Heads 28 = " + maxHeads (arr3, m: 4));//m=4
System.out.println("Test 11, Total Heads 32 = " + maxHeads (arr3, m: 5));//m=5
System.out.println("Test 12, Total Heads 35 = " + maxHeads (arr3, m: 6));//m=6](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F346b36e0-a4d8-47d7-8bd1-1ad776cb1cf3%2Fe9efef61-d8a0-4237-8e93-fa2cb6da25e3%2Fl8m9mey_processed.png&w=3840&q=75)
Transcribed Image Text:public class Main{
static int maxHeads (int[] birds, int m){
return 0;
}
}
Run | Debug
public static void main(String[] args) {
int arr1[] = {20, 1, 15);
int arr2[] = {2, 1, 7, 4, 2};
int arr3[] = {4, 10, 6, 7, 3, 1);
HI
System.out.println("Test 1, Total Heads 20 = + maxHeads (arr1, m: 1)); //m =1, bird 1 cut 20 heads, arr1 is now {10,1,15}
2, Total Heads 35 = " + maxHeads (arr1, m: 2)); //m=2, bird 3 cut 15 head, arr1 is now {10,1,7}
bird 1 cut 10 heads, arr1 is now (5,1, 7}
System.out.println("Test
System.out.println("Test
3, Total Heads 45 = " + maxHeads (arr1, m: 3)); //m=3,
System.out.println("Test
System.out.println("Test
System.out.println("Test 6, Total Heads 14 = " +
4, Total Heads 7 = " + maxHeads (arr2, m: 1)); //m=1
5, Total Heads 11 = " + maxHeads (arr2, m: 2)); //m=2
maxHeads (arr2, m: 3)); //m=3
System.out.println("Test 7, Total Heads 10 = " + maxHeads (arr3, m: 1)); //m=1||
System.out.println("Test 8, Total Heads 17 = " + maxHeads (arr3, m: 2)); //m=2
System.out.println("Test 9, Total Heads 23 = " + maxHeads (arr3, m: 3)); //m=3
System.out.println("Test 10, Total Heads 28 = " + maxHeads (arr3, m: 4));//m=4
System.out.println("Test 11, Total Heads 32 = " + maxHeads (arr3, m: 5));//m=5
System.out.println("Test 12, Total Heads 35 = " + maxHeads (arr3, m: 6));//m=6
Expert Solution
![](/static/compass_v2/shared-icons/check-mark.png)
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
This is a popular solution!
Trending now
This is a popular solution!
Step by step
Solved in 3 steps with 1 images
![Blurred answer](/static/compass_v2/solution-images/blurred-answer.jpg)
Recommended textbooks for you
![Computer Networking: A Top-Down Approach (7th Edi…](https://www.bartleby.com/isbn_cover_images/9780133594140/9780133594140_smallCoverImage.gif)
Computer Networking: A Top-Down Approach (7th Edi…
Computer Engineering
ISBN:
9780133594140
Author:
James Kurose, Keith Ross
Publisher:
PEARSON
![Computer Organization and Design MIPS Edition, Fi…](https://www.bartleby.com/isbn_cover_images/9780124077263/9780124077263_smallCoverImage.gif)
Computer Organization and Design MIPS Edition, Fi…
Computer Engineering
ISBN:
9780124077263
Author:
David A. Patterson, John L. Hennessy
Publisher:
Elsevier Science
![Network+ Guide to Networks (MindTap Course List)](https://www.bartleby.com/isbn_cover_images/9781337569330/9781337569330_smallCoverImage.gif)
Network+ Guide to Networks (MindTap Course List)
Computer Engineering
ISBN:
9781337569330
Author:
Jill West, Tamara Dean, Jean Andrews
Publisher:
Cengage Learning
![Computer Networking: A Top-Down Approach (7th Edi…](https://www.bartleby.com/isbn_cover_images/9780133594140/9780133594140_smallCoverImage.gif)
Computer Networking: A Top-Down Approach (7th Edi…
Computer Engineering
ISBN:
9780133594140
Author:
James Kurose, Keith Ross
Publisher:
PEARSON
![Computer Organization and Design MIPS Edition, Fi…](https://www.bartleby.com/isbn_cover_images/9780124077263/9780124077263_smallCoverImage.gif)
Computer Organization and Design MIPS Edition, Fi…
Computer Engineering
ISBN:
9780124077263
Author:
David A. Patterson, John L. Hennessy
Publisher:
Elsevier Science
![Network+ Guide to Networks (MindTap Course List)](https://www.bartleby.com/isbn_cover_images/9781337569330/9781337569330_smallCoverImage.gif)
Network+ Guide to Networks (MindTap Course List)
Computer Engineering
ISBN:
9781337569330
Author:
Jill West, Tamara Dean, Jean Andrews
Publisher:
Cengage Learning
![Concepts of Database Management](https://www.bartleby.com/isbn_cover_images/9781337093422/9781337093422_smallCoverImage.gif)
Concepts of Database Management
Computer Engineering
ISBN:
9781337093422
Author:
Joy L. Starks, Philip J. Pratt, Mary Z. Last
Publisher:
Cengage Learning
![Prelude to Programming](https://www.bartleby.com/isbn_cover_images/9780133750423/9780133750423_smallCoverImage.jpg)
Prelude to Programming
Computer Engineering
ISBN:
9780133750423
Author:
VENIT, Stewart
Publisher:
Pearson Education
![Sc Business Data Communications and Networking, T…](https://www.bartleby.com/isbn_cover_images/9781119368830/9781119368830_smallCoverImage.gif)
Sc Business Data Communications and Networking, T…
Computer Engineering
ISBN:
9781119368830
Author:
FITZGERALD
Publisher:
WILEY