Australian Voting

From Progteam

Jump to: navigation, search
Checkmark.jpg This problem has been solved by kerry.



Australian Voting
Problem Number 2692
Sorter: kerry
Source: Unknown
Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=2692



Australian Voting is problem number 2692 on the Peking University ACM site.


Kerry's C answer

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


int get_input();
int vote();

int main() {
char *names[21];
int tmp, num,i,j, votes[1001][21], *voters;
        tmp = 5;
        for(i=0;i<1001;i++)
                for(j=0;j<21;j++)
                        votes[i][j]=0;
        voters = &tmp;
        for(i=0;i<21;i++)
                names[i]=(char *)malloc(sizeof(char)*106);
        get_input(names, &num, votes, voters);
        vote(names, num,votes, *voters);

}

int get_input(char *names[21], int *num, int votes[1001][21], int *voters) {
int i,j;
char a;
        *voters=0;
        scanf("%d\n", num);
        for(i=1;i<=*num;i++)
                fgets(names[i], 100, stdin);
        j=0;
        while(a!=EOF && j<1001) {
                for(i=1;i<=*num;i++)
                        scanf("%d", &votes[j][i]);
                j++;
                a=getchar();
        }
        *voters=(j-1);
}

int vote(char *names[21], int num, int votes[1001][21], int voters) {
int i, j, k, m,max, min[21], max_num, min_num, next, tally[21], x, out[21];
        max = 0;
        for(i=0;i<21;i++) {
                min[i] = 0;
                tally[i] = 0;
                out[i]=0;
        }
        max_num = 0;
        min_num = 10000000;
        next=1;
        for(i=0;i<voters;i++){
                m=1;
                while(votes[i][m]==0) {
                        m++;
                }
                tally[votes[i][m]]++;
        }


        for(j=1;j<=num;j++) {
                if(out[j])
                        continue;
                if(tally[j] > max_num){
                        max_num=tally[j];
                        max=j;
                }
                if (tally[j] <= min_num && tally[j]) {
                        min_num=tally[j];
                }
        }
        for(j=1;j<=num;j++) {
                if (tally[j]==min_num && tally[j]) {
                        min[next++]=j;
                }
        }
        if (((double)max_num/voters) > 0.500001) {
                printf("%s", names[max]);
                return;
        }
        if (max_num == min_num) {
                for(j=1;j<=num;j++)
                        if (tally[j]==max_num) {
                                printf("%s", names[j]);
                        }
                return;
        }
        else {
                x=1;
                while (x<=num) {
                        if (min[x]!=0) {
                                out[x]=1;
                                for(i=0;i<voters;i++) {
                                        for(k=1;k<=num;k++){
                                                if(votes[i][k]==min[x]) {
                                                        votes[i][k]=0;
                        }}}}
                x++;
                }

        }
        vote(names, num, votes, voters);
}

Personal tools