GreatFairyWar
SRM 557 · 2012-06-05 · by cgy4ever
SRM 557 · 2012-06-05 · by cgy4ever · Brute Force, Greedy
Problem Statement
Problem Statement
You are a wizard.
You are facing N fairies, numbered 0 through N-1.
Your goal is to defeat all of them.
You can only attack one fairy at a time.
Moreover, you must fight the fairies in order: you can only attack fairy X+1 after you defeat fairy X.
On the other hand, all fairies that have not been defeated yet will attack you all the time.
Each fairy has two characteristics: her damage per second (dps) and her amount of hit points. Your damage per second is 1. That is, you are able to reduce an opponent's hit points by 1 each second. In other words, if a fairy has H hit points, it takes you H seconds to defeat her.
You are given twoint[] s, each of length N: dps and hp.
For each i, dps[i] is the damage per second of fairy i, and hp[i] is her initial amount of hit points.
We assume that your number of hit points is sufficiently large to avoid defeat when fighting the fairies.
Compute and return the total number of hit points you'll lose during the fight.
In other words, return the total amount of damage the attacking fairies will deal.
Each fairy has two characteristics: her damage per second (dps) and her amount of hit points. Your damage per second is 1. That is, you are able to reduce an opponent's hit points by 1 each second. In other words, if a fairy has H hit points, it takes you H seconds to defeat her.
You are given two
Notes
- Damage per second (dps) of a person P is the rate at which P can deal damage to their opponents.
Constraints
- dps will contain between 1 and 30 elements, inclusive.
- dps and hp will contain the same number of elements.
- Each element in dps will be between 1 and 30, inclusive.
- Each element in hp will be between 1 and 30, inclusive.
Examples
0)
{1,2}
{3,4}
Returns: 17
It will take you 3 seconds to defeat fairy 0 and then 4 seconds to defeat fairy 1. During the first 3 seconds both fairies attack you, dealing 1+2 = 3 damage each second. During the next 4 seconds fairy 1 continues to attack you, dealing 2 damage each second. The total number of hit points you lose is 3*(1+2) + 4*2 = 9 + 8 = 17.
1)
{1,1,1,1,1,1,1,1,1,1}
{1,1,1,1,1,1,1,1,1,1}
Returns: 55
The answer is 10+9+...+3+2+1 = 55.
2)
{20,12,10,10,23,10}
{5,7,7,5,7,7}
Returns: 1767
3)
{5,7,7,5,7,7}
{20,12,10,10,23,10}
Returns: 1998
4)
{30,2,7,4,7,8,21,14,19,12}
{2,27,18,19,14,8,25,13,21,30}
Returns: 11029
Submissions are judged against all 134 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class GreatFairyWar with a public method int minHP(vector<int> dps, vector<int> hp) · 134 test cases · 2 s / 256 MB per case