10374 - Election

[Vartanov Daniel]

I really don't know, where I have mistake. Can anyone write some tests?
May be there are some situations, in case of wich my program works wrong.

[Santiago Zanella]

There is no trick.
I think I can hardly help you posting some input/output sets here.
If your algorithm manage ties correctly, the only thing left to do is to check input reading and reinitialization after each case. Remember you should be careful if you're mixing scanf and gets.

[Mahbub]

As this problem has really no trick i think its not bad idea to post my code her...
u can compare ur output with mines..(by fc or else.)

Code: Select all


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

struct S
{
   char cand[100];
   char party[100];
   int vote;
} list[20000];

int cmpf(const void *a, const void *b)
{
   S *s1 = (S*)a;
   S *s2 = (S*)b;

   return strcmp(s1->cand,s2->cand);
}

int main()
{
   char s[500];
   int i,j,n,c,case_no,m,l,h,r,max,t,M;

/*   freopen("C.txt","r",stdin);  */
   scanf("%d\n",&case_no);

   for(c=0; c<case_no; c++)
   {
      
      scanf("%d\n",&n);

      for(i=0; i<n; i++)
      {
         gets(list[i].cand);
         gets(list[i].party);
      }

      for(i=0; i<n; i++)
      {
         list[i].vote = 0;      
      }

      qsort((void*)list,n,sizeof(list[0]),cmpf);

      scanf("%d\n",&M);

      for(i=0; i<M; i++)
      {
         gets(s);

         l = 0;
         h = n;

         while(l<=h)
         {
            m = (l+h)/2;

            r = strcmp(s,list[m].cand);

            if(r>0)
               l = m + 1;
            else if(r<0)
               h = m - 1;
            else
            {
               list[m].vote++;
               break;
            }
         }
      }

      max = -1;

      for(i=0; i<n; i++)
         if(list[i].vote>max)
         {
            j = i;
            max = list[i].vote;
         }

      t = 0;
      for(i=0; i<n; i++)
      {
         if(i!=j && max==list[i].vote)
         {
            t = 1;
            printf("tie\n");
            break;
         }
      }

      if(!t)
      {   
         printf("%s\n",list[j].party);
      }

      if(c<case_no-1)
      {
         printf("\n");
      }
   }
   return 0;
}


[Vartanov Daniel]

Hmm, i think, i shouldn't have problems with scanf\gets, looak at this:

[cpp]
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int n, m;
int partynum;

struct Tparty
{
char name[80];
int votes;
int independ;
} parties[20];

struct Tcand
{
char name[80];
char party[80];
int votes;
} cand[20];

int cmpPart(const void* a, const void* b)
{
Tparty bir, eki;
bir = *(Tparty *)a;
eki = *(Tparty *)b;
return bir.votes - eki.votes;
}

void Init()
{
/* for (int i = 0; i <= 19; i++)
{
cand[i].votes = 0;
parties[i].votes = 0;
}*/
memset(parties, 0, sizeof(parties));
memset(cand, 0, sizeof(cand));
}

int findcand(char name[80])
{
for (int i = 0; i <= n - 1; i++)
if (strcmp(cand[i].name, name) == 0) return i;
return -1;
}

int findparty(char name[80])
{
for (int i = 0; i <= partynum - 1; i++)
if (strcmp(parties[i].name, name) == 0) return i;
return -1;
}

int main()
{
#ifndef ONLINE_JUDGE
*stdin = *fopen("input.txt", "rt");
#endif
int tstnum;
scanf("%d", &tstnum);
while (tstnum--)
{
Init();
char tmpstr[80];
partynum = 0;
scanf("%d\n", &n);
for (int i = 0; i <= n - 1; i++)
{
gets(cand[i].name);
gets(cand[i].party);
if (! strcmp(cand[i].party, "independent"))
{
strcpy(parties[partynum++].name, cand[i].name);
strcpy(cand[i].party, cand[i].name);
parties[i].independ = 1;
}
else
if (findparty(cand[i].party) == -1)
strcpy(parties[partynum++].name, cand[i].party);
}
scanf("%d\n", &m);
for (i = 0; i <= m - 1; i++)
{
gets(tmpstr);
if (findcand(tmpstr) != -1) cand[findcand(tmpstr)].votes++;
}
for (i = 0; i <= n - 1; i++)
parties[findparty(cand[i].party)].votes += cand[i].votes;
qsort((void *)parties, partynum, sizeof(parties[0]), cmpPart);
if (parties[partynum - 1].votes == parties[partynum - 2].votes)
printf("tie\n");
else
printf("%s\n",
(parties[partynum - 1].independ) ? "independent" : parties[partynum - 1].name);
if (tstnum)
printf("\n");
}
return 0;
}

[/cpp]

[gvcormac]

I don't fully understand your code (it is much more complicated than it needs to be). However I can point out a couple of problems:

1. max input line length is 80. char[80] is not big enough because C puts a null at the end of strings.

2. you seem to use the candidate's name as the party name, in the case that the candidate is independent. What if there is a real party with this name?

In general, why don't you: find the winning candidate; print the party of the winning candidate. No need to count the votes for the party.



[quote="Vartanov Daniel"]Hmm, i think, i shouldn't have problems with scanf\gets, looak at this:

[cpp]
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int n, m;
int partynum;

struct Tparty
{
char name[80];
int votes;
int independ;
} parties[20];

[technobug]

I must be missing something here.... I tried this one twice.... first time, wrong answer, rewrote it from scratch, WA again... its easy, I just did what they said...

First one is here:

Code: Select all


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

int main() {

   int i,j,k,l,m,n,o,p;
   char part[30][100];
   char cand[30][100];
   bool val[30];
   int  capa[30];
   int  voto[30];
   int cand_c;
   char s[100];

   scanf("%d\n",&p);
   while(p--) {

      scanf("%d\n",&cand_c);
      for(i=0;i!=cand_c;i++) {
         gets(cand[i]);
         gets(part[i]);
      }

      // candidates
      for(i=0;i!=cand_c;i++) val[i]=0;
      for(i=0;i!=cand_c;i++) {
         for(j=0;j!=cand_c;j++) {
            if(strcmp(part[j],part[i])==0) {
               capa[i]=j;
               val[j]=1;
               break;
            }
         }
      }

      scanf("%d\n",&o);
      for(i=0;i!=cand_c;i++) voto[i]=0;

      // votes, please
      while(o--) {
         gets(s);
         for(i=0;i!=cand_c;i++) {
            if(strcmp(cand[i],s)==0) {
               voto[capa[i]]++;
               break;
            }
         }
      }

      j=0;
      // finds the maximum voted
      for(i=1;i<cand_c;i++) if(val[i] && voto[i]>voto[j]) j = i;

      // is it a tie?
      for(i=0;i<cand_c;i++) {
         if(val[i] && i!=j && voto[i]==voto[j]) {
            printf("tie\n");
            goto nex;
         }
      }

      // not a tie, go ahead
      printf("%s\n",part[j]);
      
      nex:
      if(p) printf("\n");

   }
   return 0;

}



[technobug]

seconds one is here:

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

using namespace std;

int dep, par;
char d[30][100];
int dp[30];
int vot[30];
char p[30][100];

char *getl(char *s) {
gets(s);
int len = strlen(s);
while(len && (s[len-1]==13 || s[len-1]==10)) { s[--len]='\0'; }
return s;
}

void st() {

int i,j,k;
dep = par = 0;
scanf("%d\n",&dep);
for(i=0;i<dep;i++) {
getl(d[i]);
getl(p[par]);
// cout << d[i] << " - " << p[par] << endl;
for(j=0;j<par;j++) {
if(strcmp(p[j],p[par])==0) { dp[i] = j; goto nex; }
}
dp[i] = par++;
nex:;
}

for(i=0;i!=par;i++) vot[i]=0;
scanf("%d\n",&k);
char s[200];
while(k--) {
getl(s);
for(i=0;i<dep;i++) if(!strcmp(d[i],s)) { vot[dp[i]]++; break; }
}

int maxi = *max_element(vot,&vot[par]);
int n = -1;
for(i=0;i!=par;i++){
if(vot[i]==maxi) {
if(n!=-1) goto tie;
else n = i;
}
}
cout << p[n] << endl;
return;

tie:cout << "tie" << endl;


}

int main() {

int t;
scanf("%d\n",&t);
while(t--) {
st();
if(t) cout << endl;}

return 0;

}

[technobug]

Either tests or suggestions are welcome....

[CodeMaker]

the problem is simple, clear and high accepted rate, it was really hard to believe when i got WA.
doesn't my code so simple, i could have used STL-map, and i will do it next may be, but i want to know why it is not working? m i missing some?

Code: Select all

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
struct combo
{
   char name[500];
   char party[500];
   int count;
};
combo list[100];
int cmp(const void *a,const void *b)
{
   combo *p=(combo*)a;
   combo *q=(combo*)b;

   return strcmp(p->name,q->name);
}
int cmp2(const void *a,const void *b)
{
   combo *p=(combo*)a;
   combo *q=(combo*)b;

   return q->count-p->count;
}
int main()
{
   combo *ptr;
   int cases,i,n,m;
   char vote[1000000];
//   freopen("in.in","r",stdin);
   scanf("%d",&cases);
   while(cases--)
   {
      scanf("%d",&n);
      getchar();
      for(i=0;i<n;i++)
      {
         gets(list[i].name);
         gets(list[i].party);
         list[i].count=0;
      }
      qsort(list,n,sizeof(list[0]),cmp);
      scanf("%d",&m);
      getchar();
      for(i=0;i<m;i++)
      {
         gets(vote);
         ptr=(combo*)bsearch(vote,list,n,sizeof(list[0]),cmp);

         if(ptr!=NULL)
         {
            list[ptr-list].count++;
         }
      }
   
      qsort(list,n,sizeof(list[0]),cmp2);
      if(list[0].count>list[1].count)
         puts(list[0].party);
      else
         puts("tie");
      if(cases)
         printf("\n");
   }
   return 0;
}

      



[Raj Ariyan]

Hi CodeMaker,
I've checked with random input. Unfortunately i didnt get any wrong output. By the way, try to use MAP STL, then it becomes very easy. This problem doesnt have any tricky input. So dont need to use such a large size of array. For name i used 85 only and there are only <=20 party.

[CodeMaker]

thanks raj, i wanted to make things sure thats why used it. i can use STL, i wanted to see the bug. i will replace the bsearch will my own code and see what happens.

[CodeMaker]

I cant believe!!!
i got wrong answer even with a simple linear search!!!
is there no way to solve it without using a STL-map? if so then why?

Code: Select all

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
struct combo
{
   char name[500];
   char party[500];
   int count;
};
combo list[100];

int cmp2(const void *a,const void *b)
{
   combo *p=(combo*)a;
   combo *q=(combo*)b;

   return q->count-p->count;
}
int main()
{
   int cases,i,j,n,m;
   char vote[1000000];
//   freopen("in.in","r",stdin);
   scanf("%d",&cases);
   while(cases--)
   {
      scanf("%d",&n);
      getchar();
      for(i=0;i<n;i++)
      {
         gets(list[i].name);
         gets(list[i].party);
         list[i].count=0;
      }
      
      scanf("%d",&m);
      getchar();
      for(i=0;i<m;i++)
      {
         gets(vote);

         for(j=0;j<n;j++)
         {
            if(strcmp(vote,list[j].name)==0)
            {
               list[j].count++;
               break;
            }
         }
      }
   
      qsort(list,n,sizeof(list[0]),cmp2);
      if(list[0].count>list[1].count)
         printf("%s\n",list[0].party);
      else
         printf("tie\n");
      if(cases)
         printf("\n");
   }
   return 0;
}

      



[dip]

[CodeMaker]

my dear friend, thank you for your help.

actually the problem is not in n==1, because the problem description clearly says that n>=2.

the fact is, the judge input file has some extra spaces followed by n and m. thats why i got wrong answer.

" No lines contain leading or trailing blanks." was this a joke or something

[pcp190]

I was working on this problem and I keep getting WA. I took care of the potential trailing spaces and everything. Does anybody have any ideas about this code?

Code: Select all

#include <iostream>
#include <string>
#include <cctype>
using namespace std;

struct Candid
{
    string name, party;
    int number;
};

int main ()
{
    int i, j, k, l, x, n, m;
    Candid stuff [20];
    string temp;
    bool first = true, tie;
    ofstream fout;
   
    cin >> x;
    cin.get();
    for (m = 0; m < x; m++) {
        if (!first) {
            fout << endl;
        }
        else {
            first = false;
        }
        while (isspace(cin.peek())) {
            cin.get();
        }
        cin >> n;
        while (isspace(cin.peek())) {
            cin.get();
        }
        for (i = 0; i < n; i++) {
            stuff[i].number = 0;
            stuff[i].name = "";
            stuff[i].party = "";
            while (cin.peek() != '\n') {
                stuff[i].name += tolower(cin.peek());
                cin.get();
            }
            cin.get();
            while (cin.peek() != '\n') {
                stuff[i].party += cin.peek();
                cin.get();
            }
            cin.get();
        }
        while (isspace(cin.peek())) {
            cin.get();
        }
        cin >> l;
        while (isspace(cin.peek())) {
            cin.get();
        }
        for (i = 0; i < l; i++) {
            temp = "";
            while (cin.peek() != '\n') {
                temp += tolower(cin.peek());
                cin.get();
            }
            cin.get();
            for (j = 0; j < n; j++) {
                if (temp == stuff[j].name) {
                    stuff[j].number++;
                }
            }
        }
        tie = true;
        j = stuff[0].number;
        k = 0;
        for (i = 0; i < n; i++) {
            if (stuff[i].number != j) {
                tie = false;
            }
        }
        if (tie) {
            cout << "tie\n";
        }
        else {
            for (i = 0; i < n; i++) {
                if (j <= stuff[i].number) {
                    j = stuff[i].number;
                    k = i;
                }
            }
            cout << stuff[k].party << endl;
        }
    }
    return 0;
}



Thanks for any help.