БЛОГ НА HUSL


Задача "Выборы в США" PYTHON3

Автор вопроса: Егорка

Задача "Выборы в США"

Условия

Как известно, в США президент выбирается не прямым голосованием, а путём двухуровневого голосования. Сначала проводятся выборы в каждом штате, и определяется победитель выборов в данном штате. Затем проводятся государственные выборы: на этих выборах каждый штат имеет определённое число голосов — число выборщиков от этого штата. На практике все выборщики от штата голосуют в соответствии с результатами голосования внутри штата, то есть на заключительной стадии выборов в голосовании участвуют штаты, имеющие различное число голосов.

На этот раз вам известно число выборщиков от каждого штата США и результаты голосования каждого гражданина США (а также в каком штате проживает данный гражданин).

Вам необходимо подвести результаты голосования: сначала определить результаты голосования в каждом штате и определить, за кого из кандидатов отданы голоса выборщиков данного штата. Далее необходимо подвести результаты голосования выборщиков по всем штатам.

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

Первая строка входных данных содержит количество штатов в США N (1≤N≤100000). Далее идёт N строк, описывающих штаты США, каждая строка состоит из названия штата и числа выборщиков от этого штата. На следующей строке задано число M (1≤M≤100000)— количество проголосовавших на выборах. В следующих M строках идут записи результатов голосования по каждому из участников голосования. Одна строка соответствует одному избирателю. Записи имеют следующий вид: название штата, имя кандидата, за которого проголосовал данный избиратель. Названия штатов и имена кандидатов не содержат пробелов.

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

Выведите список кандидатов, упорядоченный по убыванию числа голосов выборщиков, полученных за данного кандидата, а при равенстве числа голосов выборщиков — в лексикографическом порядке. После имени кандидата выведите число набранных им голосов.

Если в каком-либо штате два или более кандидатов набрали одинаковое число голосов, то все голоса выборщиков этого штата получает наименьший в лексикографическом порядке кандидат из числа победителей в этом штате.

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

Примечание к примерам тестов

  1. В Florida 2 избирателя голосует за Gore и три избирателя за Bush, поэтому 25 голосов выборщиков от Florida получает Bush. В Pennsylvania побеждает Gore (5 голосов против 1), поэтому Gore получает 23 голоса выборщиков от Pennsylvania.

  2. В Florida побеждает Gore (5 голосов выборщиков), в Alaska — Bush (2 голоса выборщиков). В Pennsylvania два кандидата набрали наибольшее число голосов (по 1), поэтому 4 голоса выборщиков от этого штата получает Clinton, т.к. он идет раньше в лексикографическом порядке.

Примеры

Ввод
2
Florida 25
Pennsylvania 23
11
Florida Gore
Pennsylvania Gore
Florida Bush
Pennsylvania Gore
Pennsylvania Bush
Florida Gore
Pennsylvania Gore
Florida Bush
Pennsylvania Gore
Florida Bush
Pennsylvania Gore

Вывод:
Bush 25
Gore 23

Ввод:
3
Florida 5
Pennsylvania 4
Alaska 3
4
Florida Gore
Pennsylvania Obama
Pennsylvania Clinton
Alaska Bush

Вывод:
Gore 5
Clinton 4
Bush 3
Obama 0

Ограничение по времени: 2с


Мой код 
votes = {}
candidates = {}
for i in range(int(input())):
    state = input().split()
    votes[state[0]] = [{}, int(state[1])]
for i in range(int(input())):
    vote = input().split()
    try:
        votes[vote[0]][0][vote[1]] += 1
    except KeyError:
        votes[vote[0]][0][vote[1]] = 1
for i in votes.keys():
    a = list(votes[i][0].keys())
    d = a.copy()
    b = list(votes[i][0].values())
    j = 0
    while j < len(d):
        if b[j] < max(b):
            d.remove(d[j])
        j += 1
    d.sort()
    candidates[d[0]] = votes[i][1]
    a.remove(a[a.index(d[0])])
    for j in range(len(a)):
        try:
            candidates[a[j]] += 0
        except KeyError:
            candidates[a[j]] = 0
f = list(candidates.keys())
for i in range(len(f)):
    f = list(candidates.keys())
    d = f.copy()
    b = list(candidates.values())
    j = 0
    while j < len(d):
        if b[j] < max(b):
            d.remove(d[j])
            b.remove(b[j])
            continue
        j += 1
    d.sort()
    while d:
        del candidates[d[0]]
        print(d.pop(0), max(b))

Помогите с дебагом: что может быть неправильно?


Источник

Ответы (2 шт):

Автор решения: Zhihar

вот такой код получился, правда не короткий, как хотелось, но зато в лоб :)

хотя если убрать комментарии - в 2,5 раза покороче получилось :)

# получить список штатов и данные по выборщикам
votes = {}
for i in range(int(input())):
    info = input().split()
    votes[info[0]] = [{}, int(info[1])]

# получить список голосов
results = {}
for i in range(int(input())):
    state, candidate = input().split()
    votes[state][0][candidate] = (votes[state][0][candidate] + 1) if candidate in votes[state][0] else 1
    results[candidate] = 0

# подсчитать выборщиков
for key in votes:
    # найти победителя в штате
    winner = ('', 0)
    for candidate in votes[key][0]:
        winner = (candidate, votes[key][0][candidate]) if votes[key][0][candidate] > winner[1] else \
            (candidate, votes[key][0][candidate]) if votes[key][0][candidate] == winner[1] and candidate < winner[0] else winner

    # учесть результат
    results[winner[0]] = results[winner[0]] + votes[key][1] if winner[0] in results else votes[key][1]

# отсортировать результат по голосам и вывести
for candidate in sorted(map(lambda candidate: (candidate, results[candidate]), results), key=lambda item: item[1], reverse=True):
    print(*candidate)

P.S.

Поскольку все кандидаты занесены в словарь заранее и им выставлено кол-во голосов 0, то строку

    # учесть результат
    results[winner[0]] = results[winner[0]] + votes[key][1] if winner[0] in results else votes[key][1]

можно смело заменит на

# учесть результат
results[winner[0]] += votes[key][1]

P.P.S.

не дочитал правила вывода, а именно

Выведите список кандидатов, упорядоченный по убыванию числа голосов выборщиков, полученных за данного кандидата, а при равенстве числа голосов выборщиков — в лексикографическом порядке.

поэтому вместо

# отсортировать результат по голосам и вывести
for candidate in sorted(map(lambda candidate: (candidate, results[candidate]), results), key=lambda item: item[1], reverse=True):
    print(*candidate)

требуется сделать несколько более хитрую сортировку

# отсортировать результат по голосам и вывести
for candidate in sorted(map(lambda candidate: (candidate, results[candidate]), results), key=lambda item: (-item[1], item[0])):
    print(*candidate)
→ Ссылка
Автор решения: SergFSM

не совсем ответ на заданный вопрос, просто как вариант решения задачи (возможно пригодиться):

states = {}
for i in range(int(input())): 
    states.update([input().split()])  # перечень штатов (словарь)
    
votes = dict.fromkeys(states,())
for i in range(int(input())): 
    s,c = input().split()
    votes[s] = *votes[s],c  # голоса проголосовавших (словарь)

# кандидаты получившие большинство голосов (словарь)
max_votes = {k:max(sorted(v),key=lambda x: v.count(x)) for k,v in votes.items()}
cands = dict.fromkeys(set(sum(votes.values(),())),0)
for k,v in max_votes.items(): 
    # число голосов выборщиков полученные кандидатами (словарь)
    cands[v] += int(states[k]) 

# вывод кандидатов в порядке убывания числа голосов выборщиков
print(*[f'{c} {v}' for c,v in sorted(cands.items(),key=lambda x: -x[1])], sep='\n')

ввод:

3
Florida 5
Pennsylvania 4
Alaska 3
4
Florida Gore
Pennsylvania Obama
Pennsylvania Clinton
Alaska Bush

вывод:

Gore 5
Clinton 4
Bush 3
Obama 0
→ Ссылка

licensed under cc by-sa 3.0 with attribution.