I have debugged it for a long time, still WA, could any kind person help me to fix it or find out a problematic test case? Many Many THANKS!
[cpp]
// @begin_of_source_code
#include <stdio.h>
#include <stdlib.h>
void main() {
char line[60], name[20][81], list[1000][21];
int box[20], a, vote, n, m, i, j, k, max, min, same, left;
scanf("%d", &n);
for (; n>0; n--) {
scanf("%d", &m);
gets(line);
for (i=0; i<m; i++)
gets(name);
vote=0;
while ((gets(line)!=NULL) && (line[0]!='\0')) {
k=0;
for (j=0; j<m; j++) {
for (; (line[k]<'0') || (line[k]>'9'); k++);
if ((line[k+1]>='0') && (line[k+1]<='9')) {
list[vote][j]=(line[k]-'0')*10+line[k+1]-'1';
k++;
}
else
list[vote][j]=line[k]-'1';
k++;
}
list[vote][20]=0;
vote++;
}
a=vote/2+1;
for (i=0; i<m; i++)
box=0;
for (i=0; i<vote; i++)
box[list[0]]++;
min=1001;
max=0;
for(i=0; i<m; i++) {
if (box==max)
same++;
if (box>max) {
max=box;
same=1;
}
if (box<min)
min=box;
}
left=m;
while ((max<a) && (same!=left)) {
for (i=0; i<m; i++)
if (box==min) {
box=-1;
left--;
}
else
box[i]=0;
for (i=0; i<vote; i++) {
for (; box[list[i][list[i][20]]]==-1; list[i][20]++);
box[list[i][list[i][20]]]++;
}
min=1001;
max=0;
for(i=0; i<m; i++) {
if (box[i]==max)
same++;
if (box[i]>max) {
max=box[i];
same=1;
}
if ((box[i]!=-1) && (box[i]<min))
min=box[i];
}
}
for (i=0; i<m; i++)
if (box[i]==max)
printf("%s\n", name[i]);
if (n!=1)
printf("\n");
}
}
//@end_of_source_code
[/cpp]
10142 - Australian Voting
Moderator: Board moderators
10142 - Australian Voting - WA
Im getting wrong answear in the 10142. Can anyone give me some testcases so I can try them with my algorithm.
here is the source that Im using (its loooooooong, I thing no one is going to read it, but am going to put it here anyway
[cpp]
#include <iostream>
#include <cctype>
#include <cstdlib>
#include <cstring>
using namespace std;
int
readvotes(int *v)
{
int c, i, j, flag = 0;
char num[16];
for (i = 0;;++i) {
j = 0;
while (isdigit(c = cin.get())) {
flag = 1;
num[j++] = c;
}
num[j] = '\0';
v = atoi(num);
if (c == '\n' || c == EOF)
break;
}
return flag;
}
struct cand_ {
int n;
int nvotes;
} cand[32];
int
comp(const void *s1, const void *s2)
{
return ( ((struct cand_ *) s2)->nvotes - ((struct cand_ *) s1)->nvotes);
}
char names[32][128];
void
print_name(int cn)
{
for (int i = 0; names[cn]; ++i)
cout << names[cn];
cout << endl;
}
struct votes_ {
int v[1004][32];
int nv;
} nv[32];
int elim[32];
int ncand;
int
main(void)
{
int v[32], nins;
cin >> nins;
while (nins--) {
cin >> ncand;
cin.get();
// get the names and init stuffs...
for (int i = 1; i <= ncand; ++i) {
cin.getline(names, 128);
cand.nvotes = nv.nv = 0;
cand.n = i;
}
// get the votes...
int tv = 0; // total of votes
while (readvotes(v)) {
int n = nv[v[0]].nv;
for (int i = 0; i < ncand; ++i) {
nv[v[0]].v[n] = v;
}
cand[v[0]].nvotes++;
nv[v[0]].nv++;
tv++;
}
// now we should have all the input data...
qsort(cand+1, ncand, sizeof(cand[1]), comp);
int nc = ncand;
memset(elim, 0, 32*sizeof(int));
while (cand[1].nvotes > cand[nc].nvotes &&
cand[1].nvotes <= tv/2) {
int mv = cand[nc].nvotes; // min voted cands
for (; cand[nc].nvotes == mv; --nc) {
int cn = cand[nc].n;
elim[cn] = 1;
for (int i = 0; i < nv[cn].nv; ++i) {
for (int j = 1; j < ncand; ++j) {
if (elim[nv[cn].v[j]])
continue;
int k;
for (k = 1;; ++k)
if (cand[k].n == nv[cn].v[i][j])
break;
cand[k].nvotes++;
break;
}
}
}
qsort(cand+1, nc, sizeof(cand[1]), comp);
}
int mv = cand[1].nvotes; // max voted
for (int i = 1; i <= ncand && cand[i].nvotes == mv; ++i)
print_name(cand[i].n);
if (nins)
cout << endl;
}
return 0;
}[/cpp]
here is the source that Im using (its loooooooong, I thing no one is going to read it, but am going to put it here anyway
[cpp]
#include <iostream>
#include <cctype>
#include <cstdlib>
#include <cstring>
using namespace std;
int
readvotes(int *v)
{
int c, i, j, flag = 0;
char num[16];
for (i = 0;;++i) {
j = 0;
while (isdigit(c = cin.get())) {
flag = 1;
num[j++] = c;
}
num[j] = '\0';
v = atoi(num);
if (c == '\n' || c == EOF)
break;
}
return flag;
}
struct cand_ {
int n;
int nvotes;
} cand[32];
int
comp(const void *s1, const void *s2)
{
return ( ((struct cand_ *) s2)->nvotes - ((struct cand_ *) s1)->nvotes);
}
char names[32][128];
void
print_name(int cn)
{
for (int i = 0; names[cn]; ++i)
cout << names[cn];
cout << endl;
}
struct votes_ {
int v[1004][32];
int nv;
} nv[32];
int elim[32];
int ncand;
int
main(void)
{
int v[32], nins;
cin >> nins;
while (nins--) {
cin >> ncand;
cin.get();
// get the names and init stuffs...
for (int i = 1; i <= ncand; ++i) {
cin.getline(names, 128);
cand.nvotes = nv.nv = 0;
cand.n = i;
}
// get the votes...
int tv = 0; // total of votes
while (readvotes(v)) {
int n = nv[v[0]].nv;
for (int i = 0; i < ncand; ++i) {
nv[v[0]].v[n] = v;
}
cand[v[0]].nvotes++;
nv[v[0]].nv++;
tv++;
}
// now we should have all the input data...
qsort(cand+1, ncand, sizeof(cand[1]), comp);
int nc = ncand;
memset(elim, 0, 32*sizeof(int));
while (cand[1].nvotes > cand[nc].nvotes &&
cand[1].nvotes <= tv/2) {
int mv = cand[nc].nvotes; // min voted cands
for (; cand[nc].nvotes == mv; --nc) {
int cn = cand[nc].n;
elim[cn] = 1;
for (int i = 0; i < nv[cn].nv; ++i) {
for (int j = 1; j < ncand; ++j) {
if (elim[nv[cn].v[j]])
continue;
int k;
for (k = 1;; ++k)
if (cand[k].n == nv[cn].v[i][j])
break;
cand[k].nvotes++;
break;
}
}
}
qsort(cand+1, nc, sizeof(cand[1]), comp);
}
int mv = cand[1].nvotes; // max voted
for (int i = 1; i <= ncand && cand[i].nvotes == mv; ++i)
print_name(cand[i].n);
if (nins)
cout << endl;
}
return 0;
}[/cpp]
10142 - Australian Voting ( HELP ? )
ITS LOOKS LIKE A PERFECT PROGRAM
IT FEELS LIKE A PERFECT PROGRAm
IT IS A PERFECT PROGRAM!
WHY WON"T ACM ACCEPT IT!
[c]
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int nc, np;
int p[1000][20];
int vote[20];
int totalvotes;
int valid[20];
char s[100];
char cname[20][80];
void count(void)
{
int i,j; totalvotes =0;
for(i=0;i<20;i++) vote = 0;
for(i=0;i<np;i++)
{
for(j=0; (j<20)&&(valid[p[j]]==0);j++);
if( valid[p[j]] )
{
vote[p[j]]++;
totalvotes++;
}
}
}
int iswinner(void)
{
int i,temp;
for(i=0;i<nc;i++)
if( valid )
{
if( vote / totalvotes > .50 )
{ printf("%s", cname);
return 1; }
else temp = vote;
}
for(i=0;i<nc;i++)
if( valid )
if( temp != vote)
return 0;
for(i=0;i<nc;i++)
if( valid[i] )
printf("%s\n", cname[i]);
return 1;
}
void main()
{
int numoftest;
int i,j,x,k,quit,min;
scanf("%d",&numoftest);
for(x=0;x<numoftest;x++)
{
nc = 0; np = 0;
for(i=0;i<1000;i++)
for(j=0;j<20;j++)
p[i][j]=0;
for(i=0;i<20;i++)
{ vote[i] = 0;
valid[i] = 0; }
for(i=0;i<20;i++)
for(j=0;j<80;j++)
cname[i][j] = 0;
scanf("%d\n",&nc);
for(i=0;i<nc;i++)
{ gets(cname[i]);
valid[i]=1;}
gets(s);
k=0;
while( strlen(s) > 0)
{ for (i=0;i<strlen(s)+1;i++)
{
if(( s[i] >= '0' ) && ( s[i] <= '9'))
p[np][k] = p[np][k] * 10 + (s[i]-'0');
else
p[np][k++]--; }
gets(s);
k=0;
np++; }
quit = 0;
while( quit == 0)
{ count();
if( iswinner() == 0 )
{
min = 9999;
for(i=0;i<nc;i++)
if( valid[i] )
if( min > vote[i])
min = vote[i];
for(i=0;i<nc;i++)
if( valid[i] )
if( min == vote[i])
valid[i] = 0;
}
else
{ quit = 1;
break;}
}
if( x < numoftest-1) printf("\n");
if( x == numoftest) exit(0);
}
}
[/c]
IT FEELS LIKE A PERFECT PROGRAm
IT IS A PERFECT PROGRAM!
WHY WON"T ACM ACCEPT IT!
[c]
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int nc, np;
int p[1000][20];
int vote[20];
int totalvotes;
int valid[20];
char s[100];
char cname[20][80];
void count(void)
{
int i,j; totalvotes =0;
for(i=0;i<20;i++) vote = 0;
for(i=0;i<np;i++)
{
for(j=0; (j<20)&&(valid[p[j]]==0);j++);
if( valid[p[j]] )
{
vote[p[j]]++;
totalvotes++;
}
}
}
int iswinner(void)
{
int i,temp;
for(i=0;i<nc;i++)
if( valid )
{
if( vote / totalvotes > .50 )
{ printf("%s", cname);
return 1; }
else temp = vote;
}
for(i=0;i<nc;i++)
if( valid )
if( temp != vote)
return 0;
for(i=0;i<nc;i++)
if( valid[i] )
printf("%s\n", cname[i]);
return 1;
}
void main()
{
int numoftest;
int i,j,x,k,quit,min;
scanf("%d",&numoftest);
for(x=0;x<numoftest;x++)
{
nc = 0; np = 0;
for(i=0;i<1000;i++)
for(j=0;j<20;j++)
p[i][j]=0;
for(i=0;i<20;i++)
{ vote[i] = 0;
valid[i] = 0; }
for(i=0;i<20;i++)
for(j=0;j<80;j++)
cname[i][j] = 0;
scanf("%d\n",&nc);
for(i=0;i<nc;i++)
{ gets(cname[i]);
valid[i]=1;}
gets(s);
k=0;
while( strlen(s) > 0)
{ for (i=0;i<strlen(s)+1;i++)
{
if(( s[i] >= '0' ) && ( s[i] <= '9'))
p[np][k] = p[np][k] * 10 + (s[i]-'0');
else
p[np][k++]--; }
gets(s);
k=0;
np++; }
quit = 0;
while( quit == 0)
{ count();
if( iswinner() == 0 )
{
min = 9999;
for(i=0;i<nc;i++)
if( valid[i] )
if( min > vote[i])
min = vote[i];
for(i=0;i<nc;i++)
if( valid[i] )
if( min == vote[i])
valid[i] = 0;
}
else
{ quit = 1;
break;}
}
if( x < numoftest-1) printf("\n");
if( x == numoftest) exit(0);
}
}
[/c]
Your Code
[cpp]char cname[20][80];[/cpp]
Problem Statement
[cpp]
while (strlen(s) > 0)
{
// [for loop omitted]
gets(s);
k=0;
np++;
}[/cpp]
If the end of the input file doesn't have a newline, you'll go into an infinite loop, as gets(s) will not update s if there is no blank line after the last input in the file.
[cpp]char cname[20][80];[/cpp]
Problem Statement
Also, be wary of this:Names may be up to 80 characters in length and may contain any printable characters.
[cpp]
while (strlen(s) > 0)
{
// [for loop omitted]
gets(s);
k=0;
np++;
}[/cpp]
If the end of the input file doesn't have a newline, you'll go into an infinite loop, as gets(s) will not update s if there is no blank line after the last input in the file.
INPUT
YOUR OUTPUT
Code: Select all
14
A
B
C
D
E
F
G
H
I
J
K
L
M
N
12 5 11 8 6 13 3 2 10 1 7 9 14 4
8 14 1 13 11 12 5 4 3 10 2 6 7 9
13 12 14 5 7 11 3 10 2 1 9 8 4 6
12 3 7 11 2 10 13 5 9 1 6 14 8 4
11 14 13 1 7 4 2 12 5 3 8 10 9 6
4 3 12 8 5 1 2 7 13 11 10 14 6 9
6 14 3 11 1 5 10 7 13 2 12 4 8 9EXPECTED OUTPUTM
Also, I noticed that you don't print the names of the candidates in the same order as they appear in the input file, and since there's no special correction judge for this, either ties never really exist, or they expect a certain order, but do not explicitly say it in the problem description.[/b]L
10142 - Australian Voting, WA, Need test cases
So far, all test cases found in earlier threads pass and my own pass, but the judge gives me a "Wrong answer" 
. If anyone can post some further test cases, it will greatly appreciated !
Here the code:
[cpp]
#define DEBUG 0
const int NameMaxLen=82;
const int MaxCanditates=20;
char names[MaxCanditates][NameMaxLen];
const int MaxBallotLineLength=MaxCanditates*3;
char ballotLine[MaxBallotLineLength];
int ballots[1000][MaxCanditates];
int votes[MaxCanditates];
void printVotes(int numC)
{
printf("Votes: ");
for(int i=0;i<numC;++i)
printf("%i:%i ",i+1,votes);
printf("\n");
}
int getMax(int numC)
{
int max=0;
for(int i=0;i<numC;++i)
if(votes>votes[max]) max=i;
return max;
}
int findLast(int numC, int winner)
{
int min=winner;
for(int i=0;i<numC;++i)
{
if(votes != -1 && votes<=votes[min])
{
min=i;
// if(DEBUG) printf("findLast: i:%i #i:%i min:%i #min:%i\n",i+1,votes,min+1,votes[min]);
}
// if(votes > 0 && votes<=votes[min]) min=i;
}
if(votes[min]==votes[winner]) // tie
return -1;
else
return min;
}
void recount(int numC, int numBallots,int last)
{
for(int i=0;i<numBallots;++i)
if(ballots[0]==last)
for(int j=1;j<numC;++j)
if(ballots[j]>=1 && votes[ballots[j]-1]!=-1 && ballots[i][j]<=numC)
{
ballots[i][0]=ballots[i][j];
ballots[i][j]=-1;
++votes[ballots[i][0]-1];
break;
}
}
int main()
{
int num=0;
scanf("%i\n",&num);
while(num>0)
{
memset(votes,0,sizeof(votes));
int numCand=0;
scanf("%i\n",&numCand);
if(DEBUG) printf("numCandidates:%i\n",numCand);
for(int i=0;i<numCand;++i)
{
fgets(names[i],NameMaxLen,stdin);
if(DEBUG) printf("%s",names[i]);
}
int numBallots=0;
while(fgets(ballotLine,MaxBallotLineLength,stdin))
{
if(strlen(ballotLine)==1) break;
// read ballots
if(DEBUG) printf("%i:",numBallots);
char* s=strtok(ballotLine," \n");
int c=0;
while(s)
{
ballots[numBallots][c]=atoi(s);
if(DEBUG) printf("%2i ",ballots[numBallots][c]);
++c;
s=strtok(0," \n");
}
for(;c<numCand;++c)
ballots[numBallots][c]=-1; // erase missing votes
if(DEBUG) printf("\n");
// count first round
++votes[ballots[numBallots][0]-1];
++numBallots;
}
// count until one is left or tie
if(DEBUG) printVotes(numCand);
int winner=getMax(numCand);
int neededVotes=numBallots/2+1;
int loser=-1;
while(votes[winner] < neededVotes)
{
if(DEBUG) printf("Winner: %i\n",winner+1);
loser=findLast(numCand,winner);
if(DEBUG) printf("losers: all with %i vote(s)\n",votes[loser]);
if(loser == -1) break; // tie
for(int i=0;i<numCand;++i)
if(votes[i]==votes[loser])
{
votes[i]=-1; // delete
recount(numCand,numBallots,i+1);
}
if(DEBUG) printVotes(numCand);
winner=getMax(numCand);
}
if(votes[winner]>=neededVotes)
printf("%s",names[winner]);
else
for(int i=0;i<numCand;++i)
if(votes[i]!= -1)
printf("%s",names[i]);
--num;
if(num>0) printf("\n");
}
return EXIT_SUCCESS;
}
[/cpp]
. If anyone can post some further test cases, it will greatly appreciated !Here the code:
[cpp]
#define DEBUG 0
const int NameMaxLen=82;
const int MaxCanditates=20;
char names[MaxCanditates][NameMaxLen];
const int MaxBallotLineLength=MaxCanditates*3;
char ballotLine[MaxBallotLineLength];
int ballots[1000][MaxCanditates];
int votes[MaxCanditates];
void printVotes(int numC)
{
printf("Votes: ");
for(int i=0;i<numC;++i)
printf("%i:%i ",i+1,votes);
printf("\n");
}
int getMax(int numC)
{
int max=0;
for(int i=0;i<numC;++i)
if(votes>votes[max]) max=i;
return max;
}
int findLast(int numC, int winner)
{
int min=winner;
for(int i=0;i<numC;++i)
{
if(votes != -1 && votes<=votes[min])
{
min=i;
// if(DEBUG) printf("findLast: i:%i #i:%i min:%i #min:%i\n",i+1,votes,min+1,votes[min]);
}
// if(votes > 0 && votes<=votes[min]) min=i;
}
if(votes[min]==votes[winner]) // tie
return -1;
else
return min;
}
void recount(int numC, int numBallots,int last)
{
for(int i=0;i<numBallots;++i)
if(ballots[0]==last)
for(int j=1;j<numC;++j)
if(ballots[j]>=1 && votes[ballots[j]-1]!=-1 && ballots[i][j]<=numC)
{
ballots[i][0]=ballots[i][j];
ballots[i][j]=-1;
++votes[ballots[i][0]-1];
break;
}
}
int main()
{
int num=0;
scanf("%i\n",&num);
while(num>0)
{
memset(votes,0,sizeof(votes));
int numCand=0;
scanf("%i\n",&numCand);
if(DEBUG) printf("numCandidates:%i\n",numCand);
for(int i=0;i<numCand;++i)
{
fgets(names[i],NameMaxLen,stdin);
if(DEBUG) printf("%s",names[i]);
}
int numBallots=0;
while(fgets(ballotLine,MaxBallotLineLength,stdin))
{
if(strlen(ballotLine)==1) break;
// read ballots
if(DEBUG) printf("%i:",numBallots);
char* s=strtok(ballotLine," \n");
int c=0;
while(s)
{
ballots[numBallots][c]=atoi(s);
if(DEBUG) printf("%2i ",ballots[numBallots][c]);
++c;
s=strtok(0," \n");
}
for(;c<numCand;++c)
ballots[numBallots][c]=-1; // erase missing votes
if(DEBUG) printf("\n");
// count first round
++votes[ballots[numBallots][0]-1];
++numBallots;
}
// count until one is left or tie
if(DEBUG) printVotes(numCand);
int winner=getMax(numCand);
int neededVotes=numBallots/2+1;
int loser=-1;
while(votes[winner] < neededVotes)
{
if(DEBUG) printf("Winner: %i\n",winner+1);
loser=findLast(numCand,winner);
if(DEBUG) printf("losers: all with %i vote(s)\n",votes[loser]);
if(loser == -1) break; // tie
for(int i=0;i<numCand;++i)
if(votes[i]==votes[loser])
{
votes[i]=-1; // delete
recount(numCand,numBallots,i+1);
}
if(DEBUG) printVotes(numCand);
winner=getMax(numCand);
}
if(votes[winner]>=neededVotes)
printf("%s",names[winner]);
else
for(int i=0;i<numCand;++i)
if(votes[i]!= -1)
printf("%s",names[i]);
--num;
if(num>0) printf("\n");
}
return EXIT_SUCCESS;
}
[/cpp]
i believe the input is flawed, the description says something like:
i submitted the following code:
it reads the ballots, reduces every number by one, sorts all the ballots and verifies that every ballot contains the numbers 0 .. nC-1 (nC == number of Candidates).
if that is not the case, it procudes an output limit exceeded. guess what? that's what i get from the judge as result.
watch out for ballots that don't contain valid votes anymore, and ignore them... that's how i got accepted.
ps: got accepted before submitting that code
so, if you have four candidates, a ballot like 1 2 1 2 would be illegal, cause it does not contain the numbers from 1 to 4.Up to 1000 lines follow; each contains the contents of a ballot. That is, each contains the numbers from 1 to n in some order. The first number indicates the candidate of first choice; the second number indicates candidate of second choice, and so on.
i submitted the following code:
Code: Select all
REP(i, nV) {
stringstream bla(vtmp[i]);
REP(j, nC) {
bla >> vot[i][j];
--vot[i][j];
}
sort(vot[i], vot[i]+nC);
REP(j, nC) if(vot[i][j]!=j) ole();
}
if that is not the case, it procudes an output limit exceeded. guess what? that's what i get from the judge as result.
watch out for ballots that don't contain valid votes anymore, and ignore them... that's how i got accepted.
ps: got accepted before submitting that code
10142 problems
There were several 10142 threads, so I picked the most recent one. My code passes my own test cases and all the test cases that have been posted in previous threads, but I still get WA.
Thanks for looking.
[c]
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef enum { false=0, true } bool;
#define CANDIDATE_MAX_NUM_CHARS 80
#define MAX_NUM_CANDIDATES 20
#define MAX_NUM_VOTERS 1000
typedef struct {
char name[CANDIDATE_MAX_NUM_CHARS+1];
bool eliminated;
} Candidate;
typedef struct {
unsigned int choices[MAX_NUM_CANDIDATES];
unsigned int currentChoice;
} Voter;
int main(int argc, char **argv) {
unsigned int numCases, caseNum;
unsigned int numCandidates, candidateNum;
Candidate candidates[MAX_NUM_CANDIDATES];
Voter voters[MAX_NUM_VOTERS];
unsigned int numVoters, voterNum;
unsigned int choiceNum;
unsigned numVotes[MAX_NUM_CANDIDATES];
unsigned int minNumVotes;
unsigned int numVotesRequiredToWin;
bool finished;
bool knowNumVotes;
bool areAllTied;
unsigned int misc;
char *cp;
char buf[256];
scanf("%u\n", &numCases);
for (caseNum=0; caseNum<numCases; caseNum++) {
memset(candidates, 0, sizeof(candidates));
memset(voters, 0, sizeof(voters));
scanf("%u\n", &numCandidates);
for (candidateNum=0; candidateNum<numCandidates; candidateNum++) {
fgets(candidates[candidateNum].name, sizeof(candidates[candidateNum].name), stdin);
cp = strchr(candidates[candidateNum].name, '\n');
if (*cp) *cp = '\0';
}
for (voterNum=0; voterNum<MAX_NUM_VOTERS; voterNum++) {
fgets(buf, sizeof(buf), stdin);
if (strlen(buf) == 1) break;
for (cp=strtok(buf, " \n"), choiceNum=0; cp; cp=strtok(NULL, " \n"), choiceNum++) {
voters[voterNum].choices[choiceNum] = atoi(cp) - 1;
}
}
numVoters = voterNum;
numVotesRequiredToWin = numVoters / 2 + 1;
/* candidate and voter data is read in at this point */
finished = false;
memset(numVotes, 0, sizeof(numVotes));
/* initial count */
for (voterNum=0; voterNum<numVoters; voterNum++) {
numVotes[voters[voterNum].choices[voters[voterNum].currentChoice]]++;
}
while (1) {
for (candidateNum=0; candidateNum<numCandidates; candidateNum++) {
if (!candidates[candidateNum].eliminated && numVotes[candidateNum] >= numVotesRequiredToWin) {
if (caseNum > 0) putchar('\n');
puts(candidates[candidateNum].name);
finished = true;
break;
}
}
if (finished) break;
/* check for tied condition */
knowNumVotes = false;
areAllTied = true;
for (candidateNum=0; candidateNum<numCandidates; candidateNum++) {
if (!candidates[candidateNum].eliminated) {
if (!knowNumVotes) {
misc = numVotes[candidateNum];
knowNumVotes = true;
continue;
}
if (numVotes[candidateNum] != misc) {
areAllTied = false;
break;
}
}
}
if (areAllTied) {
if (caseNum > 0) putchar('\n');
for (candidateNum=0; candidateNum<numCandidates; candidateNum++) {
if (!candidates[candidateNum].eliminated) {
puts(candidates[candidateNum].name);
}
}
break;
}
/* determine the lowest number of votes anyone got */
minNumVotes = 0xffffffff;
for (candidateNum=0; candidateNum<numCandidates; candidateNum++) {
if (!candidates[candidateNum].eliminated && numVotes[candidateNum] < minNumVotes) {
minNumVotes = numVotes[candidateNum];
}
}
/* eliminate candidates who got that number of votes and adjust the voters */
for (candidateNum=0; candidateNum<numCandidates; candidateNum++) {
if (!candidates[candidateNum].eliminated && numVotes[candidateNum] == minNumVotes) {
candidates[candidateNum].eliminated = true;
/* adjust voters who voted for that guy */
for (voterNum=0; voterNum<numVoters; voterNum++) {
if (voters[voterNum].choices[voters[voterNum].currentChoice] == candidateNum) {
do {
voters[voterNum].currentChoice++;
} while (candidates[voters[voterNum].currentChoice].eliminated);
/* recount that vote for the next best candidate */
numVotes[voters[voterNum].choices[voters[voterNum].currentChoice]]++;
}
}
}
}
}
}
return 0;
}
[/c]
Here is the input:
Here is the output:
Thanks for looking.
[c]
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef enum { false=0, true } bool;
#define CANDIDATE_MAX_NUM_CHARS 80
#define MAX_NUM_CANDIDATES 20
#define MAX_NUM_VOTERS 1000
typedef struct {
char name[CANDIDATE_MAX_NUM_CHARS+1];
bool eliminated;
} Candidate;
typedef struct {
unsigned int choices[MAX_NUM_CANDIDATES];
unsigned int currentChoice;
} Voter;
int main(int argc, char **argv) {
unsigned int numCases, caseNum;
unsigned int numCandidates, candidateNum;
Candidate candidates[MAX_NUM_CANDIDATES];
Voter voters[MAX_NUM_VOTERS];
unsigned int numVoters, voterNum;
unsigned int choiceNum;
unsigned numVotes[MAX_NUM_CANDIDATES];
unsigned int minNumVotes;
unsigned int numVotesRequiredToWin;
bool finished;
bool knowNumVotes;
bool areAllTied;
unsigned int misc;
char *cp;
char buf[256];
scanf("%u\n", &numCases);
for (caseNum=0; caseNum<numCases; caseNum++) {
memset(candidates, 0, sizeof(candidates));
memset(voters, 0, sizeof(voters));
scanf("%u\n", &numCandidates);
for (candidateNum=0; candidateNum<numCandidates; candidateNum++) {
fgets(candidates[candidateNum].name, sizeof(candidates[candidateNum].name), stdin);
cp = strchr(candidates[candidateNum].name, '\n');
if (*cp) *cp = '\0';
}
for (voterNum=0; voterNum<MAX_NUM_VOTERS; voterNum++) {
fgets(buf, sizeof(buf), stdin);
if (strlen(buf) == 1) break;
for (cp=strtok(buf, " \n"), choiceNum=0; cp; cp=strtok(NULL, " \n"), choiceNum++) {
voters[voterNum].choices[choiceNum] = atoi(cp) - 1;
}
}
numVoters = voterNum;
numVotesRequiredToWin = numVoters / 2 + 1;
/* candidate and voter data is read in at this point */
finished = false;
memset(numVotes, 0, sizeof(numVotes));
/* initial count */
for (voterNum=0; voterNum<numVoters; voterNum++) {
numVotes[voters[voterNum].choices[voters[voterNum].currentChoice]]++;
}
while (1) {
for (candidateNum=0; candidateNum<numCandidates; candidateNum++) {
if (!candidates[candidateNum].eliminated && numVotes[candidateNum] >= numVotesRequiredToWin) {
if (caseNum > 0) putchar('\n');
puts(candidates[candidateNum].name);
finished = true;
break;
}
}
if (finished) break;
/* check for tied condition */
knowNumVotes = false;
areAllTied = true;
for (candidateNum=0; candidateNum<numCandidates; candidateNum++) {
if (!candidates[candidateNum].eliminated) {
if (!knowNumVotes) {
misc = numVotes[candidateNum];
knowNumVotes = true;
continue;
}
if (numVotes[candidateNum] != misc) {
areAllTied = false;
break;
}
}
}
if (areAllTied) {
if (caseNum > 0) putchar('\n');
for (candidateNum=0; candidateNum<numCandidates; candidateNum++) {
if (!candidates[candidateNum].eliminated) {
puts(candidates[candidateNum].name);
}
}
break;
}
/* determine the lowest number of votes anyone got */
minNumVotes = 0xffffffff;
for (candidateNum=0; candidateNum<numCandidates; candidateNum++) {
if (!candidates[candidateNum].eliminated && numVotes[candidateNum] < minNumVotes) {
minNumVotes = numVotes[candidateNum];
}
}
/* eliminate candidates who got that number of votes and adjust the voters */
for (candidateNum=0; candidateNum<numCandidates; candidateNum++) {
if (!candidates[candidateNum].eliminated && numVotes[candidateNum] == minNumVotes) {
candidates[candidateNum].eliminated = true;
/* adjust voters who voted for that guy */
for (voterNum=0; voterNum<numVoters; voterNum++) {
if (voters[voterNum].choices[voters[voterNum].currentChoice] == candidateNum) {
do {
voters[voterNum].currentChoice++;
} while (candidates[voters[voterNum].currentChoice].eliminated);
/* recount that vote for the next best candidate */
numVotes[voters[voterNum].choices[voters[voterNum].currentChoice]]++;
}
}
}
}
}
}
return 0;
}
[/c]
Here is the input:
Code: Select all
6
3
John Doe
Jane Smith
Jane Austen
1 2 3
2 1 3
2 3 1
1 2 3
3 1 2
3
A
B
C
3
A
B
C
1 2 3
2 1 3
3 1 2
3
A
B
C
1 2 3
14
A
B
C
D
E
F
G
H
I
J
K
L
M
N
12 5 11 8 6 13 3 2 10 1 7 9 14 4
8 14 1 13 11 12 5 4 3 10 2 6 7 9
13 12 14 5 7 11 3 10 2 1 9 8 4 6
12 3 7 11 2 10 13 5 9 1 6 14 8 4
11 14 13 1 7 4 2 12 5 3 8 10 9 6
4 3 12 8 5 1 2 7 13 11 10 14 6 9
6 14 3 11 1 5 10 7 13 2 12 4 8 9
6
A
B
C
D
E
F
2 1 6 5 3 4
6 3 2 5 4 1
5 2 6 1 3 4
3 6 1 5 2 4
1 2 4 6 3 5
3 2 5 6 1 4
5 6 2 4 3 1
5 3 1 4 2 6
2 4 5 6 3 1
2 5 3 4 6 1
Code: Select all
John Doe
A
B
C
A
B
C
A
L
B
10142 - Australian Voting - WA & AC Together!!
My program ACs here, but WAs at http://www.programming-challenges.com
Why? 
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);
}Mostly http://www.programming-challenges.com has a tougher input, so it is not surprise that you get AC here but WA there. Although there is another possible case, the input at programming-challenges has problem. If you find there are people accepted at programming-challenges, then their input should be ok and your program has bug.
My signature:
- Please make discussion about the algorithm BRFORE posting source code.
We can learn much more in discussion than reading source code. - I HATE testing account.
- Don't send me source code for debug.
10142 Australian Voting - ambiguous problem description
Could anybody give me a little details on this quite ambiguous problem?
10142 WA
Every test I have run on this code has passed, however I cannot get the judge to accept it. I have searched through all the other forum posts but haven't been able to come up with a solution. Any help would be greatly appreciated.
Code: Select all
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
char buffer[256];
char names[20][81];
int rank[1000][20];
bool isValid[20];
int votes[20];
int numVoters;
int numCandidates;
int halfVotes;
inline void calculateWinner() {
bool equal;
int lowest;
for(int i = 0; i < 20; ++i)
isValid[i] = true;
while(true) {
int i;
for(i = 0; i < 20; ++i)
votes[i] = 0;
for(i = 0; i < numVoters; ++i) {
int j = 0;
while(isValid[rank[i][j]] == false && j < numCandidates)
++j;
votes[rank[i][j]]++;
}
i = 0;
while(isValid[i] == false && i < numCandidates)
++i;
lowest = i++;
equal = true;
for(; i < numCandidates; ++i)
if(votes[i] != votes[i - 1] && isValid[i] == true) {
if(votes[i] > halfVotes) {
puts(names[i]);
return;
}
if(equal == true)
equal = false;
if(votes[i] < votes[lowest])
lowest = i;
}
if(equal == true) {
for(i = 0; i < numCandidates; ++i)
if(isValid[i] == true)
puts(names[i]);
return;
}
else
for(i = 0; i < numCandidates; ++i)
if(votes[i] == votes[lowest])
isValid[i] = false;
}
}
int main () {
#ifndef ONLINE_JUDGE
freopen("main.in", "r", stdin);
#endif
int numTests;
scanf("%d\n\n", &numTests);
while(0 < numTests--) {
scanf("%d\n", &numCandidates);
int i;
for(i = 0; i < numCandidates; ++i)
gets(names[i]);
char* cp;
numVoters = 0;
gets(buffer);
while(strlen(buffer) > 1 && numVoters < 1000) {
for(cp = strtok(buffer, " \n"), i = 0; i < numCandidates; ++i, cp = strtok(NULL, " \n"))
rank[numVoters][i] = atoi(cp) - 1;
numVoters++;
gets(buffer);
}
halfVotes = numVoters / 2;
calculateWinner();
if(numTests > 0)
printf("\n");
}
}
-
Andrew Kostyagin
- New poster
- Posts: 1
- Joined: Fri Sep 16, 2005 6:50 pm
- Location: Moscow, Russia
10142 Australian Voting - bug report for tests
Good evening!
I wish to inform you, that the description of a problem 10142 "Australian Voting" and tests to it mismatch each other.
Particularly, in section Output it is written: "The Output consists of either a single line containing the name of the winner or several lines containing the names of the candidates who tied". Nothing is told about the order of a conclusion names of the candidates who tied whereas the test system expects that these names in the same order in which they went in Input of test case. My program mixed an array in which there were candidates during their sorting by quantity of ballots, and I could not understand some hours in any way that occurs.
Thank You,
Sorry for my English.
I wish to inform you, that the description of a problem 10142 "Australian Voting" and tests to it mismatch each other.
Particularly, in section Output it is written: "The Output consists of either a single line containing the name of the winner or several lines containing the names of the candidates who tied". Nothing is told about the order of a conclusion names of the candidates who tied whereas the test system expects that these names in the same order in which they went in Input of test case. My program mixed an array in which there were candidates during their sorting by quantity of ballots, and I could not understand some hours in any way that occurs.
Thank You,
Sorry for my English.