Problema
In un'elezione con ballottaggio istantaneo, ogni elettore mette in ordine di preferenza tutti i candidati. Lo spoglio procede a turni:
- Ogni scheda vale un voto per il candidato più in alto nella sua classifica che sia ancora in gara.
- Se un candidato ha più della metà di tutte le schede, vince.
- Altrimenti, se tutti i candidati rimasti hanno lo stesso numero di voti, sono tutti a pari merito e l'elezione termina.
- 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
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"].
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.