Все задачи
Средне Решено: 0 Процент решений: 0%

Выборы с мгновенным вторым туром

Проведите выборы с мгновенным вторым туром по ранжированным бюллетеням, выбывая самых слабых кандидатов раунд за раундом.

Чему вы научитесь

  • Засчитывать каждый бюллетень лучшему из оставшихся кандидатов
  • Определять победителя с большинством и полную ничью
  • Исключать всех кандидатов с наименьшим числом голосов

Условие

На выборах с мгновенным вторым туром каждый избиратель ранжирует всех кандидатов. Подсчёт идёт раундами:

  1. Каждый бюллетень отдаёт один голос тому кандидату, который стоит в нём выше всех из ещё не выбывших.
  2. Если у кандидата больше половины всех бюллетеней, он побеждает.
  3. Иначе, если у всех оставшихся кандидатов одинаковое число голосов, между ними ничья, и выборы заканчиваются.
  4. Иначе выбывают все оставшиеся кандидаты с наименьшим числом голосов (все сразу, если таких несколько), и начинается новый раунд.

Реализуйте runoff_election(candidates, ballots).

Входные данные

candidates: имена кандидатов. Кандидат i - это candidates[i].

ballots: по одной строке на избирателя: номера кандидатов (с 0) от самого предпочтительного к наименее предпочтительному. В каждой строке каждый кандидат встречается ровно один раз.

Выходные данные

Верните список с именем победителя или, если выборы закончились ничьей, имена всех кандидатов с равным результатом в том порядке, в котором они идут в candidates. Если бюллетеней нет, ничья между всеми кандидатами.

Ограничения

1 ≤ длина candidates ≤ 9

0 ≤ количество бюллетеней ≤ 200

Примеры

Пример 1
Ввод:
candidates = ["Ana", "Bo", "Cy"]
ballots = [
    [0, 1, 2],
    [0, 2, 1],
    [1, 2, 0],
    [1, 0, 2],
    [2, 0, 1]
]

Ожидаемый вывод:
expected = ["Ana"]
Ввод:
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}
};

Ожидаемый вывод:
std::vector<std::string> expected = {"Ana"};
Ввод:
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}
};

Ожидаемый вывод:
string[] expected = new string[] {"Ana"};

Пояснение

Раунд 1: Ana 2, Bo 2, Cy 1; больше 2,5 голоса ни у кого нет, поэтому Cy выбывает. Бюллетень Cy переходит к Ana, и она побеждает с 3 голосами из 5: ["Ana"].

Пример 2
Ввод:
candidates = ["Ana", "Bo", "Cy"]
ballots = [
    [0, 1, 2],
    [0, 1, 2],
    [1, 2, 0],
    [1, 2, 0],
    [2, 1, 0],
    [2, 1, 0]
]

Ожидаемый вывод:
expected = ["Ana", "Bo", "Cy"]
Ввод:
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}
};

Ожидаемый вывод:
std::vector<std::string> expected = {"Ana", "Bo", "Cy"};
Ввод:
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}
};

Ожидаемый вывод:
string[] expected = new string[] {"Ana", "Bo", "Cy"};

Пояснение

У каждого кандидата 2 первых места из 6, поэтому между всеми тремя ничья: ["Ana", "Bo", "Cy"].

Как подступиться

Сначала попробуйте сами, затем открывайте подсказки по одной.

Подсказка 1

Храните список true/false, кто ещё участвует, и в каждом раунде пересчитывайте голоса заново.

Подсказка 2

Большинство означает, что число голосов × 2 больше числа бюллетеней.

Подсказка 3

Ищите наименьшее число голосов только среди оставшихся кандидатов; если оно у всех оставшихся, это ничья.

Ожидаемая сложность

время O(c^2 × b), доп. память O(c)

Ссылки

Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.

Лучшее принятое решение каждого участника. Более быстрые, экономные и высоко оценённые решения стоят выше.

Принятых решений пока нет. Решите задачу и займите первое место.

Учитесь у других

Решения сообщества

Пока нет опубликованных решений. Решите задание, чтобы поделиться первым.