10142 - Australian Voting

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

Moderator: Board moderators

HKcow
New poster
Posts: 10
Joined: Fri Aug 30, 2002 2:34 pm

10142 - Australian Voting

Post by HKcow » Fri Oct 11, 2002 7:49 pm

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]

rodriwan
New poster
Posts: 8
Joined: Mon Jun 03, 2002 8:13 pm

10142 - Australian Voting - WA

Post by rodriwan » Sun Jun 08, 2003 5:30 am

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]

AllanLin
New poster
Posts: 8
Joined: Thu Jun 26, 2003 3:38 am

10142 - Australian Voting ( HELP ? )

Post by AllanLin » Fri Aug 01, 2003 1:27 am

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]

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » Thu Aug 21, 2003 7:49 am

Your Code
[cpp]char cname[20][80];[/cpp]
Problem Statement
Names may be up to 80 characters in length and may contain any printable characters.
Also, be wary of this:
[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.

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » Thu Aug 21, 2003 8:09 am

INPUT

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 9
YOUR OUTPUT
M
EXPECTED OUTPUT
L
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]

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » Thu Aug 21, 2003 8:17 am

Your code infinite loops on the following test data:
1

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
The correct output is
B

tom
New poster
Posts: 1
Joined: Tue Sep 14, 2004 3:12 pm

10142 - Australian Voting, WA, Need test cases

Post by tom » Tue Sep 14, 2004 3:21 pm

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]

dispanser
New poster
Posts: 18
Joined: Wed May 01, 2002 4:12 pm
Location: Jena/Germany
Contact:

Post by dispanser » Thu Oct 07, 2004 6:51 pm

i believe the input is flawed, the description says something like:
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.
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.

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

brian
New poster
Posts: 1
Joined: Wed Dec 01, 2004 10:56 am

10142 problems

Post by brian » Wed Dec 01, 2004 11:11 am

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:

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
Here is the output:

Code: Select all

John Doe

A
B
C

A
B
C

A

L

B

User avatar
N|N0
New poster
Posts: 36
Joined: Tue Jan 25, 2005 10:33 pm
Location: Ljubljana, Slovenija
Contact:

10142 - Australian Voting - WA & AC Together!!

Post by N|N0 » Tue Jan 25, 2005 10:38 pm

My program ACs here, but WAs at http://www.programming-challenges.com

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);
}
Why? :cry:

User avatar
N|N0
New poster
Posts: 36
Joined: Tue Jan 25, 2005 10:33 pm
Location: Ljubljana, Slovenija
Contact:

Post by N|N0 » Sat Jan 29, 2005 11:03 am

Any idea? Anyone?

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Sat Jan 29, 2005 2:23 pm

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.

Faisal_Bd
New poster
Posts: 13
Joined: Wed Sep 01, 2004 10:00 am
Location: Bangladesh

10142 Australian Voting - ambiguous problem description

Post by Faisal_Bd » Sat Feb 19, 2005 4:18 pm

Could anybody give me a little details on this quite ambiguous problem?

specialk
New poster
Posts: 1
Joined: Sun Jul 03, 2005 9:27 am

10142 WA

Post by specialk » Sun Jul 03, 2005 10:39 am

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

Post by Andrew Kostyagin » Fri Sep 16, 2005 6:54 pm

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.

Post Reply

Return to “Volume 101 (10100-10199)”