10374 - Election

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

Moderator: Board moderators

Vartanov Daniel
New poster
Posts: 5
Joined: Tue Aug 27, 2002 7:46 pm
Location: Russia
Contact:

10374 - Election

Post by Vartanov Daniel » Wed Nov 06, 2002 3:04 pm

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
New poster
Posts: 10
Joined: Tue Oct 01, 2002 11:37 pm

Post by Santiago Zanella » Thu Nov 07, 2002 3:45 am

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
New poster
Posts: 26
Joined: Thu Aug 08, 2002 8:04 am

Post by Mahbub » Thu Nov 07, 2002 5:30 am

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
New poster
Posts: 5
Joined: Tue Aug 27, 2002 7:46 pm
Location: Russia
Contact:

Post by Vartanov Daniel » Thu Nov 07, 2002 7:42 am

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.votes = 0;
parties.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.name, name) == 0) return i;
return -1;
}

int findparty(char name[80])
{
for (int i = 0; i <= partynum - 1; i++)
if (strcmp(parties.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.name);
gets(cand.party);
if (! strcmp(cand.party, "independent"))
{
strcpy(parties[partynum++].name, cand.name);
strcpy(cand.party, cand.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
Problemsetter & Reviewer
Posts: 194
Joined: Fri Mar 15, 2002 2:00 am
Contact:

Post by gvcormac » Thu Nov 07, 2002 9:50 am

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
Learning poster
Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien
Contact:

Post by technobug » Fri Feb 11, 2005 3:18 am

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
Learning poster
Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien
Contact:

Post by technobug » Fri Feb 11, 2005 3:19 am

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);
getl(p[par]);
// cout << d << " - " << p[par] << endl;
for(j=0;j<par;j++) {
if(strcmp(p[j],p[par])==0) { dp = j; goto nex; }
}
dp = par++;
nex:;
}

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

int maxi = *max_element(vot,&vot[par]);
int n = -1;
for(i=0;i!=par;i++){
if(vot==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
Learning poster
Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien
Contact:

Post by technobug » Fri Feb 11, 2005 3:19 am

Either tests or suggestions are welcome....

User avatar
CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Location: AIUB, Bangladesh

10374

Post by CodeMaker » Sun Jul 10, 2005 6:37 pm

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

		

Jalal : AIUB SPARKS

Raj Ariyan
Learning poster
Posts: 70
Joined: Sat Feb 05, 2005 9:38 am
Location: Gurukul

Post by Raj Ariyan » Sun Jul 10, 2005 9:50 pm

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.
Some Love Stories Live Forever ....

User avatar
CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Location: AIUB, Bangladesh

Post by CodeMaker » Mon Jul 11, 2005 6:52 pm

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.
Jalal : AIUB SPARKS

User avatar
CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Location: AIUB, Bangladesh

Post by CodeMaker » Tue Jul 12, 2005 3:05 pm

I cant believe!!!
i got wrong answer even with a simple linear search!!! :x
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;
}

		

Jalal : AIUB SPARKS

dip
New poster
Posts: 7
Joined: Sat Nov 20, 2004 10:20 am
Location: Dhaka
Contact:

Hi

Post by dip » Tue Jul 12, 2005 6:17 pm

:D
Last edited by dip on Thu Jul 14, 2005 4:49 pm, edited 1 time in total.
something .....

User avatar
CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Location: AIUB, Bangladesh

Post by CodeMaker » Wed Jul 13, 2005 7:05 pm

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 :x
Jalal : AIUB SPARKS

pcp190
New poster
Posts: 1
Joined: Sat Aug 08, 2009 11:39 pm

Re: 10374 - Election

Post by pcp190 » Sat Aug 08, 2009 11:47 pm

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.

Post Reply

Return to “Volume 103 (10300-10399)”