uva online judge australian voting problem solution python | uva 10142

The australian voting problem is little tricky but very easy problem, which can be stated as,

Australian ballots require that the voter rank the candidates in order of choice. Initially only the first choices are counted and if one candidate receives more than 50% of the vote, that candidate is elected. If no candidate receives more than 50%, all candidates tied for the lowest number of votes are eliminated. Ballots ranking these candidates first are recounted in favour of their highest ranked candidate who has not been eliminated. 

This process continues [that is, the lowest candidate is eliminated and each ballot is counted in favour of its ranked non-eliminated candidate] until one candidate receives more than 50% of the vote or until all candidates are tied.

Sample Input

1

3 
John Doe 
Jane Smith 
Sirhan Sirhan 
1 2 3 
2 1 3 
2 3 1 
1 2 3 
3 1 2

Sample Output

John Doe

Explanation

In australian voting, each voter has to vote all candidates, but in priority i.e if voter voted as 1 3 2 then his first priority was to candidate 1, then candidate 3, then candidate 2.

By considering all the votes of candidates, if any candidate received more than 50% of total votes then he will be declared as winner.

If none of condidates received more than 50% votes, then condidate with minimum number of votes is eliminated. And those voters who voted candidate 3 as their first priority, their vote goes to candidate given in second priority.

Example, if candidate 1 received lowest votes, then vote of above voter (i.e 1 3 2) will be considered for candidate 3 since he voted candidate 3 as 2nd priority.

After recalculating votes for remaining candidates, again same procedure is repeated until someone gates votes above 50%.

Code

global answer, candidate_names, voters, candidate_votes, no_of_voters, count, mid, VOTERS

no_of_itterations = int(input("Enter no of itterations : "))

def Match_candidate(x):
    global count, answer, voters, VOTERS
    
    per = 10**(no_of_candidates-1)
    y = x//per
    y-=1 #since user entered candidate from 1 not 0
    
    candidate_votes[y]+=1
    if(candidate_votes[y]>mid and answer==False):
        print(candidate_names[y])
        answer=True
        return
    else:
        count+=1

    if(count==no_of_voters):
        for i in range(0,no_of_candidates):
            for j in range(0,no_of_candidates):
                if(candidate_votes[i]<candidate_votes[j]):
                    min = i             #find minimum
        min+=1 
        #since user entered candidate from 1 not 0
        #cnt = 0
        VOTERS = []          #to change 'voters' list
        for x in voters:
            per = 10**(no_of_candidates-1)
            y = x//per
            #cnt+=1
            if(y==min):
                x = x%per
                x = x*10
            VOTERS.append(x)
                
        
            

while(no_of_itterations):
    no_of_candidates = int(input("Enter no of candidates : "))

    answer = False
    candidate_names = []
    voters = []                                
    candidate_votes = []
    no_of_voters = 0
    count=0
    

    for i in range(0,no_of_candidates):
        candidate_votes.append(int(0))

    print("\nEnter names : \n")
    for i in range(0,no_of_candidates):
        candidate_names.append(input())
        
    while(1):
        temp = input()
        if len(temp.strip()) == 0 :    #check empty line
            break
        else:
            voters.append(int(temp))
        no_of_voters+=1

    mid = no_of_voters/2
        
    while(answer==False):
        for i in voters:
            Match_candidate(i) 
            #calculate candidate votes and rearrenge while 
            #elliminating
            if(answer==True):
                break

        for i in range(0,no_of_candidates):
            candidate_votes[i] = 0
        count=0
        voters = VOTERS

    no_of_itterations-=1
            
    

Here, we first calculate first priority of each voter and assign it to respective voter. Then by using Match_candidate function we check if any candidate has votes above 50% i.e > mid, if yes then return result as candidate name.

If no candidate obtained above 50%, then eliminate candidate with minimum number of votes and recalculates votes vote again. Keep doing until winner is obtained. 

Related keywards: australian voting programming challenges in python, australian voting uva solution, australian voting uva, uva 10142, australian voting uva explanation, uva 10142 source code, online judge australian voting.