Connection Status:
Competition Arena > GreatFairyWar

GreatFairyWar

SRM 557 · 2012-06-05 · by cgy4ever

SRM 557 · 2012-06-05 · by cgy4ever · Brute Force, Greedy
Class Name: GreatFairyWar
Return Type: int
Method Name: minHP
Arg Types: (vector<int>, vector<int>)
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 two int[]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.

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.

Statement by TopCoder, Inc. — view the original on the archive.

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

Submitting as anonymous