Wprowadzenie
W wyborach powszechnych chcielibyśmy obliczyć stałą cenę za mandat parlamentu. Oznacza to, że w N >= 0celu rozdzielenia miejsc i listy nsgłosów na partię chcielibyśmy znaleźć taką liczbę d, która
sum(floor(n/d) for n in ns) == N
Aby uczynić rzeczy interesującymi (i bardziej podobnymi do realnego świata), dodajemy dwa dodatkowe fakty:
Dwie partie mogą zebrać się w „koalicji”, dzięki czemu mandaty zostaną przyznane „koalicji” przez sumę głosów wszystkich partii w niej uczestniczących. Następnie mandaty „koalicji” są podzielone między partiami w podobny sposób (znajdź dzielnik itp.)
Partia, która nie uzyskała określonego odsetka głosów (np. 3,25%) automatycznie otrzymuje 0 mandatów, a jej głosy nie liczą się do „koalicji”.
Wyzwanie
Dostaniesz :
- Lista list, każda z list zagnieżdżonych zawiera liczby całkowite (liczba głosów) i ma długość 1 dla jednej partii lub długość 2 dla „koalicji”.
- Minimalny procent głosów (aka „bar” dla „zapory”), aby uzyskać miejsca, jako ułamek (więc 3,25% podano jako 0,0325)
- Całkowita liczba miejsc do podziału między wszystkie strony (liczba całkowita)
Masz wydrukować tę samą strukturę listy zagnieżdżonej, z liczbą głosów zastąpionych miejscami w parlamencie.
Zwycięzca to kod z najmniejszą ilością bajtów.
Narożniki:
- Może istnieć (i zwykle będzie) więcej niż jeden możliwy dzielnik. Ponieważ nie ma go na wyjściu, tak naprawdę nie ma znaczenia.
- Wyobrazić sobie,
N=10ins = [[1]], dlatego mogą być dzielnikiem 0,1 (nie całkowitą) - Niektóre przypadki nie można rozwiązać, na przykład
ns=[[30],[30],[100]],bar=0,N=20. Istnieje granica, wd=7.5której suma wartości zmiennoprzecinkowych skacze z 19 do 21. Nie oczekuje się, że rozwiążesz te przypadki. (podziękowania dla członka społeczności Arnaulda za wskazanie tej sprawy)
Przykład wejścia i wyjścia
Bardzo niezoptymalizowany przykład Python3:
from math import floor
def main(_l, bar, N):
# sum all votes to calculate bar in votes
votes = sum(sum(_) for _ in _l)
# nullify all parties that didn't pass the bar
_l = [[__ if __ >= bar * votes else 0 for __ in _] for _ in _l]
# find divisor for all parliament seats
divisor = find_divisor([sum(_) for _ in _l], N)
# find divisor for each 'coalition'
divisors = [find_divisor(_, floor(sum(_)/divisor)) for _ in _l]
# return final results
return [[floor(___/_) for ___ in __] for _, __ in zip(divisors, _l)]
def find_divisor(_l, N, _min=0, _max=1):
s = sum(floor(_ / _max) for _ in _l)
if s == N:
return _max
elif s < N:
return find_divisor(_l, N, _min, (_max + _min) / 2)
else:
return find_divisor(_l, N, _max, _max * 2)
print(main(l, bar, N))Przykładowe dane wejściowe:
l = [[190970, 156473],
[138598, 173004],
[143666, 193442],
[1140370, 159468],
[258275, 249049],
[624, 819],
[1125881],
[152756],
[118031],
[74701]]
bar = 0.0325
N = 120I jego wydajność:
[[6, 4], [0, 5], [4, 6], [35, 5], [8, 8], [0, 0], [35], [4], [0], [0]]Kilka innych przykładowych wyników:
Jeśli bar=0.1uzyskamy interesujący spór między dwiema stronami, ponieważ żadna z mniejszych partii nie jest liczona:
[[0, 0], [0, 0], [0, 0], [60, 0], [0, 0], [0, 0], [60], [0], [0], [0]]A jeśli N=0(przypadek narożny) to oczywiście nikt nic nie dostaje:
[[0, 0], [0, 0], [0, 0], [0, 0], [0, 0], [0, 0], [0], [0], [0], [0]]d=7.5masz skok z 19 miejsc do 21 miejsc.