OJ Board

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

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

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

Code: Select all

jalal
bijon

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

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

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

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	*/

Code: Select all

.
.
2 3 1
1 2 3

Code: Select all

.
.
1 3 2
1 2 3

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 != "")
    {
    }
}