TopCoder problem "TheTournamentDivOne" used in SRM 453 (Division I Level Two)



Problem Statement

    

John and Brus have an interest in team sports tournaments. They are currently investigating the intermediate standings of a tournament. They don't know which games have been played so far. They only know that the tournament is played using the following rules:

Each game is played between two teams and results in either a victory for one team or a draw. If a team wins a game, it gains w points and its opponent gains no points. In case of a draw, each team gains d points. The score of a team is the sum of all the points it has gained from all its games. There are no restrictions on which teams can play against each other, and each pair of teams can play against each other any number of times (possibly zero).

You are given a int[] points representing the intermediate standings of the tournament. The i-th element of points is the score of the i-th team. Return the minimum number of games that could have been played to achieve those standings. If points doesn't represent a valid state, return -1 instead.

 

Definition

    
Class:TheTournamentDivOne
Method:find
Parameters:int[], int, int
Returns:int
Method signature:int find(int[] points, int w, int d)
(be sure your method is public)
    
 

Constraints

-points will contain between 2 and 50 elements, inclusive.
-Each element of points will be between 0 and 10,000, inclusive.
-w will be between 1 and 10,000, inclusive.
-d will be between 1 and w, inclusive.
 

Examples

0)
    
{10, 1, 1}
2
1
Returns: 6
The first team has five wins or four wins and two draws. The second and the third teams each has one draw.
1)
    
{1, 1, 1}
2
1
Returns: -1
These standings are impossible. For each of the three teams to have one point, each one must have played in a game that resulted in a draw. There is no way for three teams to have each played in exactly one game.
2)
    
{1, 4, 0, 2}
3
1
Returns: 3
The only win goes to the second team.
3)
    
{8, 3, 8, 5, 9, 2, 7, 11}
3
2
Returns: 15

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13907&pm=10685

Writer:

Vasyl[alphacom]

Testers:

PabloGilberto , ivan_metelsky , Chmel_Tolstiy

Problem categories:

Simple Math, Simple Search, Iteration