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

whiteSkar
New poster
Posts: 1
Joined: Mon Nov 26, 2012 9:21 am

Re: 10142 - Australian Voting

Post by whiteSkar » Sun Nov 02, 2014 5:37 am

Hi,

I keep getting RUNTIME ERROR.

My code passes several test cases from internet and from my own. Can someone please find out a test case that my code produces run time erorr?

Here is my code:

Code: Select all

#include <math.h>
#include <string.h>
#include <iostream>
#include <string>
#include <fstream>
#include <unordered_map>
#include <algorithm>
#include <vector>
#include <iomanip>

using namespace std;

typedef pair<string, bool> candidate;
typedef pair<int, int> candidateId;

void tokenizeString(const string &str, vector<string>& tokens, const string &delimiters);
bool candidateIdCompare(const candidateId &c1, const candidateId &c2);
bool isStringEmptyOrWhitespace(string str);

const int CANDIDATE_MAX_COUNT = 20;
const int BALLOT_MAX_COUNT = 1000;

candidate candidates[CANDIDATE_MAX_COUNT];
vector<int> ballots[BALLOT_MAX_COUNT];

bool isCandidateAlive(int candidateId)
{
	return candidates[candidateId].second;
};

void popUntilAliveCandidate(vector<int> &candidateIds)
{
	while (!candidateIds.empty())
	{
		int candidateId = candidateIds.front();
		if (isCandidateAlive(candidateId))
			break;
		candidateIds.erase(candidateIds.begin());
	}
};

void initializeAliveCandidateBallots(candidateId *curBallots, int aliveCandidateCount)
{
	int id = 0;
	for (int i = 0; i < aliveCandidateCount; ++i)
	{
		while (!isCandidateAlive(id))
		{
			id++;
		}

		curBallots[i] = candidateId(id++, 0);
	}
};

candidateId *getCandidateId(int id, candidateId *curBallots, int aliveCandidateCount)
{
	for (int i = 0; i < aliveCandidateCount; ++i)
		if (curBallots[i].first == id)
			return curBallots + i;
};

int main()
{
	//ifstream inputFile("input.txt");	// change to cin
	//ofstream outputFile("output.txt");

	string input;
	getline(cin, input);
	int numTest = atoi(input.c_str());

	getline(cin, input);	// first blank line

	for (int k = 1; k <= numTest; k++)
	{
		memset(candidates, 0, sizeof(candidate) * CANDIDATE_MAX_COUNT);
		for (int i = 0; i < BALLOT_MAX_COUNT; ++i)
			ballots[i].clear();

		while (getline(cin, input))
		{
			if (!isStringEmptyOrWhitespace(input))
				break;
		}

		int candidateCount = atoi(input.c_str());
		
		for (int i = 0; i < candidateCount; ++i)
		{
			getline(cin, input);
			candidates[i] = candidate(input, true);
		}

		int ballotCount = 0;
		while (getline(cin, input))
		{
			if (isStringEmptyOrWhitespace(input))
				break;

			vector<string> ids;
			tokenizeString(input, ids, " ");

			for (auto it = ids.begin(); it != ids.end(); it++)
				ballots[ballotCount].push_back(atoi((*it).c_str()) - 1);

			ballotCount++;
		}

		vector<int> winnerIds;
		int aliveCandidateCount = candidateCount;

		if (ballotCount == 0)
		{
			for (int i = 0; i < aliveCandidateCount; ++i)
				winnerIds.push_back(i);
		}

		while (ballotCount > 0)
		{
			candidateId *curBallots = new candidateId[aliveCandidateCount];
			initializeAliveCandidateBallots(curBallots, aliveCandidateCount);

			for (int i = 0; i < ballotCount; ++i)
			{
				getCandidateId(ballots[i].front(), curBallots, aliveCandidateCount)->second++;
			}

			sort(curBallots, curBallots + aliveCandidateCount, candidateIdCompare);

			float voteRatio = (float)curBallots[aliveCandidateCount-1].second / ballotCount;
			if (voteRatio > 50)
			{
				winnerIds.push_back(curBallots[aliveCandidateCount-1].first);
				break;
			}
			else
			{
				bool isVoteRatioAllTheSame = true;
				for (int i = 1; i < aliveCandidateCount; ++i)
				{
					if (curBallots[0].second != curBallots[i].second)
					{
						isVoteRatioAllTheSame = false;
						break;
					}
				}

				if (isVoteRatioAllTheSame)
				{
					for (int i = 0; i < aliveCandidateCount; ++i)
					{
						winnerIds.push_back(curBallots[i].first);
					}
					break;
				}
				else
				{
					int numVotes = curBallots[0].second;
					int newlyDeadCandidateCount = 0;
					for (int i = 0; i < aliveCandidateCount; ++i)
					{
						if (curBallots[i].second == numVotes)
						{
							int deadId = curBallots[i].first;
							candidates[deadId].second = false;
							newlyDeadCandidateCount++;
						}
						else
						{
							break;
						}
					}

					aliveCandidateCount -= newlyDeadCandidateCount;
					for (int i = 0; i < ballotCount; ++i)
					{
						popUntilAliveCandidate(ballots[i]);
					}
				}
			}
		}

		for (auto it = winnerIds.begin(); it != winnerIds.end(); ++it)
		{
			cout << candidates[(*it)].first << endl;
		}

		if (k < numTest)
			cout << endl;
	}

	//inputFile.close();
	//outputFile.close();

	return 0;
}

void tokenizeString(const string &str, vector<string>& tokens, const string &delimiters = " ")
{
    // Skip delimiters at beginning.
    string::size_type lastPos = str.find_first_not_of(delimiters, 0);
    // Find first "non-delimiter".
    string::size_type pos = str.find_first_of(delimiters, lastPos);

    while (pos != string::npos || lastPos != string::npos)
    {
        // Found a token, add it to the vector.
        tokens.push_back(str.substr(lastPos, pos - lastPos));
        // Skip delimiters.  Note the "not_of"
        lastPos = str.find_first_not_of(delimiters, pos);
        // Find next "non-delimiter"
        pos = str.find_first_of(delimiters, lastPos);
    }
}

bool candidateIdCompare(const candidateId &c1, const candidateId &c2)
{
	return c1.second < c2.second;
}

bool isStringEmptyOrWhitespace(string str)
{
	if (str.empty() || str.find_first_not_of(' ') == std::string::npos)
		return true;
	return false;
}
And this is the test case I use and my code all passes these cases.
I've intentionally put more blank lines to make sure my code works fine in case the real input has more than one blank line by mistake.

Code: Select all

33
 

3
John Doe
Jane Smith
Sirhan Sirhan
1 2 3
2 1 3
2 3 1
1 2 3
3 1 2
   

1
John Doe
1

2
John Doe
Jane Smith
1 2
1 2



2
John Doe
Jane Smith
1 2
2 1

2
John Doe
Jane Smith
1 2
2 1
1 2
2 1

2
John Doe
Jane Smith
1 2
2 1
2 1
2 1
1 2

3
John Doe
Jane Smith
Siran Siran
1 2 3
2 3 1
3 1 2

3
John Doe
Jane Smith
Siran Siran
1 2 3
2 1 3
2 3 1

3
John Doe
Jane Smith
Siran Siran
1 2 3
1 2 3
1 2 3

3
John Doe
Jane Smith
Siran Siran
1 2 3

3
John Doe
Jane Smith
Siran Siran
1 2 3
1 2 3
2 1 3
2 1 3
3 1 2
3 2 2

3
John Doe
Jane Smith
Siran Siran
1 2 3
1 2 3
1 2 3
2 1 3
2 1 3
2 1 3
3 1 2
3 2 1

5
John Doe
Jane Smith
Siran Siran
Hoho Haha
Hehe Huhu
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
2 1 3 4 5
2 1 3 4 5
2 1 3 4 5
3 1 2 4 5
3 1 2 4 5
3 1 2 4 5
4 2 1 3 5
4 2 1 3 5
4 2 1 3 5
5 1 2 3 4
5 2 1 3 4

5
John Doe
Jane Smith
Siran Siran
Hoho Haha
Hehe Huhu
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
2 1 3 4 5
2 1 3 4 5
2 1 3 4 5
2 1 3 4 5
2 1 3 4 5
3 1 2 4 5
3 1 2 4 5
3 1 2 4 5
3 1 2 4 5
3 1 2 4 5
4 1 2 3 5
4 1 2 3 5
4 1 2 3 5
4 1 2 3 5
4 1 2 3 5
5 1 2 3 4
5 2 1 3 4
5 3 1 2 4
5 4 1 2 3

5
John Doe
Jane Smith
Siran Siran
Hoho Haha
Hehe Huhu
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
2 1 3 4 5
2 1 3 4 5
2 1 3 4 5
2 1 3 4 5
2 1 3 4 5
3 1 2 4 5
3 1 2 4 5
3 1 2 4 5
3 1 2 4 5
3 1 2 4 5
4 1 2 3 5
4 2 1 3 5
4 3 2 1 5
4 5 2 3 1
4 5 2 3 1
5 1 2 3 4
5 2 1 3 4
5 3 1 2 4

5
John Doe
Jane Smith
Siran Siran
Hoho Haha
Hehe Huhu
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
2 1 3 4 5
2 1 3 4 5
2 1 3 4 5
2 1 3 4 5
2 1 3 4 5
3 1 2 4 5
3 1 2 4 5
3 1 2 4 5
3 1 2 4 5
3 1 2 4 5
4 1 2 3 5
4 2 1 3 5
4 3 2 1 5
4 5 1 3 2
4 5 2 3 1
5 1 2 3 4
5 2 1 3 4
5 3 1 2 4

5
John Doe
Jane Smith
Siran Siran
Hoho Haha
Hehe Huhu
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
2 1 3 4 5
2 1 3 4 5
2 1 3 4 5
2 1 3 4 5
2 1 3 4 5
3 1 2 4 5
3 1 2 4 5
3 2 1 4 5
3 2 1 4 5
3 4 5 2 1
4 1 2 3 5
4 2 1 3 5
4 3 2 1 5
4 5 1 3 2
4 5 2 3 1
5 1 2 3 4
5 2 1 3 4
5 3 1 2 4

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

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
John Doe
Jane Smith
Jane Austen
1 2 3
2 1 3
2 3 1
1 2 3
3 1 2

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

3
L
P
M
1 2 3
1 3 2
2 3 1
2 1 3
1 3 2
2 3 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

12
A
B
C
D
E
F
G
H
I
J
K
L
10 9 12 4 5 2 6 3 8 1 7 11
1 7 2 11 4 3 12 10 8 6 9 5
7 10 11 8 6 2 5 1 12 3 4 9
10 4 9 6 12 1 11 8 5 3 2 7
1 4 6 12 2 11 8 10 7 5 3 9
8 4 9 3 11 7 12 2 5 10 1 6
4 1 7 5 9 12 3 6 8 10 11 2
9 6 12 3 1 11 8 2 7 10 5 4
6 9 1 3 11 2 4 10 12 7 5 8
2 10 9 1 4 6 12 11 8 3 5 7
1 10 3 7 4 8 5 6 11 12 9 2
7 10 1 3 12 2 4 11 8 6 5 9
4 8 1 9 5 10 11 7 6 2 3 12
12 8 1 7 9 4 6 10 2 3 11 5
3 2 9 6 1 4 10 11 7 8 12 5
1 2 7 3 10 12 8 4 11 5 9 6
6 11 10 7 5 8 4 2 1 3 12 9
3 8 12 4 7 1 5 11 9 6 10 2
4 8 10 1 6 3 12 5 7 2 11 9
5 8 10 9 7 4 1 11 12 2 3 6
2 10 6 8 5 1 9 4 7 3 12 11
9 5 7 11 4 1 8 10 2 6 3 12
2 12 7 4 3 5 10 9 6 11 8 1

16
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
5 4 11 1 14 6 2 12 9 16 3 13 15 10 8 7
11 7 1 16 8 10 2 9 14 15 12 5 4 3 13 6
16 6 3 5 1 15 10 14 13 11 2 4 8 12 9 7
14 12 1 6 7 5 16 4 13 10 8 9 2 15 11 3
2 3 10 15 4 13 11 16 9 12 14 5 8 7 6 1
7 11 10 5 8 6 15 14 4 13 2 3 9 16 1 12

Thank you very much,
whiteSkar

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 10142 - Australian Voting

Post by lighted » Mon Nov 03, 2014 8:59 am

Your code gets RE for sample I/O. http://ideone.com/ZVjq6e.

Please use code tags for posting test cases, otherwise your post becomes too big. :)
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

fipas
New poster
Posts: 2
Joined: Fri Nov 28, 2014 5:27 pm

Re: 10142 - Australian Voting

Post by fipas » Fri Nov 28, 2014 5:30 pm

Hello!

I got AC at the programming challenges website, but not at UVA.
Could somebody help me please?
This is my code:

Code: Select all

#include <bits/stdc++.h>

using namespace std;

int main() {

    int TC;
    cin >> TC;

    cin.ignore();

    for (int c = 0; c < TC; c++) {
        if (c) cout << endl;

        int numCandidates, numVotes = 0;
        string line;
        bool winnerFound = false;
        int maxVotes = -1, minVotes = 1000;
        vector<string> candidates;
        vector< vector<int> > votes(1010);

        cin >> numCandidates;

        bool eliminated[numCandidates + 1];
        int votesCandidate[numCandidates + 1];
        memset(eliminated, false, sizeof eliminated);
        memset(votesCandidate, 0, sizeof votesCandidate);

        cin.ignore();

        for (int i = 0; i < numCandidates; i++) {
            getline(cin, line);
            candidates.push_back(line);
        }

        while(getline(cin, line) && !line.empty()) {
            istringstream tokenizer(line);
            for (int i = 0; i < numCandidates; i++) {
                int val;
                tokenizer >> val;
                votes[numVotes].push_back(val);
            }
            numVotes++;
        }

        while (!winnerFound) {
            maxVotes = -1;
            minVotes = 1010;

            for (int i = 1; i <= numCandidates; i++)
                votesCandidate[i] = 0;

            for (int i = 0; i < numVotes; i++) {
                for (int j = 0; j < numCandidates; j++) {
                    if (eliminated[votes[i][j]]) continue;
                    else {
                        votesCandidate[votes[i][j]]++;
                        break;
                    }
                }
            }

            for (int i = 1; i <= numCandidates; i++) {
                if (!eliminated[i]) {
                    maxVotes = max(maxVotes, votesCandidate[i]);
                    minVotes = min(minVotes, votesCandidate[i]);
                }
            }

            if (maxVotes > numVotes / 2 || maxVotes == minVotes) {
                winnerFound = true;
            }

            if (maxVotes != minVotes) {
                for (int i = 1; i <= numCandidates; i++) {
                    if (votesCandidate[i] == minVotes) {
                        eliminated[i] = true;
                    }
                }
            }
        }

        for (int i = 1; i <= numCandidates; i++)
            if (!eliminated[i])
                cout << candidates[i - 1] << endl;
    }

    return 0;
}

fipas
New poster
Posts: 2
Joined: Fri Nov 28, 2014 5:27 pm

Re: 10142 - Australian Voting

Post by fipas » Sat Nov 29, 2014 4:06 pm

I've managed to find my error! Thanks!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10142 - Australian Voting

Post by brianfry713 » Sat Dec 13, 2014 10:16 pm

Input:

Code: Select all

1

4
A
B
C
D
2 1 3 4
2 1 3 4
3 1 4 2
4 1 2 3
AC output B
Check input and AC output for thousands of problems on uDebug!

nglinh
New poster
Posts: 1
Joined: Sat Dec 13, 2014 10:19 pm

Re: 10142 - Australian Voting

Post by nglinh » Sat Dec 13, 2014 10:24 pm

Could you explain why the answer is B instead of A B?

Aren't B elected only if B has more than 50% of the votes?

Edit: nevermind, the 'secondary' vote counts towards the one that has not been eliminated only

Zedi
New poster
Posts: 2
Joined: Mon Aug 31, 2015 10:40 am

Re: 10142 - Australian Voting

Post by Zedi » Mon Aug 31, 2015 10:53 am

Can anyone help me why I get WA?

Code: Select all

#include <stdio.h>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <fstream>

using namespace std;

//int inMinIndex(int, int*, int);

int main(void){

	ifstream ifs;
	int l;

	int case_num = 0;
	char line[100];
	//cout << "start\n";

	cin >> case_num;
	gets(line);

	//ifs.open("input.txt");
	//ifs >> case_num;

	for (int i = 0; i < case_num; i++){
		
		int cand_num = 0;
		//int * votes;
		//char ** cand_names;

		if (i > 0)
			cout << endl;

		cin >> cand_num;
		gets(line);// stdin 제거용
		//ifs >> cand_num;
		//ifs.getline(line, 100);

		char cand_names[20][80];
		int votes[20];

		for (int j = 0; j < cand_num; j++){
			gets(cand_names[j]);
			//ifs.getline(cand_names[j], 80);
		}

		int votings[1000][20];

		int vote_num = 0;

		while (1){

			for (int k = 0; k < 50; k++){
				gets(line);
				//ifs.getline(line, 80);

				if (!strcmp(line, "") || line[0] == '\0'){
					break;
				}

				char num[3];
				int m = 0;
				int n = 0;
				for (l = 0; l < 100; l++){
					
					if (line[l] == ' ' || line[l] == '\0'){
						votings[k][n++] = atoi(num);
						//cout << votings[k][n++]<<endl;
						m--;
						for (; m > -1; m--){
							num[m] = ' ';
						}
						if (line[l] == '\0')
							break;
						m++;
					}
						
					else
						num[m++] = line[l];
															
				}

				vote_num++;

			}

			break;			
		}

		//for (int k = 0; k < vote_num; k++){
		//	for (int l = 0; l < cand_num; l++){
		//		cout << votings[k][l];
		//	}
		//	cout << endl;
		//}
		

		int min_index[20];
		
		int max_vote = 0;
		int same_all = 0;
		int std = 0;
		int std_index;	
			
		for (l = 0; l < cand_num; l++){
			min_index[l] = -1;
			votes[l] = 0;
		}			

		// 1순위 숫자 센다.
		for (l = 0; l < vote_num; l++){
			votes[votings[l][0] - 1]++;
		}

		while (1) {
			//proc_b = clock();
			int winner_num = 0;
			int min_vote = 1000;
			int min_num = 0;
			int more_half = 0;


			// 종료 조건 : 과반 
			for (l = 0; l < cand_num; l++){
				if (votes[l] > (double)vote_num / (double)2){
					more_half = 1;
					//cout << cand_names[l] << endl;
					puts(cand_names[l]);
				}
				if (votes[l] <= min_vote && votes[l] != 0){
					min_vote = votes[l];
				}
			}
			if (more_half)
				break;
			
			// 종료 조건 : 모든 후보 동률
			// 유효 votes찾기
			for (l = 0; l < cand_num; l++){
				if (votes[l] != 0){
					std = votes[l];
					std_index = l;
					break;
				}
			}
			// 같은 지 검사
			for (l = std_index + 1; l < cand_num; l++){
				if (std != votes[l] && votes[l] != 0){
					same_all = 0;
					break;
				}
				if (l == cand_num - 1)
					same_all = 1;
			}

			if (same_all){
				for (l = 0; l < cand_num; l++){
					if (votes[l] != 0)
						//cout << cand_names[l] << endl;
						puts(cand_names[l]);
				}
				break;
			}
			
			for (l = 0; l < vote_num; l++){
				int m = 0;
				int exit = 0;
				
				while ( votes[votings[l][m] - 1] != min_vote){	
					if (votes[votings[l][m] - 1] > min_vote){
						exit = 1;
						break;
					}
					m++;
				}

				if (exit) continue;

				while (votes[votings[l][m] - 1] <= min_vote){
					m++;
				}
				votes[votings[l][m] - 1]++;
			}

			for (l = 0; l < cand_num; l++){
				if (votes[l] == min_vote)
					votes[l] = 0;

			}		

		}

	}

	return 0;
}

bitaron
New poster
Posts: 12
Joined: Mon Jan 06, 2014 9:40 pm

Re: 10142 - Australian Voting

Post by bitaron » Sun Nov 01, 2015 2:38 pm

Tested with all the cases in the forum. Getting WA. Also getting Presentation Error in programming-challenges . Can any one tell me whats the problem.
Thanks in advance.

Code: Select all

#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<algorithm>
#include<set>
#include<stack>
#include<queue>
#include<list>
#include<iostream>
#include<fstream>
#include <sstream>
#include<numeric>
#include<string>
#include<vector>
#include<cstring>
#include<map>
#include<iterator>
using namespace std;

queue<int> split(string str, char delimiter) {
  queue<int> internal;
  stringstream ss(str); // Turn the string into a stream.
  string tok;
  
  while(getline(ss, tok, delimiter)) {
	  int temp = atoi(tok.c_str());
	  if(temp !=0){
		internal.push(temp);
	  }
    
  }
 // cout<<internal.size();
  return internal;
}

bool shouldBeRemoved(int target, set<int>minCan, int voteCount){
	pair<std::set<int>::iterator,bool> inserted = minCan.insert(target);
	return !inserted.second || voteCount<0;
}

int main(int argc, char **argv)
{
	std::ifstream infile;
	int caseNumber;
	//infile.open("10142.txt");
	//infile>>caseNumber;
	cin>>caseNumber;
	
	int c = 0;
	while(c<caseNumber){
		int can;
		//infile>>can;
		cin>>can;
		//cout<<can<<endl;
		vector<string> names;
		string line;
		getline(cin,line);
		for(int j=0;j<can;j++){
			getline(cin,line);
		//	cout<<line<<endl;
			names.push_back(line);
		}
		vector<queue<int> > votes;
		while(getline(cin,line)){
			
			if(line.empty()){
				break;
			}else{
				votes.push_back(split(line,'  '));
			}
		}
		
		if(votes.size() == 0){
			for(int i = 1; i<=can;i++){
				cout<<names[i-1]<<endl;			
			}
		}
		int count[can+3]; 
		//memset(count,0,can+3);
		fill(count, count+can+3, 0);
		/*	for(int i=0;i<=can;i++){
			cout<<i<<"="<<count[i]<<endl;
		}*/
		//counting the the first vote of every voter
		for(int i=0;i<votes.size();i++){
			count[votes[i].front()]++;
		}
	/*	for(int i=0;i<votes.size();i++){
			while(!votes[i].empty()){
				cout<<votes[i].front()<<" ";
				votes[i].pop();
			}
			cout<<endl;
		}*/
	//int k =2;
	
	//the all decider loop
		while(1){
			//k--;
		//	cout<<caseNumber<<endl;
			int max = -1;
			int min = 99999999;
			set<int> minCan;
			int previous;
			//getting a value from the vote count to match if 
			// all the voter has same vote. and setting sentinal 
			// value for voter with votes 0
			for(int i=1;i<=can;i++){
				if(count[i]>0){
					previous = count[i];
					
				}else{
					count[i] = -99999;
				}
			}
			int maxCan;
			bool allEqual = true;
			
			//finding the max and min votes and candidate 
			//also checking if all votes are equal
			for(int i=1;i<=can;i++){
			//	cout<<i<<"="<<count[i]<<endl;
				if(count[i]>0){
					
					if(count[i]>max){
						max = count[i];
						maxCan = i;
					}
					
					if(count[i] == min){
						minCan.insert(i);
					}
					
					if(count[i]<min){
						min = count[i];
						minCan.clear();
						minCan.insert(i);
					}
					
					if(count[i] != previous){
						allEqual = false;
					}
				}
			}
			double percentage = (double)max/(double)votes.size();
			percentage *= 100;
		//	cout<<allEqual<<" "<<percentage<<endl;
			if(allEqual){
			//	cout<<"here"<<endl;
				for(int i = 1; i<=can;i++){
					if(count[i]>0){
						cout<<names[i-1]<<endl;
					}
					
				}
				break;
			}else if(percentage>50){
			//	cout<<"here"<<endl;
				cout<<names[maxCan-1]<<endl;
				break;
			}else{
				//removing min candidates
				for(int j = 0; j<votes.size();j++){
					while(1){
						//cout<<votes[j].front()<<"="<<count[votes[j].front()]<<endl;
						if(shouldBeRemoved(votes[j].front(),minCan,count[votes[j].front()])){
							count[votes[j].front()] = -99999;
							votes[j].pop();
							count[votes[j].front()]++;
						}else{
							break;
						}
					}
				}
			}
		}
	//	cout<<"here"<<endl;
		if(c<caseNumber){
			cout<<endl;
		}
		c++;
	}
	
	return 0;
}



Post Reply

Return to “Volume 101 (10100-10199)”

Who is online

Users browsing this forum: Bing [Bot] and 1 guest