Problema
Em uma eleição com segundo turno instantâneo, cada eleitor ordena todos os candidatos por preferência. A apuração é feita em rodadas:
- Cada cédula vale um voto para o candidato mais bem colocado nela que ainda está na disputa.
- Se um candidato tiver mais da metade de todas as cédulas, ele vence.
- Caso contrário, se todos os candidatos restantes tiverem o mesmo número de votos, todos empatam e a eleição termina.
- Caso contrário, todos os candidatos restantes com o menor número de votos são eliminados (todos de uma vez, se vários empatarem na menor contagem), e começa uma nova rodada.
Implemente runoff_election(candidates, ballots).
Entrada
candidates: os nomes dos candidatos. O candidato i é candidates[i].
ballots: uma linha por eleitor, com os números dos candidatos (a partir de 0) do mais preferido para o menos preferido. Cada linha contém todos os candidatos exatamente uma vez.
Saída
Retorne uma lista com o nome do vencedor ou, se a eleição terminar empatada, os nomes de todos os empatados na ordem em que aparecem em candidates. Sem nenhuma cédula, todos os candidatos empatam.
Restrições
1 ≤ tamanho de candidates ≤ 9
0 ≤ número de cédulas ≤ 200
Exemplos
Entrada:
candidates = ["Ana", "Bo", "Cy"]
ballots = [
[0, 1, 2],
[0, 2, 1],
[1, 2, 0],
[1, 0, 2],
[2, 0, 1]
]
Saída esperada:
expected = ["Ana"]
Entrada:
std::vector<std::string> candidates = {"Ana", "Bo", "Cy"};
std::vector<std::vector<long long>> ballots = {
{0, 1, 2},
{0, 2, 1},
{1, 2, 0},
{1, 0, 2},
{2, 0, 1}
};
Saída esperada:
std::vector<std::string> expected = {"Ana"};
Entrada:
string[] candidates = new string[] {"Ana", "Bo", "Cy"};
long[][] ballots = new long[][] {
new long[] {0, 1, 2},
new long[] {0, 2, 1},
new long[] {1, 2, 0},
new long[] {1, 0, 2},
new long[] {2, 0, 1}
};
Saída esperada:
string[] expected = new string[] {"Ana"};
Explicação
Rodada 1: Ana 2, Bo 2, Cy 1; ninguém passa de 2,5, então Cy sai. A cédula de Cy vai para Ana, que vence com 3 de 5: ["Ana"].
Entrada:
candidates = ["Ana", "Bo", "Cy"]
ballots = [
[0, 1, 2],
[0, 1, 2],
[1, 2, 0],
[1, 2, 0],
[2, 1, 0],
[2, 1, 0]
]
Saída esperada:
expected = ["Ana", "Bo", "Cy"]
Entrada:
std::vector<std::string> candidates = {"Ana", "Bo", "Cy"};
std::vector<std::vector<long long>> ballots = {
{0, 1, 2},
{0, 1, 2},
{1, 2, 0},
{1, 2, 0},
{2, 1, 0},
{2, 1, 0}
};
Saída esperada:
std::vector<std::string> expected = {"Ana", "Bo", "Cy"};
Entrada:
string[] candidates = new string[] {"Ana", "Bo", "Cy"};
long[][] ballots = new long[][] {
new long[] {0, 1, 2},
new long[] {0, 1, 2},
new long[] {1, 2, 0},
new long[] {1, 2, 0},
new long[] {2, 1, 0},
new long[] {2, 1, 0}
};
Saída esperada:
string[] expected = new string[] {"Ana", "Bo", "Cy"};
Explicação
Cada candidato tem 2 votos em primeiro lugar de um total de 6, então os três empatam: ["Ana", "Bo", "Cy"].
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
Mantenha uma lista de verdadeiro/falso de quem ainda está na disputa e recomece a contagem do zero a cada rodada.
Dica 2
Maioria significa votos × 2 maior que o número de cédulas.
Dica 3
Procure a menor contagem só entre os candidatos restantes; se todos os restantes a tiverem, a eleição termina empatada.
Complexidade esperada
tempo O(c^2 × b), espaço extra O(c)
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.