TopCoder problem "VoteRigging" used in SRM 388 (Division II Level Two)



Problem Statement

    

You have used your secret mind-reading device to find out how every voter will vote in the next election. Your mind-reading device also revealed to you that all the voters are prepared to change their vote if you pay them enough.

The ith element of votes is the number of people who were originally planning to vote for candidate i. Return the minimum number of votes that you must change to ensure that candidate 0 (your favorite) will have more votes than any other candidate.

 

Definition

    
Class:VoteRigging
Method:minimumVotes
Parameters:int[]
Returns:int
Method signature:int minimumVotes(int[] votes)
(be sure your method is public)
    
 

Constraints

-votes will contain between 1 and 50 elements, inclusive.
-Each element of votes will be between 1 and 100, inclusive.
 

Examples

0)
    
{5, 7, 7}
Returns: 2
Buying one vote from each of the other two candidates leaves candidate 0 with 7 votes and the others with 6 each.
1)
    
{10, 10, 10, 10}
Returns: 1
You need strictly more votes than all other candidates, so you need to buy one vote.
2)
    
{1}
Returns: 0
If you are the only candidate, you automatically win.
3)
    
{5, 10, 7, 3, 8}
Returns: 4

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=11122&pm=8520

Writer:

bmerry

Testers:

PabloGilberto , Olexiy , marek.cygan , ivan_metelsky

Problem categories:

Brute Force