10142 - Australian Voting

[krkhan]

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]

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]

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]

nice to meet you all.

[cah]

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]

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]

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]

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;
}

[olivier]

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]

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]

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?!

[kenjush]

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

[mpi]

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?

[sohel]

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

[mpi]

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
Anyway, I'm still getting WA, don't know why and I'm sick of trying such an easy problem (no offense).