| | Class name: Reps
Method name: representatives
Parameters: int[], int
Returns: int[]
Implement a class Reps, which contains a method representatives.
representatives returns a int[] of elements indicating the number of
representatives various states should receive. The parameters are an int[],
containing the populations of various states, and an int indicating how many
representatives are to be distributed over the states. Return the most
equitable distribution of representatives.
The most equitable division minimizes the sum of discrepancies between the
number of representatives given to each state and each state's expected share.
A state's expected share of representatives is defined as:
state's population
state's expected share = numRepresentatives x --------------------
total population
where "numRepresentatives" is the total number of representatives to be
apportioned among the states and "total population" is the sum of the
populations of the individual states. The discrepancy between the number of
representatives given to a state and that state's expected share is the
absolute value of their difference. For example, when dividing 4
representatives over states containing 4 and 6 people, the first state has an
expected share of 4 x 4 / 10 = 1.6 representatives while the second state has
an expected share of 4 x 6 / 10 = 2.4 representatives. To minimize the summed
differences, each state gets 2 representatives, giving a discrepancy sum of |2
- 1.6| + |2 - 2.4| = .8 people.
Here is the method signature (be sure your method is public):
int[] representatives(int[] counts, int numRepresentatives)
*counts is a int[] of between 1 and 50, inclusive, positive Integers.
*The sum of the Integers in counts is less than or equal to 1,000,000,000
*The total number of numRepresentatives is positive (but no greater than the
total population)
*TopCoder will ensure only valid input is passed to your method.
In the case of multiple such solutions, where one or more representatives can
be allocated to any of two or more states, choose the solution that assigns the
representative(s) to the earliest possible state(s) in the list. For example
[10, 10, 10], 5 should return [2, 2, 1] over all other possible permutations.
The returned int[] must represent the number of representatives per state in
the same order as the input int[] and must be the same size as the input int[].
Examples:
If the int[] is [10, 20, 30] and the int is 6, the returned int[] is [1, 2, 3]
[10, 20, 30], 7 returns [1, 2, 4]
[10, 20, 30], 60 returns [10, 20, 30]
[6, 28, 496, 8128, 33550336], 6972593 returns [1, 6, 103, 1689, 6970794]
[10,10,10], 5 returns [2,2,1]
[1,1,1000], 5 returns [0,0,5]
|