10142 - Australian Voting

All about problems in Volume 101. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

User avatar
krkhan
New poster
Posts: 3
Joined: Mon Jul 07, 2008 3:09 pm
Contact:

Re: 10142 - Australian Voting

Post by krkhan » Fri Jul 11, 2008 7:07 am

Never mind. Fixed it. Actually, while taking input, the string and istringstream objects were created and destroyed on every iteration, making the whole thing very expensive w.r.t. time :) .

dynamite
New poster
Posts: 1
Joined: Sun Nov 02, 2008 7:54 pm

10142 - Australian Voting

Post by dynamite » Sun Nov 02, 2008 11:22 pm

Hi
I am facing the same problem as many others in this thread. My code for this problem got accepted on programming challenges but I get a WA on the uva judge. I get the correct outputs for all the test cases posted in this thread. Can anyone point out the faults in my code. Any help really be appreciated..Thanks

Code: Select all

#include <iostream>
#include <vector>
#include <stack>
#include <map>
#include <sstream>
using namespace std;
int compare(void const *a, void const *b)
{
	const int *ia = (const int *)a;
	const int *ib = (const int *)b;
	return (*ia - *ib);
}
int main()
{
	int tot;
	cin>>tot;
	getchar();
	if(tot>0)getchar();
	while(tot--)
	{
		char c;
		int numc,numv=0,count=0;
		cin >>numc;
		getchar();
		char names[numc][100];
		map <int, vector <int> > votemap;
		for(int i=0;i<numc;i++)gets(names[i]);
		istringstream * is;
		int votes[2000][numc];
		for(numv=0;numv<2000;numv++)
		{
			char line[100];
			gets(line);
			if(strlen(line)==0)break;
			is=new istringstream(line,istringstream::in);
			int tvote[numc];
			for(int i=0;i<numc;i++)
			{
				int temp;
				*is >> temp;
				votes[numv][i]=--temp;
				tvote[i]=temp;
			}
			qsort(tvote,numc,sizeof(int),compare);
			int flag=0;
			for(int i=0;i<numc;i++)
				if(tvote[i]!=i)
				{
					flag=1;
					--numv;
					break;
				}
			if(flag)
			{
				delete is;
				continue;
			}
			int temp=votes[numv][0];
			if(votemap.find(temp)!=votemap.end())
			{
				vector <int> list=votemap[temp];
				list.push_back(numv);
				votemap[temp]=list;
			}
			else
			{
				vector <int> list;
				list.push_back(numv);
				votemap.insert( pair <int, vector <int> > (temp,list));
			}
		}
		map <int, vector <int> >::iterator it;
		if(numv==0)
		{
			for(int i=0;i<numc;i++)
				cout<<names[i]<<endl;
			if(tot!=0)cout<<endl;
			continue;
		}
		int eliminated[numc],wincount=numv/2;
		for(int i=0;i<numc;i++)eliminated[i]=1;
		for(it=votemap.begin(); it!=votemap.end() ;it++)eliminated[it->first]=0;
		while(votemap.size()!=0)
		{
			int s=votemap.size();
			int min=INT_MAX,max=INT_MIN,size;
			stack <int> minS;
			stack <int> maxS;
			for(it=votemap.begin(); it!=votemap.end() ;it++)
			{
				vector <int> list = it->second;
				size=list.size();
				if(size<min)
				{
					while(!minS.empty())minS.pop();
					minS.push(it->first);
					min=size;
				}
				else if(size==min)minS.push(it->first);
				if(size>max)
				{
					while(!maxS.empty())maxS.pop();
					maxS.push(it->first);
					max=size;
				}
				else if(size==max)maxS.push(it->first);
			}
			if(maxS.size()==votemap.size())
			{
				stack <int> tempS;
				while(!maxS.empty())
				{
					tempS.push(maxS.top());
					maxS.pop();
				}
				while(!tempS.empty())
				{
					cout<<names[tempS.top()]<<endl;
					tempS.pop();
				}
				if(tot!=0)cout<<endl;
				break;
			}
			if(max>wincount)
			{
				stack <int> tempS;
				while(!maxS.empty())
				{
					tempS.push(maxS.top());
					maxS.pop();
				}
				while(!tempS.empty())
				{
					cout<<names[tempS.top()]<<endl;
					tempS.pop();
				}
				if(tot!=0)cout<<endl;
				break;
			}
			else
			{
				while(!minS.empty())
				{
					eliminated[minS.top()]=1;
					minS.pop();
				}
				for(int i=0;i<numc;i++)
				{
					if(eliminated[i]==1)
					{
						if(votemap.find(i)!=votemap.end())
						{
							vector <int> voters=votemap[i];
							for(int j=0;j<voters.size();j++)
							{
								for(int k=0;k<numc;k++)
								{
									if(eliminated[votes[voters[j]][k]]==0)
									{
										if(votemap.find(votes[voters[j]][k])!=votemap.end())
										{
											vector <int> list=votemap[votes[voters[j]][k]];
											list.push_back(voters[j]);
											votemap[votes[voters[j]][k]]=list;
											break;
										}
									}
								}
							}
							votemap.erase(i);
						}
					}
				}
			}
		}
	}
	return 0;
}

forcebrute
New poster
Posts: 4
Joined: Wed Dec 03, 2008 6:46 pm

Re: 10142 - Australian Voting

Post by forcebrute » Thu Dec 25, 2008 8:20 pm

10142 - Australian Voting - WA & AC Together!!

Postby N|N0 on Wed Jan 26, 2005 2:08 am
My program ACs here, but WAs at http://www.programming-challenges.com

Code: Select all

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

    #define MAX_KAND 20

    char imena[MAX_KAND][100];      
    int glasovi[1000][MAX_KAND];      
    int v_igri[MAX_KAND];         
    int glasov[MAX_KAND];         

    void prestej(int num_v, int st_kand) {
      int i, j;
      for (i=0; i<st_kand; i++) glasov[i] = 0;
      for (i=0; i<num_v; i++) {
        j = 0;
        while (v_igri[glasovi[i][j]] == 0) j++;
        glasov[glasovi[i][j]]++;
      }
      return;
    }

    int main(void) {
      int kdo, cases, st_kand, ostali, i, n, count, max, maxn, min, first = 1;
      char niz[200], *p;
      scanf("%d\n\n", &cases);      
      while (cases > 0) {          
        scanf("%d\n", &st_kand);      
        for (i=0; i<st_kand; i++) {
          gets(imena[i]);         
          v_igri[i] = 1;         
        }
        count = 0;            
        do {
          gets(niz);         
          if (strlen(niz) < 1) break;   
          p = niz;
          for (i=0; i<st_kand; i++) {   
             sscanf(p, "%d", &n);      
            while (isdigit(p[0])) p++;   
            while (isspace(p[0])) p++;
            glasovi[count][i] = n-1;
          }
          count++;            
          if (feof(stdin)) break;      
        } while (1);
        ostali = st_kand;         
        do {            
          prestej(count, st_kand);      
          max = 0;            
          kdo = 0;            
          maxn = 0;            
          min = count;         
          for (i=0; i<st_kand; i++)    
          if (v_igri[i]) {         
            if (glasov[i] > max) {
              max = glasov[i];
              kdo = i;
              maxn = 1;
            } else if (glasov[i] == max) maxn++;
            if (glasov[i] < min) min = glasov[i];
          }
          if (maxn == 1 && (1.0 * max / count) > 0.5) {   
             if (!first) putchar('\n');
             printf("%s\n", imena[kdo]);         
             first = 0;
             break;
          } else if (max == min) {
             if (!first) putchar('\n');         
            for (i=0; i<st_kand; i++)
            if (v_igri[i]) printf("%s\n", imena[i]);   
            first = 0;
            break;
          } else {                  
            for (i=0; i<st_kand; i++)
              if (v_igri[i]) {
                if (glasov[i] == min) {         
                  v_igri[i] = 0;
                  ostali--;
                }
              }
          }     
        } while (1);
        cases--;
      }
      return(0);
    }
Change the line if(feof(stdin) ) break; to if(getchar()==EOF) break;
This code will always manipulate the last case incorrectly. It will take an extra ballot same as the actual last one.
Its strange that this wrong code gives AC on UVA .
Got AC finally with the help of this code.
No need to check for invalid ballots.

tony47ch
New poster
Posts: 1
Joined: Thu Dec 04, 2008 3:09 pm

nice

Post by tony47ch » Sat Dec 27, 2008 6:04 am

nice to meet you all.

cah
New poster
Posts: 1
Joined: Thu Mar 12, 2009 5:24 am

Re: 10142 - Australian Voting

Post by cah » Thu Mar 12, 2009 5:30 am

Please.. I need some help!!

Judge gives me TLE, but I tested with many many inputs, and I have no idea what I'm doing wrong.
What input my code (in C) enters in loop?

Code: Select all

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


void eliminaCandidato(int cedula[10000][200], int candidato, int n, int m) {
    int i, j, k;

    for (i = 0; i < n; i++)
        for (j = 0; j < m; j++)
            if (cedula[i][j] == candidato) {
                for (k = j; k < m-1; k++)
                    cedula[i][k] = cedula[i][k+1];
                cedula[i][k] = -1;
            }
}

void imprimeEmpate(char nomes[200][800], int votos[200], int maxVotos, int indiceNomes) {
    int i;

    for (i = 0; i < indiceNomes; i++) 
        if (votos[i] == maxVotos)
            printf("%s\n", nomes[i]);

}

int jaEliminou(int candidato, int candidatosEliminados[200], int indiceEliminado) {
    int i;
    for (i = 0; i< indiceEliminado; i++) {
        if (candidatosEliminados[i] == candidato)
            return 1;
    }
    return 0;
}


void quebraString(char s[1000]) {
    int i, k;

    for (i = 0; s[i] != ' '; i++);
    for (k = 0; k < 999 && i < 998; k++, i++)
        s[k] = s[i+1];
}

int main() {

    int testes;
    int candidatos;

    char nomes[200][800];
    int indiceNomes;

    int cedula [10000][200];
    int indiceCedulas;

    int votos[200];
    int minVotos, maxVotos;

    int alguemGanhou;
    int candidatosEliminados[200];
    int indiceEliminado;

    char c;
    int i, j, temp;
    char s[1000];
    

    scanf("%d", &testes); /*printf("testes:%d\n", testes);*/
    for ( ; testes > 0; testes--) {

        scanf("%d", &candidatos); /*printf("-------------------------candidatos:%d\n\n", candidatos);*/
        c = getchar(); /* descarta o \n */    
        c = ',';

        /* Le o nome dos candidatos */
        indiceNomes = 0;
        for ( ; candidatos > 0; candidatos--) {
            fgets(nomes[indiceNomes], 100, stdin);
            nomes[indiceNomes][strlen(nomes[indiceNomes])-1] = '\0';
            indiceNomes++;
        }
    
        for (i=0; i < indiceNomes; i++) {
            candidatosEliminados[i] = 30;
        }


        /* le as cedulas de votacao */
        indiceCedulas = 0;
        while (1) {
            fgets(s, 1000, stdin);
            if (s[0] != '\n') {

                for (i = 0; i < indiceNomes; i++) {
                    sscanf(s, "%d", &temp);
                    cedula[indiceCedulas][i] = --temp;
                    quebraString(s);
                }
                indiceCedulas++;
            }
            else 
                break;
        }

/*        for (i = 0; i < indiceCedulas; i++) {
            printf(">");
            for (j = 0; j < indiceNomes; j++)
                printf("%d ", cedula[i][j]);
            printf("\n");
        }
*/

        
        alguemGanhou = 0;
        indiceEliminado = 0;
        while (!alguemGanhou) {

            /* conta numero de votos de cada um */
            for (i=0; i < indiceNomes; i++) 
                votos[i] = 0;
    
            for (i = 0; i < indiceCedulas && cedula[i][0] != -1; i++) 
                votos[cedula[i][0]]++;
    
/*            for (i = 0; i < indiceNomes; i++) {        
                printf("%s %d\n", nomes[i], votos[i]);
            }
            printf("\n");
*/   
            /* verifica se tem ganhador */
            minVotos = 10000;
            maxVotos = 0;
            for (i = 0; i < indiceNomes; i++) { 
                if (votos[i] >= indiceCedulas/2+1) {
                    alguemGanhou = 1;
                    printf("%s\n", nomes[i]);
                }
        
                if (minVotos > votos[i] && !jaEliminou(i, candidatosEliminados, indiceEliminado))
                    minVotos = votos[i];
                if (maxVotos < votos[i])
                    maxVotos = votos[i];
            }
    
            if (!alguemGanhou) {
                if (minVotos == maxVotos) {
                    imprimeEmpate(nomes, votos, maxVotos, indiceNomes);
                    alguemGanhou = 1;
                    break;
                }
                for (i = 0; i < indiceNomes; i++) 
                    if (votos[i] == minVotos) { 
                        if (!jaEliminou(i, candidatosEliminados, indiceEliminado)) {
                            eliminaCandidato(cedula, i, indiceCedulas, indiceNomes);            
                            candidatosEliminados[indiceEliminado++] = i;          
                        }
                    }
/*                for (i = 0; i < indiceCedulas; i++) {
                    printf(">>");
                    for (j = 0; j < indiceNomes; j++)
                        printf("%d ", cedula[i][j]);
                    printf("\n");
                } */
            }

        }

        if (testes != 1) 
            printf("\n");
    }
    
    return 0;
}

iit2006015
New poster
Posts: 4
Joined: Fri Jul 18, 2008 9:44 pm

Re: 10142 - Australian Voting

Post by iit2006015 » Sat May 30, 2009 4:01 pm

Got Accepted in http://www.programming-challenges.com/ but Wrong Answer in UVA , help needed

Code: Select all

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include<string>
#include<fstream>
#define MAX 1000001
#define eps 1e-9
//#define cin fin
//#define cout fout
using namespace std;
string i2s(int n)
{  stringstream ss;
   ss<<n;
   return ss.str();  
}
int s2i(string h)
{   stringstream ss;
    ss<<h;
    int n;
    ss>>n;
    return  n;
} 
int main()
{  int t;
   //fstream cin;cin.open("d.txt",ios::in);
   //fstream cout;cout.open("d1.txt",ios::out);
   cin>>t;
   while(t--)
   {   int n;
       cin>>n;string l11="";getline(cin,l11);
       vector<string> re;re.clear();
       for(int i=0;i<n;i++)
       {   string h1="";getline(cin,h1);
           re.push_back(h1);
       }
       string bal="";
       int votes[1000][n];memset(votes,0,sizeof(votes));
       int cnt=0;
       //string l1="";getline(cin,l1);
       while(getline(cin,bal))
       {   if(bal=="")
           {  break;  // case of the next test cases 
           }
           else
           {    stringstream ss;ss<<bal;
                
                
                int num;int k1=0;
                while(ss>>num)
                {  votes[cnt][k1]=num;k1++;
                }
                cnt++;
                
                
            }
       }
       
       
       
       // case of the no of votes  cnt   can be used to see 50 % criterion 
       // now the case of the counting 
       vector<int> count1(n,0);
       for(int i=0;i<cnt;i++)
       {  count1[votes[i][0]-1]++; 
       }
       bool flag=true;
       while(flag)
       {   
          /* cout<<"counts ";
           
           for(int i=0;i<n;i++)
           {  cout<<count1[i]<<" ";
           }*/
            
           
           int value=*min_element(count1.begin(),count1.end());   // case of the minimum has been calculated 
           
           int no_can=count(count1.begin(),count1.end(),value);  // no_can with that much less votes
           
           //cout<<"value "<<value<<" "<<no_can;
           
           //case of the highest no of the votes 
           int max1=0;int index=-1;
           for(int i=0;i<n;i++)
           {    if(count1[i]!=10000 && count1[i]>max1)
                {  max1=count1[i]; 
                   index=i;
                }
           }
           
          // cout<<" index "<<index<<endl;
           
           double per=((double)max1/(double)cnt)* (double)100;
           
          // cout<<" per "<<per<<endl;
           
           if(((double)per-(double)50)>eps)
           {   flag=false;
               cout<<re[index]<<endl;
               if(t!=0)cout<<endl;
               continue;
           }
           
           //int y4;cin>>y4;
           
           // now the case of number nonelimeinated candidates 
           int no_noneli=0;
           for(int i=0;i<n;i++)
           {  if(count1[i]!=10000)
              {  no_noneli++;
              }
           }
           if(no_can==no_noneli)
           {   // means all are tied at the lowest 
               flag=false;
               for(int i=0;i<n;i++)
               {   if(count1[i]==value)
                   {   cout<<re[i]<<endl; 
                   } 
               } 
               if(t!=0)
               {
               cout<<endl;
               }
           }
           else
           {  // only few are at lowest rest are not 
              for(int i=0;i<n;i++)
              {   if(count1[i]==value)  
                  {   // case of this to be eliminated
                      count1[i]=10000;  // eliminated 
                      for(int j=0;j<cnt;j++)
                      {   if(votes[j][0]==i+1)
                          {   // case of giving to next non eliminated 
                              for(int k=1;k<n;k++)
                              {  if(count1[votes[j][k]-1]!=10000 && count1[votes[j][k]-1]!=value)
                                 { count1[votes[j][k]-1]++;
                                   break;
                                 }
                              }
                           }
                      }
                  }
              }
           }
       }
   }    
   system("pause");
}

PxM
New poster
Posts: 1
Joined: Wed Jun 24, 2009 7:30 pm

Re: Why Invalid Memory Reference?? Help me...

Post by PxM » Thu Jun 25, 2009 10:40 pm

I fail to understand why should we ignore the last ballot.

If consider all ballots, the output must be bijon only.

I believe ignoring the last ballot is wrong. If the judge follows your answer, then the judge must be wrong as well.

When I try to ignore the last vote, I still got wrong answer. However, the time taken this time was longer, which I assumed that it passed one more test case.
Therefore I can consider that the judge was wrong. So the results it generates are not reliable.

Can anyone explain why the answer is

Code: Select all

jalal
bijon
in this test case:

Code: Select all

4
jalal
hasan
bijon
saiket
1 2 3 4
3 1 2 4
1 2      3 4
2 1  3 4
3 1 2 4
4 3        1 3

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 10142 - Australian Voting

Post by Obaida » Thu Jul 23, 2009 4:54 am

Still i can't figure out why Wa..! I checked all the case :(
Some one plz post some tricky case? to help me check my code.

Code: Select all

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

int main()
{
	int c,n,choice[1001][21],i,j,k,l,len,vote[21],max,min,col[1001],temp[21];
	char st[21][81],inpt[6],line[201];
	bool update,fail[21];
	gets(inpt);
	c = atoi(inpt);
	while(c--)
	{
		while(1){gets(inpt);if(inpt[0]!=0)break;}
		n = atoi(inpt);
		for(i=0;i<n;i++)gets(st[i]);
		i=0;
		while(gets(line))
		{
			if(line[0]==0)break;len = strlen(line);l=0;k=0;
			for(j=0;j<len;j++)
			{
				if(isdigit(line[j]))inpt[k++]=line[j];
				if((isspace(line[j])&&isdigit(line[j-1]))||j==len-1){inpt[k]=NULL;choice[i][l++]=atoi(inpt);k=0;}
			}
			i++;
		}
		for(j=0;j<n;j++){vote[j]=-1;fail[j]=0;}
		for(j=0;j<i;j++){vote[choice[j][0]-1]++;col[j]=0;}
		while(1)
		{
			max=-1;min=1001;
			for(j=0;j<n;j++){if(vote[j]>max)max=vote[j];if(vote[j]<min&&vote[j]>-1)min=vote[j];if(vote[j]==-1)fail[j]=1;}
			if((max+1)*2>i)break;
			else
			{
				update=0;for(j=0;j<n;j++)temp[j]=0;
				for(j=0;j<n;j++)
				{
					if(vote[j]==min)
					{
						for(k=0;k<i;k++)
						{
							if(choice[k][col[k]]==j+1&&col[k]+1<n)
							{
								len = choice[k][++col[k]]-1;
								if(fail[len]!=1)
									temp[len]++;
								update=1;
							}
						}
						if(max!=min)fail[j]=1;
					}
				}
				if(!update)break;
				for(j=0;j<n;j++)if(temp[j])vote[j]+=temp[j];
			}
		}
		for(j=0;j<n;j++)if(vote[j]==max&&!fail[j])printf("%s\n",st[j]);
		if(c)puts("");
	}
	return 0;
}
try_try_try_try_&&&_try@try.com
This may be the address of success.

olivier
New poster
Posts: 1
Joined: Wed Nov 04, 2009 10:35 am

10142 - Input error

Post by olivier » Wed Nov 04, 2009 10:50 am

Hi all,

I keep getting Runtime Error on this problem, and I've tracked it down to my input handling code. Here is a stripped down version (plain C) that just reads the input and doesn't output anything; it should get WA but gets RE.

Precisely, the error happens when I tokenize the poll lines (on spaces) and try reading integers.

Obviously, this works like a charm on my machine (ubuntu, gcc 4.3.3) for any test data that I've seen on the forum.

Does anyone have a clue? I haven't been coding C for a long time, so I may have missed something...

Code: Select all

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

#define MAX_CANDIDATES 20
#define MAX_LINE_SIZE 256

int numCandidates;

int main() {
	char line[MAX_LINE_SIZE];
	char* token;
	int i, numCases;

	/* Number of cases */
	if (fgets(line, sizeof line, stdin) == NULL) return 1; 
	if (sscanf(line, "%d", &numCases) != 1) return 1;

	/* Empty line */
	if (fgets(line, sizeof line, stdin) == NULL) return 1; 

	while (numCases-- > 0) {
		/* Number of candidates */
		if (fgets(line, sizeof line, stdin) == NULL) return 1; 
		if (sscanf(line, "%d", &numCandidates) != 1) return 1;

		/* Candidate names */
		for (i = 0; i < numCandidates; i++) {
			if (fgets(line, sizeof line, stdin) == NULL) return 1; 
			if (sscanf(line, "%*80[^\n]") != 0) return 1;
		}
	
		/* Polls : read the whole line and then tokenize it */
		int c;
		while (fgets(line, sizeof line, stdin) != NULL
			&& line[0] != '\n') {
			token = (char*) strtok(line, " ");
			/* RUNTIME ERROR HAPPENS HERE */
			if (sscanf(token, "%d", &c) != 1) return 1;
			
			for (i = 1; i < numCandidates; i++) {
				token = (char*) strtok(NULL, " ");
				if (sscanf(token, "%d", &c) != 1) return 1;
			}
		}
		/* Empty line between each case */
		if (numCases > 0) printf("\n");
	}
	return 0;
}
TIA,
Olivier

jcxavier
New poster
Posts: 1
Joined: Mon May 17, 2010 11:48 pm

10142 - Australian Voting - TLE

Post by jcxavier » Mon May 17, 2010 11:51 pm

Hello everyone,

Even though I've tried all the test cases I've found here, my code still returns me a TLE, and I tried it on P-C too (time limit: 10 sec).
I'm pretty sure that's not the algorithm's fault, so it might enter in an infinite loop which I have yet to find.

Any help on this matter would be appreciated! Below is my code:

Code: Select all

// Author: João Xavier
// Date: 17-05-2010

/*	@JUDGE_ID:	'00000'	10142	C++	"Australian Voting"	*/

/*	@BEGIN_OF_SOURCE_CODE	*/

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;

int main()
{
	int candidateVoteCount[21];
	int candidateVotes[1001][42];
	char candidateNames[21][128];

	int n;
	char line[128];

	for (scanf("%d", &n); n; n--)
	{
		int totalCandidates = 0, totalBallots = 0;

		memset(candidateVoteCount, 0, sizeof(int)*21);
		memset(candidateVotes, 0, sizeof(int)*1001*42);
		memset(candidateNames, 0, sizeof(char)*21*128);

		scanf("%d", &totalCandidates);

		for (int i = 0; i <= totalCandidates; i++)
			cin.getline(candidateNames[i], 128);

		cin.getline(line, 128);
		while (line[0])
		{
			if (cin.eof())
				break;

			candidateVotes[++totalBallots][1] = atoi(strtok(line, " "));

			for (int i = 2; i <= totalCandidates; i++)
				candidateVotes[totalBallots][i] = atoi(strtok(NULL, " "));

			cin.getline(line, 128);
		}

		bool winnerFound = false;
		while (!winnerFound)
		{
			int max = 0, min = 21;

			for (int i = 1; i <= totalCandidates; i++)
				if (candidateVoteCount[i] != -1)
					candidateVoteCount[i] = 0;

			for (int i = 1; i <= totalBallots; i++)
				candidateVoteCount[candidateVotes[i][1]]++;

			for (int i = 1; i <= totalCandidates; i++)
			{
				if (candidateVoteCount[i] > max)
					max = candidateVoteCount[i];

				if ((candidateVoteCount[i] != -1) && (candidateVoteCount[i] < min))
					min = candidateVoteCount[i];
			}

			if ((max == min) || (((float)max / (float)totalBallots) > 0.5f))
			{
				for (int i = 1; i <= totalCandidates; i++)
					if (candidateVoteCount[i] == max)
						printf("%s\n", candidateNames[i]);

				winnerFound = true;
			}
			else
			{
				for (int i = 1; i <= totalCandidates; i++)
					if (candidateVoteCount[i] == min)
					{
						for (int j = 1; j <= totalBallots; j++)
							for (int k = 1; k <= totalCandidates; k++)
								if (candidateVotes[j][k] == i)
									memcpy(candidateVotes[j] + k, candidateVotes[j] + k + 1, sizeof(int)*totalCandidates);

						candidateVoteCount[i] = -1;
					}
			}
		}

		if (n != 1)
			putchar('\n');
	}

	return 0;
}

/*	@END_OF_SOURCE_CODE	*/

kenjush
New poster
Posts: 2
Joined: Sat Jul 31, 2010 5:12 pm

10142 - Australian Voting & java

Post by kenjush » Sat Jul 31, 2010 5:19 pm

hi
I code in java!
I wondered if on the last line of last test case there is a '\n' character or not?!
I mean my code runs fine on all test cases on the form of:

Code: Select all

.
.
2 3 1
1 2 3

but if input comes in the form of sth linke this:

Code: Select all

.
.
1 3 2
1 2 3
it gives wrong answer!

and another question?!
in the state of tied votes, should I write them in any order or as they appeared in input?!
Last edited by kenjush on Sat Jul 31, 2010 6:03 pm, edited 1 time in total.

kenjush
New poster
Posts: 2
Joined: Sat Jul 31, 2010 5:12 pm

Re: 10142 - Australian Voting & java

Post by kenjush » Sat Jul 31, 2010 6:02 pm

never mind! I finally got AC!
I had made a mistake in finding the minimum votes! :P

mpi
New poster
Posts: 46
Joined: Fri Nov 03, 2006 7:53 pm
Location: Madrid

Re: 10142 - Australian Voting

Post by mpi » Thu Aug 05, 2010 12:40 pm

Hi everybody

I've been trying to get this problem AC for a few days now and there is no way. My solution is really simple, as I think the problem is too, but no matter how hard I try I can't find out what I'm doing wrong.

What if there's no ballots?
I guess all the candidates tie with 0 votes and you have to print all their names.

Maybe I'm misunderstanding the logic of the problem. For example, if I have a ballot like this:
2 3 1 4
and candidate 2 is eliminated, then I have to add 1 vote to candidate 3 unless this one is eliminated too. If that's the case, I check candidates 1 and 4 in order until I find the one who's not eliminated. Am I right?

On the other hand, I may read input data wrong. Here's how I do it:

Code: Select all

cin >> t;
while (t--)
{
    cin >> c;
    cin.ignore();
    for (i = 0; i < c; ++i)
    {
        getline(cin, names[i]);
    }
    while (getline(cin, ballot) && ballot != "")
    {
    }
}
Anyone?

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Re: 10142 - Australian Voting

Post by sohel » Thu Aug 05, 2010 10:35 pm

You can use the UVA Toolkit Site to test your code with your own test cases.

mpi
New poster
Posts: 46
Joined: Fri Nov 03, 2006 7:53 pm
Location: Madrid

Re: 10142 - Australian Voting

Post by mpi » Fri Aug 06, 2010 1:19 pm

Thanks sohel. Very useful tool.
I managed to find an error: I wasn't marking all the new eliminated candidates before giving away their ballots, so I could give a ballot to a candidate who was going to be eliminated later in the same iteration :oops:
Anyway, I'm still getting WA, don't know why and I'm sick of trying such an easy problem (no offense).

Post Reply

Return to “Volume 101 (10100-10199)”

Who is online

Users browsing this forum: No registered users and 1 guest