Выборы в США - 2
Сначала выбираем победителя каждого штата, затем суммируем его голоса выборщиков.
Как к ней подойти
Потренируйтесь хранить пары «ключ - значение» и находить нужные записи в словаре.
Словарь связывает ключ со значением и позволяет быстро найти запись по ключу. Решите, что будет ключом, что значением и как обрабатывать отсутствующую запись. Для подсчётов удобно начинать с нуля.
Считаем бюллетени отдельно в каждом штате. При равенстве выбираем лексикографически первого кандидата; итог сортируем по убыванию голосов, затем по имени. Эти правила восстановлены по архивным тестам, поскольку краткое условие не описывает разрешение ничьих.
Проверьте перед запуском
- Нельзя напрямую суммировать бюллетени по всей стране.
- Кандидаты без полученных голосов выборщиков выводятся с нулём.
- Архив содержит только два теста: правила ничьих и порядок выведены из них; поведение для штата без бюллетеней явно не задано, здесь его вес не распределяется.
Сравните свой подход
Ниже - готовое решение, другой способ, если он есть, и важные детали проверки.
Ваше принятое решение
Рекомендуемое решение: Словари голосов по штатам
Считаем бюллетени отдельно в каждом штате. При равенстве выбираем лексикографически первого кандидата; итог сортируем по убыванию голосов, затем по имени. Эти правила восстановлены по архивным тестам, поскольку краткое условие не описывает разрешение ничьих.
import sys
n = int(input())
weights = {}
for _ in range(n):
state, weight = input().split()
weights[state] = int(weight)
votes = {state: {} for state in weights}
totals = {}
for line in sys.stdin:
state, candidate = line.split()
totals.setdefault(candidate, 0)
counts = votes[state]
counts[candidate] = counts.get(candidate, 0) + 1
for state, counts in votes.items():
if counts:
winner = min(counts, key=lambda c: (-counts[c], c))
totals[winner] += weights[state]
for candidate in sorted(totals, key=lambda c: (-totals[c], c)):
print(candidate, totals[candidate])
Время: Ожидаемое O(n + v + p + k log k), n — штатов, v — бюллетеней, p — пар штат–кандидат, k — кандидатов; без учёта длины строк. Память: O(n+p+k).
Другой способ: Группировка отсортированных бюллетеней
Сортировка объединяет бюллетени по штату и кандидату. Размеры групп дают результаты штата, затем применяются те же правила ничьих и итогового порядка.
import sys
from itertools import groupby
n = int(input())
weights = {}
for _ in range(n):
state, weight = input().split()
weights[state] = int(weight)
ballots = [tuple(line.split()) for line in sys.stdin]
totals = {candidate: 0 for _, candidate in ballots}
ballots.sort()
for state, group in groupby(ballots, key=lambda r: r[0]):
counts = []
for candidate, rows in groupby(group, key=lambda r: r[1]):
counts.append((sum(1 for _ in rows), candidate))
winner = min(counts, key=lambda pair: (-pair[0], pair[1]))[1]
totals[winner] += weights[state]
for candidate in sorted(totals, key=lambda c: (-totals[c], c)):
print(candidate, totals[candidate])
Время: O(n + v log(v + 1) + k log(k + 1)), включая чтение n штатов; без учёта длины строк. Память: O(v+n+k).