Tutte le sfide
Media 0 risolte 0% di accettazione

Elezione con ballottaggio istantaneo

Svolgi un'elezione a ballottaggio istantaneo con schede a preferenze ordinate, eliminando turno dopo turno i candidati più deboli.

Cosa imparerai

  • Assegnare ogni scheda alla prima preferenza ancora in gara
  • Riconoscere un vincitore con la maggioranza e una parità completa
  • Eliminare tutti i candidati con il conteggio più basso

Problema

In un'elezione con ballottaggio istantaneo, ogni elettore mette in ordine di preferenza tutti i candidati. Lo spoglio procede a turni:

  1. Ogni scheda vale un voto per il candidato più in alto nella sua classifica che sia ancora in gara.
  2. Se un candidato ha più della metà di tutte le schede, vince.
  3. Altrimenti, se tutti i candidati rimasti hanno lo stesso numero di voti, sono tutti a pari merito e l'elezione termina.
  4. Altrimenti, tutti i candidati rimasti con il minor numero di voti vengono eliminati (tutti insieme, se più di uno condivide il minimo) e inizia un nuovo turno.

Implementa runoff_election(candidates, ballots).

Input

candidates: i nomi dei candidati. Il candidato i è candidates[i].

ballots: una riga per elettore, con i numeri dei candidati (a partire da 0) dal preferito al meno gradito. Ogni riga contiene tutti i candidati esattamente una volta.

Output

Restituisci una lista con il nome del vincitore oppure, se l'elezione finisce in parità, i nomi di tutti i candidati a pari merito nell'ordine in cui compaiono in candidates. Senza schede, tutti i candidati sono a pari merito.

Vincoli

1 ≤ lunghezza di candidates ≤ 9

0 ≤ numero di schede ≤ 200

Esempi

Esempio 1
Input:
candidates = ["Ana", "Bo", "Cy"]
ballots = [
    [0, 1, 2],
    [0, 2, 1],
    [1, 2, 0],
    [1, 0, 2],
    [2, 0, 1]
]

Output atteso:
expected = ["Ana"]
Input:
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}
};

Output atteso:
std::vector<std::string> expected = {"Ana"};
Input:
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}
};

Output atteso:
string[] expected = new string[] {"Ana"};

Spiegazione

Turno 1: Ana 2, Bo 2, Cy 1; nessuno supera 2.5, quindi Cy viene eliminato. La scheda di Cy passa ad Ana, che vince con 3 voti su 5: ["Ana"].

Esempio 2
Input:
candidates = ["Ana", "Bo", "Cy"]
ballots = [
    [0, 1, 2],
    [0, 1, 2],
    [1, 2, 0],
    [1, 2, 0],
    [2, 1, 0],
    [2, 1, 0]
]

Output atteso:
expected = ["Ana", "Bo", "Cy"]
Input:
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}
};

Output atteso:
std::vector<std::string> expected = {"Ana", "Bo", "Cy"};
Input:
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}
};

Output atteso:
string[] expected = new string[] {"Ana", "Bo", "Cy"};

Spiegazione

Ogni candidato ha 2 prime preferenze su 6, quindi tutti e tre sono a pari merito: ["Ana", "Bo", "Cy"].

Come affrontarlo

Prova prima da solo, poi apri un suggerimento alla volta.

Suggerimento 1

Tieni una lista di vero/falso che indica chi è ancora in gara e ricalcola tutto da zero a ogni turno.

Suggerimento 2

Maggioranza significa che voti × 2 è maggiore del numero di schede.

Suggerimento 3

Cerca il conteggio più basso solo tra i candidati rimasti; se ce l'hanno tutti, l'elezione è in parità.

Complessità attesa

tempo O(c^2 × b), spazio aggiuntivo O(c)

Riferimenti

Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.

La migliore soluzione superata di ogni programmatore. Le più veloci, leggere e meglio valutate stanno in alto.

Ancora nessuna soluzione superata. Risolvila e prendi il primo posto.

Impara dagli altri

Soluzioni della community

Nessuna soluzione pubblicata. Risolvi questa sfida per condividere la prima.