TopCoder problem "SumoTournament" used in TCHS SRM 37 (Division I Level Three)



Problem Statement

    There are several sumo wrestlers registered for the current season. You are given a int[] weight, where the i-th element is the weight of the i-th wrestler. One or more of these wrestlers are registered in this week's tournament. You are given an int averageWeight, which is the exact average weight of the wrestlers registered in the tournament. Return the maximal possible weight of a wrestler who might be in this tournament, or -1 if the average is not possible with the given input.
 

Definition

    
Class:SumoTournament
Method:maxWeight
Parameters:int[], int
Returns:int
Method signature:int maxWeight(int[] weight, int averageWeight)
(be sure your method is public)
    
 

Constraints

-averageWeight will be between 1 and 200, inclusive.
-weight will contain between 1 and 50 elements, inclusive.
-Each element of weight will be between 1 and 200, inclusive.
 

Examples

0)
    
{80,90,100}
90
Returns: 100
There are three possible tournaments with an average weight of 90: {80,90,100}, {80,100}, {90}. Thus, it is possible that the wrestler with weight 100 is in the tournament.
1)
    
{81,90,150}
90
Returns: 90
2)
    
{10,20}
15
Returns: 20
3)
    
{40,30,20,10}
27
Returns: -1
There is no way to achieve an average weight of 27.

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10776&pm=7660

Writer:

Janq

Testers:

PabloGilberto , brett1479 , Olexiy , ivan_metelsky

Problem categories:

Dynamic Programming, Simple Math, Simple Search, Iteration