감 ¶
2005/03/13 Accepted(P.E.) 0:01.191 520
근방법 못돼 루 고다.
복 드는 감당 는 그가 긴다
문를 대로 다.
딩기 각는 많 가
다른 문들 같면 를 력데 문는 그렇 다. 그래 가 면 다.
문를 때 기 많 를 날려다.
근방법 못돼 루 고다.
복 드는 감당 는 그가 긴다
문를 대로 다.
딩기 각는 많 가
다른 문들 같면 를 력데 문는 그렇 다. 그래 가 면 다.
문를 때 기 많 를 날려다.
¶
~cpp
#include <iostream>
using namespace std;
#include <stdlib.h>
#include <string.h>
int main()
{
int numberOfCase;
cin >> numberOfCase;
int i, tc;
for (tc = 0; tc < numberOfCase; tc++)
{
int numberOfCandidates;
char candidates[20][81];
int votes[1000][20] = {{0}};
int rank[1000] = {{0}};
int votesPerCandidates[20] = {{0}};
cin >> numberOfCandidates;
cin.get();
for (i = 0; i < numberOfCandidates; i++)
cin.getline(candidates[i], 81);
int numberOfVoters = 0;
char temp[60];
while (cin.getline(temp, 60) && strcmp(temp, ""))
{
votes[numberOfVoters][0] = atoi(strtok(temp, " "));
for (i = 1; i < numberOfCandidates; i++)
votes[numberOfVoters][i] = atoi(strtok(NULL, " "));
numberOfVoters++;
}
bool foundWinner = false;
bool foundTie = true;
int winner;
int sameVote;
int eliminated[20];
int eliminatedCnt = 0;
while (true)
{
for (i = 0; i < numberOfCandidates; i++)
{
votesPerCandidates[i] = 0;
}
// 보 개당 득를 구다
for (i = 0; i < numberOfVoters; i++)
{
votesPerCandidates[votes[i][rank[i]] - 1]++;
}
// 력(보 개당 득)
/*for (i = 0; i < numberOfCandidates; i++)
cout << votesPerCandidates[i] << " ";
cout << endl;*/
// 력(가 구 는)
/*for (i = 0; i < numberOfVoters; i++)
{
cout << votes[i][rank[i]] << " ";
}
cin.get();*/
// 명 50% 과나 득가 모두 같면 료
for (i = 0; i < numberOfCandidates; i++)
{
if (votesPerCandidates[i] > 0.5 * numberOfVoters)
{
foundWinner = true;
winner = i;
break;
}
}
foundTie = true;
sameVote = 0;
for (i = 0; i < numberOfCandidates; i++)
{
if (votesPerCandidates[i] == 0)
continue;
if (sameVote == 0)
sameVote = votesPerCandidates[i];
else if (sameVote != votesPerCandidates[i])
foundTie = false;
}
if (foundWinner || foundTie)
break;
// 가 득를 보를 권들 보 그 로 (2단)
int minVote = 1001;
for (i = 0; i < numberOfCandidates; i++)
{
if (votesPerCandidates[i] == 0)
continue;
if (minVote > votesPerCandidates[i])
minVote = votesPerCandidates[i];
}
// 1-될 보 목록 만들고
for (i = 0; i < numberOfVoters; i++)
{
int j;
if (votesPerCandidates[votes[i][rank[i]] - 1] == minVote)
{
for (j = 0; j < eliminatedCnt; j++)
{
if (eliminated[j] == votes[i][rank[i]])
break;
}
if (j == eliminatedCnt)
eliminated[eliminatedCnt++] = votes[i][rank[i]];
}
}
// 2-될 보 목록 는 람
for (i = 0; i < numberOfVoters; i++)
{
int j;
if (votesPerCandidates[votes[i][rank[i]] - 1] == minVote)
{
bool foundNextCandidates;
while (true)
{
rank[i]++;
foundNextCandidates = true;
for (j = 0; j < eliminatedCnt; j++)
if (votes[i][rank[i]] == eliminated[j])
{
foundNextCandidates = false;
break;
}
if (foundNextCandidates)
break;
}
}
}
// 력(된 명단)
/*for (i = 0; i < eliminatedCnt; i++)
cout << eliminated[i] << " ";
cout << endl;*/
}
if (foundWinner)
cout << candidates[winner] << endl;
else if (foundTie)
{
for (i = 0; i < numberOfCandidates; i++)
{
if (sameVote == votesPerCandidates[i])
cout << candidates[i] << endl;
}
}
cout << endl;
}
return 0;
}
