Todos os desafios
Médio 0 resolvidos 0% de aceitação

Eleição com segundo turno instantâneo

Apure uma eleição com segundo turno instantâneo a partir de cédulas ranqueadas, eliminando os candidatos mais fracos rodada a rodada.

O que você vai aprender

  • Contar cada cédula para a primeira opção que ainda está na disputa
  • Detectar um vencedor por maioria e um empate geral
  • Eliminar todos os candidatos com a menor contagem

Problema

Ver original (inglês)

Em uma eleição com segundo turno instantâneo, cada eleitor ordena todos os candidatos por preferência. A apuração é feita em rodadas:

  1. Cada cédula vale um voto para o candidato mais bem colocado nela que ainda está na disputa.
  2. Se um candidato tiver mais da metade de todas as cédulas, ele vence.
  3. Caso contrário, se todos os candidatos restantes tiverem o mesmo número de votos, todos empatam e a eleição termina.
  4. 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

Exemplo 1
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"].

Exemplo 2
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.

A melhor solução aprovada de cada programador. As mais rápidas, leves e mais bem avaliadas ficam no topo.

Ainda não há soluções aprovadas. Resolva e fique com o primeiro lugar.

Aprenda com outros

Soluções da comunidade

Ainda não há soluções publicadas. Resolva este desafio para compartilhar a primeira.