10142 - Australian Voting
Moderator: Board moderators
how to test?
when i compile and run, what am i suppose to input?
or am i suppose to have a resource file or something?
or am i suppose to have a resource file or something?
i shall update this later
10142- wa
I got this codes accept to PC, but I keep geting WA here, can anyone help me ?
source is java:

source is java:
Code: Select all
import java.io.InputStream;
import java.io.IOException;
import java.util.StringTokenizer;
final class MyBufferedReader {
private InputStream in;
public MyBufferedReader (InputStream in) {
this.in = in;}
public String readLine () throws IOException {
final StringBuffer sb = new StringBuffer(80);
int i = 0;
while (((i = in.read()) != '\n') && (i != -1))
if (i != '\r')
sb.append((char) i);
if (i == -1)
return null;
return sb.toString();}}
final class Main {
static int [][] ballot;
static int max;
static int min;
static int casenum;
static int numvoters;
static String card;
static int x;
static int y;
static boolean end;
static boolean firstround;
static int temp;
static String [] candidatesnam;
static int[] votecount;
static int cannum;
private static final MyBufferedReader in = new MyBufferedReader(System.in);
public static void main (String[] args)
{
try {casenum = Integer.parseInt(in.readLine());}
catch (IOException e){}
try {in.readLine();}
catch (IOException e){}
ballot = new int[1000][21];
candidatesnam = new String [21];
while(casenum > 0)
{
firstround = true;
max =0; min = 1000;
try {StringTokenizer st = new StringTokenizer(in.readLine());
cannum = Integer.parseInt(st.nextToken());
}
catch (IOException e) {
}
temp = cannum+1;
votecount = new int [temp];
for(int z =1; z<=cannum;++z )
{
try {candidatesnam[z] = in.readLine();}
catch (IOException e) {}
}
y = 0;
end = false;
card = "";
numvoters =0;
try {card = in.readLine();}
catch (IOException e) {end = true;}
if(card == null||card.length() == 0)
{end = true;}
if(!end)
{
while ( !end)
{
++numvoters;
StringTokenizer st = new StringTokenizer(card);
for(int z = 1; z <=cannum;++z )
{ballot[y][z] = Integer.parseInt(st.nextToken());
ballot[y][0]= 1;
}
++y;
try {card = in.readLine();}
catch (IOException e) {
end = true;}
if(card == null||card.length() == 0)
{end = true;}
}
while(eval()) {
firstround = false;}
}
else{
for(int z = 1; z < cannum+1;z++)
{
System.out.println(candidatesnam[z]);
}
}
if(casenum > 1)
{
}
-- casenum;
}
}
public static boolean eval()
{
y =0;
while( y<numvoters)
{
if (firstround)
{
++votecount[ballot[y][1] ];
}
else if( votecount[ballot[y][ballot[y][0]]]<0)
{
while(votecount[ballot[y][ballot[y][0]]]<0)
{++ballot[y][0];
}
++votecount[ballot[y][ballot[y][0]] ];
}
++y;
}
min = 1000;
for(int z = 1; z<= cannum;z++)
{
if( votecount[z] > max)
max = votecount[z];
if((votecount[z]<min) && (votecount[z]!= -1))
min = votecount[z];
}
if(max>numvoters/2)
{y = 0;
while(votecount[y] != max)
{++y;}
System.out.println(candidatesnam[y]);
return false;
}
else if (max == min)
{ for(int z = 1; z < (cannum+1);z++)
{
if(votecount[z] == max)
System.out.println(candidatesnam[z]);
}
return false;
}
for(int z = 0; z < votecount.length;z++)
{
if(votecount[z] == min)
votecount[z] = -1;
}
return true;
}
}


-
- New poster
- Posts: 3
- Joined: Sat Apr 09, 2005 12:19 am
10142 RE!!!
I got runtime error in 10142, but my arrays are of correct sizes.
Any idea?
Any idea?
Code: Select all
//10142
#include <stdio.h>
#include <string.h>
char nombre[30][100];
int voto[2000][30];
int votos[30];
bool eliminado[30];
int p[30];
int main(){
int i, j, k, r;
int N, V, e;
int casos;
for(scanf("%d", &casos);casos--; ){
scanf("%d", &N);
for(i=1;i<=N;i++){
scanf("\n%[^\n]", nombre[i]);
}
memset(p, 0, sizeof(p));
memset(votos, 0, sizeof(votos));
memset(eliminado, 0, sizeof(eliminado));
for(i=1; ;i++){
j=getchar();
j=getchar();
if(j=='\n' || j==EOF || i>1000)
break;
ungetc(j, stdin);
for(j=0;j<N;j++)
scanf("%d", &voto[i][j]);
scanf("%*[^\n]");
}
V=i;
V--;
for(i=0, e=0;i<N && e<N;i++){
memset(votos, 0, sizeof(votos));
for(j=1;j<=V;j++){
while(eliminado[voto[j][p[j]]])
p[j]++;
votos[voto[j][p[j]]]++;
}
for(j=1, r=0, k=(1<<30);j<=N;j++)
if(!eliminado[j]){
if(votos[j]>V/2){
printf("%s\n", nombre[j]);
goto a;
}
k<?=votos[j];
r>?=votos[j];
}
for(j=1;j<=N;j++)
if(votos[j]==k){
eliminado[j]=true;
e++;
}
}
a:
if(i==N || e==N)
for(i=1;i<=N;i++)
if(votos[i]==r)
printf("%s\n", nombre[i]);
if(casos>0)
printf("\n");
}
}
-
- New poster
- Posts: 8
- Joined: Mon Jul 10, 2006 9:31 am
Hi!
Please check for some test case on the following link:
http://online-judge.uva.es/board/viewto ... 9650#49650
Hope this helps you
http://online-judge.uva.es/board/viewto ... 9650#49650
Hope this helps you
-
- New poster
- Posts: 8
- Joined: Mon Jul 10, 2006 9:31 am
10142... RTE (Signal 11).. Please help
Hi,
I am getting RTE(signal 11) as the verdict of my program... I have read posts regarding the test cases and then corrected my program so that it gives the right output for more than one space between nos... I have tested for all the test data posted.. It gives the correct out.. I am a newbie so please help me with it...Here is my code
I am getting RTE(signal 11) as the verdict of my program... I have read posts regarding the test cases and then corrected my program so that it gives the right output for more than one space between nos... I have tested for all the test data posted.. It gives the correct out.. I am a newbie so please help me with it...Here is my code
Code: Select all
#include<string.h>
#include<stdio.h>
struct details
{
char name[4000];
int novotes;
}elements[200];
void remove_leading(char *s);
void token(char *s, int re);
void count (int b,int n);
void initial(int n);
void initial1(int n);
int maxmin(int n,char *maxname,int *min);
void eliminate(int min,int n);
void rem_end(char *s);
void print(int);
int a[50000][1000];
main()
{
int t,n,i,j,senti=0,max,min,k;
char *maxname;
char str1[10000];
scanf("%d",&t);
for(k=1;k<=t;k++)
{
senti=0;
scanf("%d",&n);
getchar();
for(j=1;j<=n;j++)
{
gets(elements[j].name);
remove_leading(elements[j].name);
rem_end(elements[j].name);
}
initial1(n);
i=1;j=1;
a[1][1]=1;
while(gets(str1))
{
if(strcmp(str1,"")==0)
break;
token(str1,i);
i++;
}
while(senti==0)
{
count(i-1,n);
max=maxmin(n,maxname,&min);
if(max==min)
{
senti=1;
print(n);
}
if(((float)max)>((float)((i-1)/2)) && senti==0)
{
puts(maxname);
senti=1;
}
if(((float)max)<=((float)((i-1)/2)) && senti==0)
{
eliminate(min,n);
initial(n);
}
}
printf("\n\n");
}
}
void count(int b,int n)
{
int i,j;
for(i=1;i<=b;i++)
{
for(j=1;j<=n;j++)
{
if(elements[a[i][j]].novotes!=-1)
{
elements[a[i][j]].novotes++;
break;
}
}
}
}
int maxmin(int n,char *maxname,int *min)
{
int j,i,max=0;
*min=5000;
for(i=1;i<=n;i++)
{
if(elements[i].novotes>max)
{
max=elements[i].novotes;
j=i;
}
if(elements[i].novotes<*min && elements[i].novotes!=-1)
*min=elements[i].novotes;
}
strcpy(maxname,elements[j].name);
return max;
}
void print(int n)
{
int i;
for(i=1;i<=n;i++)
{
if(elements[i].novotes!=-1)
{
if(i==1)
puts(elements[i].name);
else
puts(elements[i].name);
}
}
}
void initial(int n)
{
int i;
for(i=1;i<=n;i++)
{
if(elements[i].novotes!=-1)
elements[i].novotes=0;
}
}
void initial1(int n)
{
int i;
for(i=1;i<=n;i++)
{
elements[i].novotes=0;
}
}
void eliminate(int min,int n)
{
int i;
for(i=1;i<=n;i++)
{
if(min==elements[i].novotes)
elements[i].novotes=-1;
}
}
void token(char *s, int re)
{
int i,j=0,n=1;
char str[50000],*temp;
temp=s;
while(strlen(s)!=0)
{
for(i=0;s[i]!=' '&&s[i]!='\0';i++);
temp=s;
strncpy(str,s,i);
str[i]='\0';
remove_leading(s);
remove_leading(str);
rem_end(s);
rem_end(str);
temp=temp+i;
strcpy(s,temp);
remove_leading(s);
remove_leading(str);
rem_end(s);
rem_end(str);
a[re][n]=atoi(str);
n++;
}
}
void remove_leading(char *s)
{
char *temp;
int i;
if(strlen(s)==0)
return;
temp=s;
for(i=0;s[i]==' ';i++);
temp=temp+i;
strcpy(s,temp);
}
void rem_end(char *s)
{
char *temp=s;
int i;
if(strlen(s)==0)
return;
for(i=(strlen(s)-1);s[i]==' ';i--);
strncpy(s,temp,i);
s[i+1]='\0';
}
10142 TLE(Help Needed!!)
Hai guys!
I got TLE for this problem. What's wrong with it? Can somebody help me?
I got TLE for this problem. What's wrong with it? Can somebody help me?
Code: Select all
#include <iostream>
#include <cstdio>
#include <list>
#include <vector>
#include <deque>
#include <algorithm>
#include <string>
#include <cctype>
#include <sstream>
#include <cstdlib>
using namespace std;
struct val{
int value;
int pos;
};
bool minFunc(val a, val b){
return a.value<b.value;
}
void process(vector<deque<int> > ballot, vector<string> candidate){
if(ballot.size()==0){
for(int i=0;i<candidate.size();i++){
cout<< candidate[i]<< endl;
}
}else{
vector<val> count,countBuff;
vector<vector<val>::iterator > pos;
vector<bool> lose;
for(int i=0;i<candidate.size();i++)
lose.push_back(true);
int total=0;
val t;
for(int i=0;i<candidate.size();i++){
t.pos=i+1;
t.value=0;
count.push_back(t);
}
for(int i=0;i<ballot.size();i++){
count[ballot[i][0]-1].value++;
total++;
}
bool found = false;
int maxEl=count[0].value,minEl=count[0].value;
for(int i=1;i<count.size();i++){
if(maxEl<count[i].value)
maxEl=count[i].value;
if(minEl>count[i].value)
minEl=count[i].value;
}
while(!found){
if(maxEl>total/2 || maxEl==minEl){
found =true;
for(vector<val>::iterator i=count.begin();i!=count.end();++i){
val t2 = *i;
if(t2.value==maxEl){
cout << candidate[t2.pos-1] << endl;
}
}
break;
}else{
minEl = count[0].value;
for(int i=1;i<count.size();i++){
if(minEl>count[i].value)
minEl=count[i].value;
}
pos.clear();
for(vector<val>::iterator i=count.begin();i!=count.end();++i){
val t2 = *i;
if(t2.value==minEl){
lose[t2.pos-1]=false;
}else
countBuff.push_back(*i);
}
count = countBuff;
countBuff.clear();
pos.clear();
for(int j=0;j<ballot.size();j++){
while(!lose[ballot[j][0]-1]){
ballot[j].pop_front();
for(int k=0;k<count.size();k++){
if(ballot[j].front()==count[k].pos && lose[ballot[j].front()-1]){
count[k].value++;
break;
}
}
}
}
if(count.size()>0){
maxEl=count[0].value;
minEl=count[0].value;
}
for(int i=1;i<count.size();i++){
if(maxEl<count[i].value)
maxEl=count[i].value;
if(minEl>count[i].value)
minEl=count[i].value;
}
}
}
}
}
int main(){
//freopen("input.in","r",stdin);
//freopen("output.out","w",stdout);
int n;
vector<string> candidate;
cin >> n;
string buff;
vector<deque<int> > ballot;
deque<int> temp;
getline(cin,buff);
int x;
while(true){
cin >> x;
getline(cin,buff);
//Input Candidate name
for(int i=0;i<x;i++){
getline(cin,buff);
candidate.push_back(buff);
}
//Input Ballot
while(true){
if(feof(stdin))break;
getline(cin,buff);
if(buff=="") break;
istringstream is(buff);
int buff2;
temp.clear();
while(is>>buff2){
temp.push_back(buff2);
}
ballot.push_back(temp);
if(feof(stdin)) break;
}
process(ballot,candidate);
cout << endl;
candidate.clear();
ballot.clear();
if(feof(stdin)) break;
}
return 0;
}
Here is my C++ code, I tried with 20 cases, and it did just fine. Judge says:
Your program has died with signal 11 (SIGSEGV). Meaning:
Invalid memory reference
Before crash, it ran during 0.002 seconds.
Here is my code:
I tried with is in input:
and gives me the output:
I don't know what I'm doing wrong... I set the char buffers to like 10000 in case that judge inputs my program with a very large vote string... Still it does not work.... To all of you AC people... Please help me out!!!
Greetings
Your program has died with signal 11 (SIGSEGV). Meaning:
Invalid memory reference
Before crash, it ran during 0.002 seconds.
Here is my code:
Code: Select all
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
int main()
{
int veces, i, j, c, k, m, t, **votos, *votos_c, menor, mayor, mitad;
char **cand, *no, *tmp;
bool caso;
votos = new int *[20];
tmp = new char[10000];
cand = new char *[20];
votos_c = new int[20];
for (j = 0; j < 20; j++)
{
cand[j] = new char[100];
votos[j] = new int;
}
cin >> veces;
while (veces--)
{
cin >> i;
if (i == 0)
goto next;
cin.getline(cand[0], 101);
while(cand[0][0] == 0)
cin.getline(cand[0], 101);
for (j = 1; j < i; j++)
cin.getline(cand[j], 101);
for (j = 0; j < 20; j++)
votos_c[j] = 0;
cin.getline(tmp, 10001);
if (tmp[0] == 0)
{
caso = 0;
goto out;
}
c = 0;
while(tmp[0] != 0)
{
j = 0;
no = strtok(tmp, " ");
sscanf(no, "%d", &votos[c][j++]);
for (; j < i; j++)
{
no = strtok(NULL, " ");
sscanf(no, "%d", &votos[c][j]);
}
cin.getline(tmp, 10001);
c++;
}
while (1)
{
for (j = 0; j < 20; j++)
{
if (votos_c[j] != -1)
votos_c[j] = 0;
}
for (j = 0; j < c; j++)
if (votos[j][0] != (-1))
votos_c[votos[j][0]-1]++;
j = 0;
while (votos_c[j] == -1)
j++;
menor = mayor = votos_c[j];
for (j = 0; j < i; j++)
{
if (votos_c[j] != -1)
{
if (votos_c[j] < menor)
menor = votos_c[j];
if (votos_c[j] > mayor)
mayor = votos_c[j];
}
}
if (mayor == menor)
{
caso = 0;
goto out;
}
mitad = c / 2;
for (j = 0; j < i; j++)
{
if (votos_c[j] > mitad)
{
caso = 1;
goto out;
}
}
for (j = 0; j < i; j++)
{
if (votos_c[j] == menor)
{
votos_c[j] = -1;
for(k = 0; k < c; k++)
for (m = 0; m < i; m++)
if (m == i-1 && votos[k][m] == j + 1)
votos[k][m] = -1;
else if (votos[k][m] == j + 1)
{
for (t = m; t < i - 1; t++)
votos[k][t] = votos[k][t + 1];
votos[k][t] = -1;
m--;
}
}
}
}
out:
if (caso == 0)
{
for (j = 0; j < i; j++)
{
if (votos_c[j] != -1)
cout << cand[j] << endl;
}
}
else
{
cout << cand[j] << endl;
}
next:
if (veces > 0)
{
cout << endl;
}
}
}
Code: Select all
20
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
2
i am jalal
he is Hasan
1 2
2 1
3
L
P
M
1 2 3
1 3 2
2 3 1
2 1 3
1 3 2
2 3 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
4
jalal
hasan
bijon
saiket
1 2 3 4
3 1 2 4
1 2 3 4
2 1 3 4
3 1 2 4
4 3 1 3
3
John Doe
Jane Smith
Sirhan Sirhan
1 2 3
2 1 3
2 3 1
1 2 3
3 1 2
3
John Doe
Jane Smith
Sirhan Sirhan
1 2 3
2 1 3
2 3 1
1 2 3
3 1 2
4
jalal
hasan
bijon
saiket
1 2 3 4
2 1 3 4
1 2 3 4
2 1 3 4
3 1 2 4
4 2 1 3
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
3
L
P
M
1 2 3
1 3 2
2 3 1
2 1 3
1 3 2
2 3 1
4
jalal
hasan
bijon
saiket
1 2 3 4
3 1 2 4
1 2 3 4
2 1 3 4
3 1 2 4
4 3 1 3
3
John Doe
Jane Smith
Sirhan Sirhan
1 2 3
2 1 3
2 3 1
1 2 3
3 1 2
3
John Doe
Jane Smith
Sirhan Sirhan
1 2 3
2 1 3
2 3 1
1 2 3
3 1 2
4
jalal
hasan
bijon
saiket
1 2 3 4
2 1 3 4
1 2 3 4
2 1 3 4
3 1 2 4
4 2 1 3
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
3
L
P
M
1 2 3
1 3 2
2 3 1
2 1 3
1 3 2
2 3 1
Code: Select all
John Doe
A
B
C
A
B
C
A
L
B
i am jalal
he is Hasan
L
P
B
jalal
bijon
John Doe
John Doe
jalal
hasan
B
L
P
jalal
bijon
John Doe
John Doe
jalal
hasan
B

Greetings
-
- New poster
- Posts: 3
- Joined: Fri Oct 12, 2007 4:33 pm
Bug
There an error in this loop:
Check the EOF flag and array limits;
Are you using a UNIX-like environment?
while(tmp[0] != 0)
{
j = 0;
no = strtok(tmp, " ");
sscanf(no, "%d", &votos[c][j++]);
for (; j < i; j++)
{
no = strtok(NULL, " ");
sscanf(no, "%d", &votos[c][j]);
}
cin.getline(tmp, 10001);
c++;
}
Check the EOF flag and array limits;
Are you using a UNIX-like environment?
while(tmp[0] != 0)
{
j = 0;
no = strtok(tmp, " ");
sscanf(no, "%d", &votos[c][j++]);
for (; j < i; j++)
{
no = strtok(NULL, " ");
sscanf(no, "%d", &votos[c][j]);
}
cin.getline(tmp, 10001);
c++;
}
That first case is invalid - read the problem statement.
I didn't read the "discussion" you had for the first input, but for the second one, I really don't see what the problem is. You miss the fact that 4 gets eliminated right away (because there were no first-choice votes for 4), and then, yes, 1 and 6. At that point, you have B with 4 votes and C and E with 3. So C and E get eliminated in the next step and B remains with 10 votes. You reintroduce a few of the eliminated candidates in your last count, which is clearly wrong.
This is not a hard problem, just read the statement a bit more carefully. It was one of the first ones I did - it still had a header with my ID, wrong I/O and stuff like that.
As for one of your questions - say you have 9 candidates, 3 have 3 votes each, rest have 0 votes - you eliminate all of those with 0's in one step, nothing changes, and you have a 3-way tie. (Note that the situation that you describe cannot occur - if there are 10 ballots, you cannot have 3 tied and 7 0's)
I didn't read the "discussion" you had for the first input, but for the second one, I really don't see what the problem is. You miss the fact that 4 gets eliminated right away (because there were no first-choice votes for 4), and then, yes, 1 and 6. At that point, you have B with 4 votes and C and E with 3. So C and E get eliminated in the next step and B remains with 10 votes. You reintroduce a few of the eliminated candidates in your last count, which is clearly wrong.
This is not a hard problem, just read the statement a bit more carefully. It was one of the first ones I did - it still had a header with my ID, wrong I/O and stuff like that.
As for one of your questions - say you have 9 candidates, 3 have 3 votes each, rest have 0 votes - you eliminate all of those with 0's in one step, nothing changes, and you have a 3-way tie. (Note that the situation that you describe cannot occur - if there are 10 ballots, you cannot have 3 tied and 7 0's)
WA, depressed.
Hi,
I've read all the threads for this problem and tried all the test cases. But I just can't find the bug. Can anybody help me figure it out?
I've read all the threads for this problem and tried all the test cases. But I just can't find the bug. Can anybody help me figure it out?
Code: Select all
/*if a candidate is elminated, the choices is updated by set the candidate number to 0*/
#include <iostream>
#include <vector>
#include <string>
#include <cstdlib>
#include <algorithm>
#include <sstream>
#include <cstdio>
#include <cstring>
using namespace std;
string cans[25]; //names of the candidates
int cnts[25]; //number of votes obtained
int ch[1100][25]; //choices
int current_ch[1100]; //current choices
int current_in[1100]; //the order of current choices
int ncans; //number of candidates
int ch_count; //total number of votes
bool outs[25] = {true};
void ini() {
for (int i = 0; i < 21; ++i) {
cans[i] = "";
cnts[i] = 0;
outs[i] = false;
}
for (int i = 0; i < 1001; ++i) {
current_in[i] = 1;
current_ch[i] = 0;
}
ncans = 0;
ch_count = 0;
}
/*proc: find the tickets the current choice is eliminated candidate, then update it*/
void proc() {
int min = 1001;
vector<int> eli;
/*find the candidate numbers to be eliminated*/
for (int i = 1; i <= ncans; ++i) {
if (!outs[i]) {
if (cnts[i] < min) {
min = cnts[i];
eli.clear();
eli.push_back(i);
}
else if (cnts[i] == min)
eli.push_back(i);
}
}
/*update everything*/
for (vector<int>::size_type j = 0; j < eli.size(); ++j) {
int i = eli[j];
cnts[i] = 0; //out, i is the candidate number
outs[i] = true;
for (int j = 1; j <= ch_count; ++j) { //j is the votes number
if (current_ch[j] == i) { //find the votes needs to update
current_in[j]++;
int k = current_in[j];
current_ch[j] = ch[j][k];
cnts[current_ch[j]]++;
}
}
}
}
bool check() {
bool tie = true;
int tie_num; //if tie, the number of votes each candidate get
int j = 1;
while (outs[j])
j++;
tie_num = cnts[j];
for (int i = 1; i <= ncans; ++i) {
if (!outs[i]) { //remaining candidates
if (cnts[i]*2 > ch_count) {
cout << cans[i] << endl;
return true;
}
else if (cnts[i] != tie_num)
tie = false;
}
}
if (tie == true) {
for (int i = 1; i <= ncans; ++i)
if (!outs[i])
cout << cans[i] << endl;
return true;
}
return false;
}
int main(void) {
int ncase;
cin >> ncase;
while (ncase--) {
ini();
cin >> ncans;
string tmp;
getline(cin, tmp); //eliminate the new line left behind
for (int i = 1; i <= ncans; ++i)
getline(cin, cans[i]);
string s;
while (getline(cin, s)) {
if (s == "")
break;
istringstream input(s);
ch_count++;
for (int j = 1; j <= ncans; ++j) {
input >> ch[ch_count][j];
if (j == 1)
cnts[ch[ch_count][j]]++; //count the initial choices
}
current_ch[ch_count] = ch[ch_count][1]; //initialize the current choice
}
/*begin to process*/
while (!check())
proc();
if (ncase)
cout << endl;
}
}
Re: 10142 - Australian Voting
Since I was just practicing STL, this code is ugly. I don't expect anyone to read through it. However, even though I have tried every (valid) test-case I have been able to found and it worked perfectly, the judge says time limit exceeds on this one
. I'll be thankful if someone can point out some quirky test-case:

Code: Select all
#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <vector>
#include <iterator>
#include <map>
using namespace std;
#define NBALLOTS 1000
typedef vector< vector< int > > twod_vector;
istream& operator>>(istream& in, twod_vector &v)
{
for(twod_vector::iterator p = v.begin(); p < v.end(); p++) {
for(vector< int >::iterator pr = (*p).begin();
pr < (*p).end();
pr++) {
*pr = *istream_iterator<
twod_vector::value_type::value_type
>(in);
}
}
return in;
}
ostream& operator<<(ostream &out, twod_vector v)
{
twod_vector::const_iterator p;
for(p = v.begin(); p < v.end(); p++) {
vector< int >::const_iterator pp;
for(pp = (*p).begin(); pp < (*p).end(); pp++) {
out<<setw(5)<<*pp<<" ";
}
out<<endl;
}
return out;
}
vector< int > calculate(vector< int > votes, int ncand, bool atleast_50)
{
vector< int > winners;
int total = votes.size();
int max = 0;
for(int i = 0; i < ncand; i++) {
int id = i + 1;
int vote_count = count(votes.begin(), votes.end(), id);
bool cond = !atleast_50 || (vote_count > total / 2);
if(vote_count > 0 &&
vote_count >= max &&
cond) {
max = vote_count;
winners.push_back(i);
}
}
return winners;
}
bool compare(pair< int, int > a, pair< int, int > b)
{
return a.second < b.second;
}
map< int, int > vote_map(vector< int > votes)
{ map< int, int > table;
vector< int >::iterator p;
for(p = votes.begin(); p < votes.end(); p++) {
if(table.count(*p) > 0) {
table[*p]++;
} else {
table[*p] = 1;
}
}
return table;
}
vector< int > least_votes(vector< int > votes)
{
map< int, int > table = vote_map(votes);
vector< int > min_keys;
int min_value =
min_element(table.begin(), table.end(), compare)->second;
map< int, int >::iterator p;
for( p = table.begin(); p != table.end(); p++ ) {
if(p->second == min_value) {
min_keys.push_back(p->first);
}
}
return min_keys;
}
twod_vector shift(twod_vector ballots)
{
vector< int > &first = ballots.at(0);
vector< int > min_values = least_votes(ballots.at(0));
vector< int >::iterator pi;
for(pi = min_values.begin(); pi != min_values.end(); pi++) {
int min_value = *pi;
vector< int >::iterator p;
while((p = find(first.begin(), first.end(), min_value))
!= first.end()) {
int index = p - first.begin();
int tmp = ballots.at(0).at(index);
ballots.at(0).at(index) = ballots.at(1).at(index);
int i;
for(i = 1; i < (int) ballots.size() - 1; i++) {
ballots.at(i).at(index)
= ballots.at(i + 1).at(index);
}
ballots.at(i).at(index) = tmp;
}
}
return ballots;
}
bool draw(vector< int > votes)
{
if(!votes.size()) {
return true;
}
map< int, int > table = vote_map(votes);
map< int, int >::iterator p = table.begin();
int n = p->second;
p++;
for(; p != table.end(); p++) {
if( n != p->second ) {
return false;
}
}
return true;
}
int main(int argc, char *argv[])
{
twod_vector ballots;
int ncases;
cin>>ncases;
cin.ignore();
string dummy;
getline(cin, dummy);
for(int i = 0; i < ncases; i++) {
int ncand;
cin>>ncand;
cin.ignore();
vector< string > candidates(ncand);
for(int j = 0; j < ncand; j++) {
getline(cin, candidates.at(j));
}
twod_vector ballots(ncand);
for(int j = 0; j < NBALLOTS; j++) {
string str;
getline(cin, str);
if(str == "") {
break;
}
istringstream iss(str);
vector< int > v;
for(int k = 0; k < ncand; k++) {
int value = *istream_iterator< int >(iss);
if(find(v.begin(), v.end(), value)
== v.end()) {
v.push_back(value);
}
}
if((int) v.size() < ncand) {
continue;
}
for(int k = 0; k < ncand; k++) {
ballots.at(k).push_back(
v.at(k)
);
}
}
vector< int > winners;
int j = 0;
while(winners.size() == 0) {
if(j > 0) {
if(draw(ballots.at(0))) {
winners = calculate(
ballots.at(0),
ncand,
false);
break;
}
ballots = shift(ballots);
}
winners = calculate(ballots.at(0), ncand, true);
j++;
}
if(!ballots.at(0).size()) {
for(int k = 0; k < ncand; k++) {
winners.push_back(k);
}
}
sort(winners.begin(), winners.end());
if(i > 0) {
cout<<endl;
}
vector< int >::const_iterator p;
for(p = winners.begin(); p < winners.end(); p++) {
cout<<candidates.at(*p)<<endl;
}
}
return 0;
}
Re: 10142 - Australian Voting
I finally got my program to be accepted at Programming Challenges' website. In my previous code, I wasn't "eliminating" candidates the right way.
However, the program still exceeds time-limit at UVa judge
:
However, the program still exceeds time-limit at UVa judge

Code: Select all
#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <vector>
#include <iterator>
#include <map>
using namespace std;
#define NBALLOTS 1000
typedef vector< vector< int > > twod_vector;
vector< int > calculate(vector< int > &votes, int ncand, bool atleast_50)
{
vector< int > winners;
int total = votes.size();
int max = 0;
for(int i = 0; i < ncand; i++) {
int id = i + 1;
int vote_count = count(votes.begin(), votes.end(), id);
bool cond = !atleast_50 || (vote_count > total / 2);
if(vote_count > 0 &&
vote_count >= max &&
cond) {
max = vote_count;
winners.push_back(i);
}
}
return winners;
}
bool compare(pair< int, int > a, pair< int, int > b)
{
return a.second < b.second;
}
map< int, int > vote_map(vector< int > &votes)
{
map< int, int > table;
vector< int >::iterator p;
for(p = votes.begin(); p < votes.end(); p++) {
if(table.count(*p) > 0) {
table[*p]++;
} else {
table[*p] = 1;
}
}
return table;
}
vector< int > least_votes(vector< int > &votes)
{
map< int, int > table = vote_map(votes);
vector< int > min_keys;
int min_value =
min_element(table.begin(), table.end(), compare)->second;
map< int, int >::iterator p;
for( p = table.begin(); p != table.end(); p++ ) {
if(p->second == min_value) {
min_keys.push_back(p->first);
}
}
return min_keys;
}
void eliminate(twod_vector &ballots, int value)
{
for(int i = 0; i < (int) ballots.size(); i++) {
for(int j = 0; j < (int) ballots.at(i).size(); j++) {
if(ballots.at(i).at(j) == value) {
for(int k = i;
k < (int) ballots.size() - 1;
k++) {
ballots.at(k).at(j)
= ballots.at(k + 1).at(j);
}
}
}
}
}
void eliminate(twod_vector &ballots)
{
vector< int > min_values = least_votes(ballots.at(0));
for(vector< int >::iterator p = min_values.begin();
p != min_values.end();
p++) {
eliminate(ballots, *p);
}
}
bool draw(vector< int > &votes)
{
if(!votes.size()) {
return true;
}
map< int, int > table = vote_map(votes);
map< int, int >::iterator p = table.begin();
int n = p->second;
p++;
for(; p != table.end(); p++) {
if( n != p->second ) {
return false;
}
}
return true;
}
int main(int argc, char *argv[])
{
twod_vector ballots;
int ncases;
cin>>ncases;
cin.ignore();
string dummy;
getline(cin, dummy);
for(int i = 0; i < ncases; i++) {
int ncand;
cin>>ncand;
cin.ignore();
vector< string > candidates(ncand);
for(int j = 0; j < ncand; j++) {
getline(cin, candidates.at(j));
}
twod_vector ballots(ncand);
for(int j = 0; j < NBALLOTS; j++) {
string str;
getline(cin, str);
if(str == "") {
break;
}
istringstream iss(str);
vector< int > v;
for(int k = 0; k < ncand; k++) {
int value = *istream_iterator< int >(iss);
ballots.at(k).push_back(
value
);
}
}
vector< int > winners;
int j = 0;
while(winners.size() == 0) {
if(j > 0) {
if(draw(ballots.at(0))) {
winners = calculate(
ballots.at(0),
ncand,
false);
break;
}
eliminate(ballots);
}
winners = calculate(ballots.at(0), ncand, true);
j++;
}
if(!ballots.at(0).size()) {
for(int k = 0; k < ncand; k++) {
winners.push_back(k);
}
}
sort(winners.begin(), winners.end());
if(i > 0) {
cout<<endl;
}
vector< int >::const_iterator p;
for(p = winners.begin(); p < winners.end(); p++) {
cout<<candidates.at(*p)<<endl;
}
}
return 0;
}