Todos los desafíos
Intermedio 0 resueltos 0% de aceptación

Elección con segunda vuelta instantánea

Resuelve una elección con segunda vuelta instantánea a partir de boletas con preferencias, eliminando ronda tras ronda a los candidatos más débiles.

Lo que aprenderás

  • Contar cada boleta para su opción preferida que siga en la contienda
  • Detectar un ganador por mayoría y un empate total
  • Eliminar a todos los candidatos con el menor conteo

Problema

Ver original (inglés)

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:

  1. Cada boleta cuenta como un voto para el candidato mejor clasificado en ella que siga en la contienda.
  2. Si un candidato tiene más de la mitad de todas las boletas, ese candidato gana.
  3. Si no, cuando todos los candidatos que quedan tienen la misma cantidad de votos, empatan y la elección termina.
  4. 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

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

Ejemplo 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]
]

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.

Clasificación

Clasificación completa

La mejor solución aprobada de cada programador. Las más rápidas, ligeras y mejor valoradas van primero.

Aún no hay soluciones aprobadas. Resuélvelo y quédate el primer puesto.

Aprende de otros

Soluciones de la comunidad

Aún no hay soluciones publicadas. Resuelve este reto para compartir la primera.