10142 - Australian Voting

[whiteSkar]

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]

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.

[fipas]

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]

I've managed to find my error! Thanks!

[brianfry713]

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

[nglinh]

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]

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]

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