10374 - Election
Moderator: Board moderators
-
- New poster
- Posts: 5
- Joined: Tue Aug 27, 2002 7:46 pm
- Location: Russia
- Contact:
10374 - Election
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.
May be there are some situations, in case of wich my program works wrong.
-
- New poster
- Posts: 10
- Joined: Tue Oct 01, 2002 11:37 pm
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.)
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;
}
-
- New poster
- Posts: 5
- Joined: Tue Aug 27, 2002 7:46 pm
- Location: Russia
- Contact:
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]
[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]
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];
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];
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:
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;
}
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;
}
-
- Experienced poster
- Posts: 183
- Joined: Thu Nov 11, 2004 12:35 pm
- Location: AIUB, Bangladesh
10374
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?
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
-
- Learning poster
- Posts: 70
- Joined: Sat Feb 05, 2005 9:38 am
- Location: Gurukul
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.
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 ....
-
- Experienced poster
- Posts: 183
- Joined: Thu Nov 11, 2004 12:35 pm
- Location: AIUB, Bangladesh
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?
i got wrong answer even with a simple linear search!!!
![:x](./images/smilies/icon_mad.gif)
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
-
- Experienced poster
- Posts: 183
- Joined: Thu Nov 11, 2004 12:35 pm
- Location: AIUB, Bangladesh
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](./images/smilies/icon_mad.gif)
![:)](./images/smilies/icon_smile.gif)
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](./images/smilies/icon_mad.gif)
Jalal : AIUB SPARKS
Re: 10374 - Election
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?
Thanks for any help.
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;
}