Tous les défis
Moyen 0 résolus 0 % de réussite

Élection par vote alternatif

Dépouillez une élection par vote alternatif avec des bulletins classés, en éliminant les candidats les plus faibles à chaque tour.

Ce que vous allez apprendre

  • Attribuer chaque bulletin à son premier choix encore en course
  • Détecter un gagnant majoritaire et une égalité générale
  • Éliminer tous les candidats ayant le plus petit score

Problème

Dans un vote alternatif (ou second tour instantané), chaque électeur classe tous les candidats par ordre de préférence. Le dépouillement se fait en plusieurs tours :

  1. Chaque bulletin compte comme une voix pour le candidat le mieux classé qui est encore en course.
  2. Si un candidat obtient plus de la moitié de tous les bulletins, il gagne.
  3. Sinon, si tous les candidats restants ont le même nombre de voix, ils sont tous à égalité et l'élection s'arrête.
  4. Sinon, tous les candidats restants qui ont le moins de voix sont éliminés (tous en même temps si plusieurs partagent le plus petit score), et un nouveau tour commence.

Implémentez runoff_election(candidates, ballots).

Entrée

candidates : les noms des candidats. Le candidat i est candidates[i].

ballots : une ligne par électeur, contenant les numéros des candidats (à partir de 0) du préféré au moins apprécié. Chaque ligne contient chaque candidat exactement une fois.

Sortie

Renvoyez une liste contenant le nom du gagnant ou, si l'élection se termine sur une égalité, les noms de tous les candidats à égalité dans l'ordre où ils apparaissent dans candidates. Sans aucun bulletin, tous les candidats sont à égalité.

Contraintes

1 ≤ longueur de candidates ≤ 9

0 ≤ nombre de bulletins ≤ 200

Exemples

Exemple 1
Entrée :
candidates = ["Ana", "Bo", "Cy"]
ballots = [
    [0, 1, 2],
    [0, 2, 1],
    [1, 2, 0],
    [1, 0, 2],
    [2, 0, 1]
]

Sortie attendue :
expected = ["Ana"]
Entrée :
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}
};

Sortie attendue :
std::vector<std::string> expected = {"Ana"};
Entrée :
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}
};

Sortie attendue :
string[] expected = new string[] {"Ana"};

Explication

Premier tour : Ana 2, Bo 2, Cy 1 ; personne ne dépasse 2,5, donc Cy est éliminé. Son bulletin passe à Ana, qui gagne avec 3 voix sur 5 : ["Ana"].

Exemple 2
Entrée :
candidates = ["Ana", "Bo", "Cy"]
ballots = [
    [0, 1, 2],
    [0, 1, 2],
    [1, 2, 0],
    [1, 2, 0],
    [2, 1, 0],
    [2, 1, 0]
]

Sortie attendue :
expected = ["Ana", "Bo", "Cy"]
Entrée :
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}
};

Sortie attendue :
std::vector<std::string> expected = {"Ana", "Bo", "Cy"};
Entrée :
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}
};

Sortie attendue :
string[] expected = new string[] {"Ana", "Bo", "Cy"};

Explication

Chaque candidat a 2 voix de premier choix sur 6, donc les trois sont à égalité : ["Ana", "Bo", "Cy"].

Comment l'aborder

Essayez d'abord seul, puis ouvrez les indices un par un.

Indice 1

Gardez une liste de booléens indiquant qui est encore en course, et recomptez tout depuis zéro à chaque tour.

Indice 2

Une majorité signifie que voix × 2 est supérieur au nombre de bulletins.

Indice 3

Cherchez le plus petit score uniquement parmi les candidats restants ; si tous les restants l'ont, l'élection se termine sur une égalité.

Complexité attendue

temps O(c^2 × b), espace supplémentaire O(c)

Références

Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.

La meilleure solution validée de chaque codeur. Les plus rapides, les plus légères et les mieux notées passent devant.

Aucune solution validée pour l'instant. Résolvez-le et prenez la première place.

Apprenez des autres

Solutions de la communauté

Aucune solution publiée pour l'instant. Résolvez ce défi pour partager la première.