Based on that need help in solving the code for this problem in python. The time complexity has to be as less as possible (nlogn or n at best, no n^2). Apply the divide and conquer algorithm to the problem. Make sure both test cases return correct answers. Output Format For each test case, output a single line, which is the minimum hit points L Leon needs to survive his mission. If Leon needs more than 10^5 HP, print "You're gonna need a flashbang." (without quotes). Sample Input 0 3 1 3 6 4 9 4 3 2 2 Sample Output 0 9 Explanation 0 You only need 9 HP. The scenario runs as follows. There are 3 zombies. Leon can shoot the zombie with 3 HP, downing it. He can still shoot 1 bullet into the zombie with 4 HP, leaving it with 3 HP. Remaining zombies = {3,6} There are 2 zombies that are not downed or stunned, which is not less than Y = 2. Leon guards, taking 1 damage per zombie, for a total of 2 damage. Leon has 7 HP remaining. There are 2 zombies. Leon reloads back to C = 4 bullets in his clip. There are 2 zombies that are not downed or stunned, which is not less than Y = 2. Leon guards, taking 1 damage per zombie, for a total of 2 damage. Leon has 5 HP remaining. There are 2 zombies. Leon can shoot the zombie with 3 HP, downing it. He can still shoot 1 bullet into the zombie with 6 HP, leaving it with 5 HP. Remaining zombies = {5} There is 1 zombie remaining which is not downed or stunned, which is less than Y = 2. Leon charges in, taking 2 damage per zombie, for a total of 2 damage. Leon has 3 HP remaining. Leon has the vaccine. There is 1 zombie. Leon reloads. There is 1 zombie that is not downed or stunned, which is less than Y = 2. Leon charges in, taking 2 damage per zombie, for a total of 2 damage. Leon has 1 HP remaining. Leon escapes the laboratory, succeeding his mission. The actual code # Enter your code here. Read input from STDIN. Print output to STDOUT

Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
icon
Related questions
Question

Information is present in the screenshot and below. Based on that need help in solving the code for this problem in python. The time complexity has to be as less as possible (nlogn or n at best, no n^2). Apply the divide and conquer algorithm to the problem. Make sure both test cases return correct answers.

Output Format
For each test case, output a single line, which is the minimum hit points L Leon needs to survive his mission. If Leon needs more than 10^5 HP, print "You're gonna need a flashbang." (without quotes).

Sample Input 0
3 1
3 6 4
9 4 3 2 2

Sample Output 0
9

Explanation 0
You only need 9 HP. The scenario runs as follows.

  1. There are 3 zombies. Leon can shoot the zombie with 3 HP, downing it. He can still shoot 1 bullet into the zombie with 4 HP, leaving it with 3 HP. Remaining zombies = {3,6}
  2. There are 2 zombies that are not downed or stunned, which is not less than Y = 2. Leon guards, taking 1 damage per zombie, for a total of 2 damage. Leon has 7 HP remaining.
  3. There are 2 zombies. Leon reloads back to C = 4 bullets in his clip.
  4. There are 2 zombies that are not downed or stunned, which is not less than Y = 2. Leon guards, taking 1 damage per zombie, for a total of 2 damage. Leon has 5 HP remaining.
  5. There are 2 zombies. Leon can shoot the zombie with 3 HP, downing it. He can still shoot 1 bullet into the zombie with 6 HP, leaving it with 5 HP. Remaining zombies = {5}
  6. There is 1 zombie remaining which is not downed or stunned, which is less than Y = 2. Leon charges in, taking 2 damage per zombie, for a total of 2 damage. Leon has 3 HP remaining. Leon has the vaccine.
  7. There is 1 zombie. Leon reloads.
  8. There is 1 zombie that is not downed or stunned, which is less than Y = 2. Leon charges in, taking 2 damage per zombie, for a total of 2 damage. Leon has 1 HP remaining. Leon escapes the laboratory, succeeding his mission.

The actual code

# Enter your code here. Read input from STDIN. Print output to STDOUT
For this problem, the field follows this behavior:
goal = vaccine
MISSION = ???
while MISSION == ???
if there are zombies in the hallway
if Leon's clip is empty
reload
else
Leon shoots as many zombies as he can (you choose the order)
if all zombies are stunned or downed, Leon has enough time to reload back to a full
clip
let W = # of zombies that are not downed or stunned
if W < Y
Leon rushes to his goal
min (X,W) zombies deal Z damage each to Leon
if Leon's HP > 0
if goal
else
else
else
vaccine.
goal exit
MISSION = ACCOMPLISHED
MISSION FAILED
Leon stands his ground and guards himself
min (W,X) zombies deal floor (Z / 2) damage each to Leon
if Leon's HP <= 0:
MISSION = FAILED
all stunned zombies recover. Any zombies who have taken damage without being downed
recover (1.e. they have to take another S damage to be stunned)
Your task is simple: what is the minimum hit points I Leon needs in order to survive this hallway?
Input Format
Input contains several test cases. The first line contains N and Q, indicating the number of zombies in the
hallway and the number of queries.
The next line contains N space-separated integers H₂, indicating the HP values of the zombies in the hallway.
Assume Leon is a good enough shot to hit any of them.
Q lines follow, each containing 5 space-separated integers S, C, X, Y, Z wherein:
• S is the amount of damage until a zombie is stunned.
C' is the clip size
• X is the number of zombies that can attack Leon at once (see Leon's strategy in the problem statement)
• Y is Leon's threshold for deciding whether to charge or guard
• Z is the damage a zombie inflicts on Leon
Constraints
0≤N ≤ 10³
1≤Q, S, C, X, Y, Z ≤ 10³
1≤ H₁ ≤ 10³ for all 1 ≤ i ≤ N
Transcribed Image Text:For this problem, the field follows this behavior: goal = vaccine MISSION = ??? while MISSION == ??? if there are zombies in the hallway if Leon's clip is empty reload else Leon shoots as many zombies as he can (you choose the order) if all zombies are stunned or downed, Leon has enough time to reload back to a full clip let W = # of zombies that are not downed or stunned if W < Y Leon rushes to his goal min (X,W) zombies deal Z damage each to Leon if Leon's HP > 0 if goal else else else vaccine. goal exit MISSION = ACCOMPLISHED MISSION FAILED Leon stands his ground and guards himself min (W,X) zombies deal floor (Z / 2) damage each to Leon if Leon's HP <= 0: MISSION = FAILED all stunned zombies recover. Any zombies who have taken damage without being downed recover (1.e. they have to take another S damage to be stunned) Your task is simple: what is the minimum hit points I Leon needs in order to survive this hallway? Input Format Input contains several test cases. The first line contains N and Q, indicating the number of zombies in the hallway and the number of queries. The next line contains N space-separated integers H₂, indicating the HP values of the zombies in the hallway. Assume Leon is a good enough shot to hit any of them. Q lines follow, each containing 5 space-separated integers S, C, X, Y, Z wherein: • S is the amount of damage until a zombie is stunned. C' is the clip size • X is the number of zombies that can attack Leon at once (see Leon's strategy in the problem statement) • Y is Leon's threshold for deciding whether to charge or guard • Z is the damage a zombie inflicts on Leon Constraints 0≤N ≤ 10³ 1≤Q, S, C, X, Y, Z ≤ 10³ 1≤ H₁ ≤ 10³ for all 1 ≤ i ≤ N
It is currently Leon S. Kennedy's first day on the Raccoon City police force. Unfortunately, the deadly T-virus
has recently broken out and for the past few hours, he has been struggling to survive the hordes of infected
zombies that have been getting in the way of his survival.
After escaping through the sewers, he finally found himself in what appears to be the source of all this chaos:
the Umbrella Corporation NEST labs underneath Raccoon City. At the heart of this laboratory rests a possible
vaccine that could prevent the virus from spreading further than Raccoon City.
Unfortunately, NEST is a labyrinthine hellscape of zombie infested hallways and although Leon brought a lot
of ammunition, time is limited.
For this problem, let us only consider a single hallway. Leon's goal is to:
1. Reach the end of the hallway, alive and well.
2. Retrieve the vaccine.
3. Make it back to the start of the hallway, also alive and well.
Unfortunately, the hallway is littered with zombies, each with a varying amount of hit points. The hit points
refer to how much damage they can take before the zombie ceases to be a threat.
The following describe the effects of Leon and the zombie's actions:
• Leon has I hit points.
• One bullet from Leon's pistol deals 1 damage.
• A zombie is downed once their hit points reaches 0 or lower.
• A zombie is stunned when they take at least S damage.
•
Leon has C bullets in each clip. This means he can take C shots before needing to reload.
• A zombie deals Z damage per attack.
Leon always starts with a full clip. For this problem, assume that Leon has unlimited ammunition.
Transcribed Image Text:It is currently Leon S. Kennedy's first day on the Raccoon City police force. Unfortunately, the deadly T-virus has recently broken out and for the past few hours, he has been struggling to survive the hordes of infected zombies that have been getting in the way of his survival. After escaping through the sewers, he finally found himself in what appears to be the source of all this chaos: the Umbrella Corporation NEST labs underneath Raccoon City. At the heart of this laboratory rests a possible vaccine that could prevent the virus from spreading further than Raccoon City. Unfortunately, NEST is a labyrinthine hellscape of zombie infested hallways and although Leon brought a lot of ammunition, time is limited. For this problem, let us only consider a single hallway. Leon's goal is to: 1. Reach the end of the hallway, alive and well. 2. Retrieve the vaccine. 3. Make it back to the start of the hallway, also alive and well. Unfortunately, the hallway is littered with zombies, each with a varying amount of hit points. The hit points refer to how much damage they can take before the zombie ceases to be a threat. The following describe the effects of Leon and the zombie's actions: • Leon has I hit points. • One bullet from Leon's pistol deals 1 damage. • A zombie is downed once their hit points reaches 0 or lower. • A zombie is stunned when they take at least S damage. • Leon has C bullets in each clip. This means he can take C shots before needing to reload. • A zombie deals Z damage per attack. Leon always starts with a full clip. For this problem, assume that Leon has unlimited ammunition.
Expert Solution
steps

Step by step

Solved in 2 steps

Blurred answer
Knowledge Booster
Counting Sort
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.
Similar questions
Recommended textbooks for you
Database System Concepts
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education