Connection Status:
Competition Arena > BossFight

BossFight

SRM 116 · 2002-10-15 · by LunaticFringe

SRM 116 · 2002-10-15 · by LunaticFringe
Class Name: BossFight
Return Type: int[]
Method Name: getHealthRange
Arg Types: (vector<string>, vector<string>)
Problem Statement

Problem Statement

You are helping your friend beat the final boss in the latest RPG. "Man, this guy is tough!" your friend exclames. "How much health does he have?" You have to admit that even though you've played this game hundreds of times before, you don't know for sure. However, being the obsessive gamer that you are, you've kept a detailed record of all your previous boss fights. The record shows the attacks you did, in order, to vanquish the enemy in each game you played. You decide to write a program to determine the range of possible health values for the boss.

You will be given a list of attack types (each attack type in the format "<name> <damage>"), along with a list of battles (a battle being a space separated, ordered list of attacks). You should return a int[] containing the minimum and maximum possible health values for the boss. The int[] should contain exactly two elements and be formatted as {minHealth, maxHealth}.

Notes

  • The boss starts out with a fixed, positive health value which never increases. It only decreases when you attack him.
  • Each attack subtracts an amount from the boss's health equal to the amount of damage that attack does. The boss dies when his health becomes nonpositive.
  • The final attack in each battle represents the finishing blow. The sum of all the previous attacks were not enough to defeat the boss, but when the damage from the final attack is added, it is enough (or more than enough) to win.

Constraints

  • attacks will contain between 1 and 50 elements, inclusive.
  • Each element of attacks will be between 3 and 50 characters, inclusive, and only contain uppercase letters 'A'-'Z', digits '0'-'9', and spaces.
  • Each element of attacks will be of the form " " (quotes used for clarity), where consists of only uppercase letters, and is an integer from 1 to 1000000, inclusive, with no leading zeroes.
  • Each element of attacks will have a unique attack name.
  • battles will contain between 1 and 50 elements, inclusive.
  • Each element of battles will be between 1 and 50 characters, inclusive, and only contain uppercase letters 'A'-'Z' and spaces.
  • Each element of battles will contain one or more attack names separated by exactly one space.
  • No element of attacks or battles will start or end with a space.
  • Each attack name mentioned in battles will also be mentioned in attacks.
  • The inputs will not contradict each other. (That is, there will always be at least one possible health value for the boss.)
Examples
0)
{"PUNCH 5","KICK 10","THROW 12"}
{"KICK KICK PUNCH"}
Returns: { 21,  25 }

Here we only have data from a single battle. The first kick dealt the boss 10 points of damage, which wasn't enough to kill him. The second kick increased the damage dealt to 20, which was still less than the boss's health. The final punch resulted in a total of 25 points of damage, which was enough to win. The boss's health must therefore be from 21 to 25, inclusive.

1)
{"PUNCH 5","KICK 10","THROW 12"}
{"KICK KICK PUNCH","THROW KICK THROW","THROW THROW"}
Returns: { 23,  24 }

The first battle (from above) tells us that the boss's health must be between 21 and 25, inclusive. The second battle tells us that we can successfully deal 22 points of damage without winning (THROW + KICK), but that 34 points of damage (THROW + KICK + THROW) is more than enough. The third battle tells us that the boss has between 13 and 24 points of health. Battle 1: {21, 25} Battle 2: {23, 34} Battle 3: {13, 24} Therefore, we know the boss has either 23 or 24 health points.

2)
{"POKE 1"}
{"POKE POKE POKE POKE POKE POKE POKE POKE POKE POKE"}
Returns: { 10,  10 }

We once again only have one battle, but it is enough to determine that the boss has exactly 10 points of health.

3)
{"OVERKILL 9999"}
{"OVERKILL"}
Returns: { 1,  9999 }

We know that 9999 is enough to kill the boss. Since the boss's health must be positive, we return 1 as the minimum possible health.

4)
{"A 965939"
,"B 642876"
,"C 579290"
,"D 305875"
,"E 206139"
,"F 202795"
,"G 307979"
,"H 144467"
,"I 866386"
,"J 943978"
,"K 168660"
,"L 559739"
,"M 878626"
,"N 383086"
,"O 673845"
,"P 826654"
,"Q 980470"
,"R 619790"
,"S 587024"
,"T 467245"
,"U 168317"
,"V 977394"
,"W 786"
,"X 16241"
,"Y 400479"
,"Z 893457"}
{"R A O B O K P V T S D U K I Z T F Y"
,"F W V J H Y X P P E X V E X S L L A A F R"
,"A C V I X E R T Y M X C W V Q R F S K"
,"G A C D T R W Y J B J N N A I Q Q"
,"U U U N F Q L N O W D Q D T Y Z U S L P Y S"
,"O F N V V Q O B D A U K E U K I P I"
,"I A K M O P F T V W G C M X G Y Q M"
,"S J N Y L J D E I W G F K L J N Z R F X H K I"
,"T E Q C E D L S O Q C P Q N O E G V"
,"F P Z W V A L K P X K D W Q O Q R P C"}
Returns: { 9994870,  10076486 }

Submissions are judged against all 31 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class BossFight with a public method vector<int> getHealthRange(vector<string> attacks, vector<string> battles) · 31 test cases · 2 s / 256 MB per case

Submitting as anonymous