PROBLEM STATEMENT
In everything below, quotes and angle brackets are for clarity only.
As master Packyman trainer Ace Ketchup, you've been challenged to a Packyman
battle by your rival, Hairy Oaf! People have always wondered how you always
picked the right Packyman to face off against rivals. Your secret: A computer
program.
Packyman have four statistics. They have a name, a strength, a primary type,
and a secondary type. You have up to 20 Packyman at your disposal. Your rival
has already selected his team of three Packyman. Your job is to find the
combination of three Packyman that would do best against Hairy's Packyman.
The first String[] represents your Packyman, formatted as "<Name> <Strength>
<Type1> <Type2>". Name, Type1, and Type2 contain only uppercase letters.
Strength is an integer between 1 to 1000 inclusive, without leading zeroes.
The second String[] is your rivals Packyman, formatted in the same way.
The third String[] is a list representing types that have an advantage over (or
"beat") another type. This is formatted as "<TypeA> <TypeB>", where TypeA
beats TypeB. There will be no duplicate strings in this array.
A Packyman's "score" against another is calculated in the following manner:
If Packyman "A"'s primary type beats Packyman "B"'s primary type, Packyman A
gets a 50% strength bonus against Packyman B.
If Packyman "A"'s primary type beats Packyman "B"'s secondary type, Packyman
A gets a 25% strength bonus against Packyman B.
If Packyman "A"'s secondary type beats Packyman "B"'s primary type, Packyman
A gets a 20% strength bonus against Packyman B.
If Packyman "A"'s secondary type beats Packyman "B"'s secondary type,
Packyman A gets a 10% strength bonus against Packyman B.
The same is then done to Packyman "B"'s strength against "A". All values after
the decimal in the resulting strengths are truncated, and all bonuses are
percentages of the original strength.
To get the final score, subtract B's strength from A.
The best team is the team of Packyman with the greatest combined score against
all the rival's Packyman. Return the names of the three Packyman in
alphabetical order, separated by spaces. If two teams have the same score
against your rival's Packyman, return the string that occurs first
lexicographically. If the best team has a negative total score, return the
string "FORFEIT", because that's what you'll do.
DEFINITION
Class: Packyman
Method getBestTeam
Parameters: String[], String[], String[]
Returns: String
Method signature (be sure your method is public): String getBestTeam(String[]
you, String[] rival, String[] types);
NOTES
-Given <typeA> and <typeB>, it will be possible for the strings "<typeA>
<typeB>" and "<typeB> <typeA>" to appear in types at the same time.
-Given <typeA>, it will be possible for the string "<typeA> <typeA>" to appear
in types.
Topcoder will ensure the validity of the inputs. Inputs are valid if all of
the follwing criteria are met:
-you contains between 3 and 20 elements, inclusive
-rival contains exactly 3 elements
-all elements of both you and rival contain only the characters A-Z, 0-9, and
space (' ').
-all elements of both you and rival are formatted as "<Name> <Strength> <Type1>
<Type2>" with no extra spaces.
-<Name> may have digits in it.
-There are no duplicate names in you.
-each element in you and rival is between 7 and 50 characters in length,
inclusive.
-each <Name>, <Type1>, and <Type2> is between 1 and 20 characters in length,
inclusive.
-each <Strength> is an integer between 1 and 1000, inclusive, without leading
zeroes.
-types contains between 0 and 20 elements, inclusive.
-types contains no duplicates.
-each element of types is formatted as "<Type1> <Type2>" with no extra spaces.
-each element of types contains only the characters A-Z and a single space
between the two types.
-each element of types is between 3 and 50 characters in length, inclusive.
EXAMPLES
1.
you = {"JIGGLYDUFF 20 NORMAL NORMAL",
"PEEKATYOU 30 ELECTRIC ELECTRIC",
"PIGLET 40 GROUND GRASS",
"CHARBROILED 50 FIRE ROCK"}
rival = {"BAM 30 WATER WATER",
"MONKEY 10 NORMAL NORMAL",
"SPAM 60 GRASS GROUND"}
types = {"ELECTRIC WATER",
"FIRE GRASS",
"GROUND ELECTRIC",
"WATER FIRE",
"WATER GROUND",
"ROCK GROUND",
"GRASS WATER"}
Method returns "CHARBROILED PEEKATYOU PIGLET"
Scores are calculated as follows:
JIGGLYDUFF:
NORMAL isn't even mentioned in types, so there are no bonuses for either side.
JIGGLYDUFF vs. BAM -> 20-30 = -10.
JIGGLYDUFF vs. MONKEY -> 20-10 = 10.
JIGGLYDUFF vs. SPAM -> 20-60 = -40.
JIGGLYDUFF's final score : -40.
PEEKATYOU:
PEEKATYOU vs. BAM
Bonuses for PEEKATYOU:
Primary Beats Primary 50%
Primary Beats Secondary 25%
Secondary Beats Primary 20%
Secondary Beats Secondary 10%
----
Total: 105%
BAM receives no bonuses.
Score is 30+30*105%=61.5=61(round down afterwards) - 30 = 31.
PEEKATYOU vs. MONKEY... No bonuses. 30-10 = 20.
PEEKATYOU vs. SPAM
PEEKATYOU gets no bonuses.
SPAM's Bonuses:
Secondary beats Primary 20%
Secondary beats Secondary 10%
Score is 30-(60+60*30%) = 30-78 = -48.
Score for PEEKATYOU = 3.
PIGLET:
PIGLET vs. BAM yields (40+40*30%(SBP&SBS))-(30+30*70%(PBP&SBP)) = 52-51 = 1.
PIGLET vs. MONKEY yields 40-10 = 30.
PIGLET vs. SPAM yields 40-60 = -20.
Score for PIGLET = 11.
CHARBROILED:
CHARBROILED vs. BAM yields 50 - (30+30*70%(PBP&SBP)) = 50-51 = -1.
CHARBROILED vs. MONKEY yields 50-10 = 40.
CHARBROILED vs. SPAM yields (50+50*60%(PBP&SBS))-60 = 80-60 = 20.
Score for CHARBROILED = 59.
Obviously, the best team is CHARBROILED, PIGLET, and PEEKATYOU. That in
alphabetical order is "CHARBROILED PEEKATYOU PIGLET".
2.
you = {"JIGGLYDUFF 20 NORMAL NORMAL",
"PEEKATYOU 30 ELECTRIC ELECTRIC",
"PIGLET 40 GROUND GRASS",
"CHARBROILED 50 FIRE ROCK"}
rival = {"BAM 300 WATER WATER",
"MONKEY 100 NORMAL NORMAL",
"SPAM 600 GRASS GROUND"}
types = {"ELECTRIC WATER",
"FIRE GRASS",
"GROUND ELECTRIC",
"WATER FIRE",
"WATER GROUND",
"ROCK GROUND",
"GRASS WATER"}
Method returns "FORFEIT"
Obviously, his Packyman have been doing some training, and yours don't stand a
chance.
3.
you = {"B 10 A A",
"E 10 A A",
"A 10 A A",
"D 10 A A",
"C 10 A A"}
rival = {"Q 1 A A",
"Q 2 A A",
"Q 3 A A"} Note: Rival may contain duplicate names, but not you.
types = {}
returns "A B C"
All combinations of three Packyman would tie (with an overall score of 72), so
"A B C" is the first one lexicographically.
4.
you = {"B 10 A A",
"E 10 A A",
"A 10 A A",
"D 10 B B",
"C 10 A A"}
rival = {"Q 1 A A",
"Q 2 A A",
"Q 3 A A"}
types = {"B A"}
returns "A B D"
All combinations of three Packyman that contains "D" would tie. The winner of
the alphabetic race here is "A B D".