Problema
En una elección con segunda vuelta instantánea, cada votante ordena a todos los candidatos según su preferencia. El conteo se hace por rondas:
- Cada boleta cuenta como un voto para el candidato mejor clasificado en ella que siga en la contienda.
- Si un candidato tiene más de la mitad de todas las boletas, ese candidato gana.
- Si no, cuando todos los candidatos que quedan tienen la misma cantidad de votos, empatan y la elección termina.
- En otro caso, se eliminan todos los candidatos que quedan con la menor cantidad de votos (todos a la vez si varios comparten el mínimo) y empieza una nueva ronda.
Implementa runoff_election(candidates, ballots).
Entrada
candidates: los nombres de los candidatos. El candidato i es candidates[i].
ballots: una fila por votante con los números de los candidatos (empezando en 0), del más preferido al menos preferido. Cada fila contiene a todos los candidatos exactamente una vez.
Salida
Devuelve una lista con el nombre del ganador o, si la elección termina en empate, los nombres de todos los candidatos empatados en el orden en que aparecen en candidates. Si no hay boletas, todos los candidatos empatan.
Restricciones
1 ≤ longitud de candidates ≤ 9
0 ≤ número de boletas ≤ 200
Ejemplos
Entrada:
candidates = ["Ana", "Bo", "Cy"]
ballots = [
[0, 1, 2],
[0, 2, 1],
[1, 2, 0],
[1, 0, 2],
[2, 0, 1]
]
Salida 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}
};
Salida 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}
};
Salida esperada:
string[] expected = new string[] {"Ana"};
Explicación
Ronda 1: Ana 2, Bo 2, Cy 1; nadie tiene más de 2.5, así que Cy queda eliminado. La boleta de Cy pasa a Ana, que gana con 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]
]
Salida 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}
};
Salida 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}
};
Salida esperada:
string[] expected = new string[] {"Ana", "Bo", "Cy"};
Explicación
Cada candidato tiene 2 votos en primer lugar de 6, así que los tres empatan: ["Ana", "Bo", "Cy"].
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
Lleva una lista de verdadero/falso con quién sigue en la contienda y vuelve a contar desde cero en cada ronda.
Pista 2
Hay mayoría cuando votos × 2 es mayor que la cantidad de boletas.
Pista 3
Busca el conteo más bajo solo entre los candidatos que quedan; si todos lo tienen, la elección es un empate.
Complejidad esperada
tiempo O(c^2 × b), espacio extra O(c)
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.