TopCoder problem "BestResult" used in East China Round 1 (Division I Level Three)



Problem Statement

    

The Olympic Games are over and now you need to rank the teams. You must pick three integers Pg, Ps and Pb, representing the number of points awarded to each team for each gold, silver and bronze medal they won, respectively, where 1000 >= Pg >= Ps >= Pb >= 1. The teams will be ranked according to the total number of points they have (teams with more points will be ranked higher). You want to select Pg, Ps and Pb so that your team gets ranked as high as possible.

You will be given a String[] teams, the i-th element of which represents the medal counts of the i-th team. Each element will be formatted as "G S B" (quotes for clarity), where G, S and B are integers representing the total number of gold, silver and bronze medals won by that team, respectively. Your team is the 0-th team. The highest possible rank is 1, the second highest rank is 2, and so on. If your team has the same number of total points as some other teams, your team will be ranked higher than those other teams. In other words, your final ranking will be equal to 1 plus the number of teams that have a strictly greater number of points than your team.

Return a int[] containing exactly three elements - the values of Pg, Ps and Pb (in that order) that will give your team the highest ranking. If there are multiple possible return values, return the one with the smallest value for Pg. If there are still multiple return values, return the one with the smallest value for Ps. If there are still multiple return values, return the one with the smallest value for Pb.

 

Definition

    
Class:BestResult
Method:findBestResult
Parameters:String[]
Returns:int[]
Method signature:int[] findBestResult(String[] teams)
(be sure your method is public)
    
 

Constraints

-Each element of teams will be formatted as "G S B" (quotes for clarity), where G, S and B are integers between 0 and 100000, inclusive, with no extra leading zeroes.
-teams will contain between 2 and 15 elements, inclusive.
 

Examples

0)
    
{"1 1 1", "0 1 2", "2 1 0"}
Returns: {1, 1, 1 }
In this example, your team has won 1 gold, 1 silver and 1 bronze. There are multiple ways to get your team ranked number 1, but the best way is to assign 1 to Pg, Ps and Pb. Every team gets 3 points, and your team gets ranked the highest.
1)
    
{"0 0 0", "1 1 1"}
Returns: {1, 1, 1 }
In this example, no matter what values you choose, your team will always be ranked second.
2)
    
{"0 1 2", "1 0 0", "0 0 4"}
Returns: {2, 2, 1 }
3)
    
{"0 3 0", "0 0 4", "3 0 0"}
Returns: {2, 2, 1 }
4)
    
{"24 0 0", "5 6 7", "5 45 5", "4 4 64"}
Returns: {4, 1, 1 }
5)
    
{ "1 2 0", "5 4 0", "3 0 1", "0 4 5", "2 3 4" }
Returns: {7, 1, 1 }
6)
    
{ "6 4 8", "2 0 4", "3 8 1", "0 6 5", "3 6 10", "5 6 7", "8 2 7" }
Returns: {3, 2, 2 }
7)
    
{ "7 8 5", "8 2 7", "3 10 0", "10 8 0", "5 2 7", "1 10 10", "9 7 1", "5 8 0" }

Returns: {3, 2, 2 }

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8789

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=12226&pm=8789

Writer:

DStepanenko

Testers:

PabloGilberto , Olexiy , lovro , ivan_metelsky

Problem categories:

Geometry, Simple Math, Simulation, Sorting, String Parsing