Czas ... policzyć głosy!

Dzisiaj w całym kraju odbywają się wybory lokalne. Tutaj liczba miejsc dla każdej ze stron jest ustalana za pomocą metody D'Hondta . Twoim celem jest wdrożenie programu lub funkcji, która decyduje o tym, ile miejsc dostanie każda ze stron, w jak najkrótszej ilości bajtów.

W przypadku tej metody istnieje stała liczba miejsc do rozdzielenia i odbywa się to w następujący sposób:

1. Każda partia ma przypisaną zmienną liczbę, która zaczyna się od liczby głosów, które uzyskała.
2. Następnie pierwsze miejsce przyznawane jest partii, która ma największą wartość w swojej zmiennej, a następnie ta wartość dla tej partii staje się ich całkowitą liczbą głosów podzieloną przez 1+seats, zaokrągloną w dół, gdzie seatsjest liczba miejsc, które już ma (więc po uzyskaniu po pierwsze, ich głosy są dzielone przez 2, a przez 3 po uzyskaniu drugiego miejsca).
3. Następnie głosy partii są ponownie porównywane. Proces ten trwa do momentu przypisania wszystkich miejsc.

Jeśli najwyższa liczba to remis między dwiema lub więcej drużynami, jest ona rozstrzygana losowo (musi być losowa, nie może to być pierwsza z dwóch na liście).

Wejście

Otrzymasz numer N, który wskaże liczbę dostępnych miejsc oraz listę głosów otrzymanych przez każdą partię, w dowolnym formacie. Przykład:

25
12984,7716,13009,4045,1741,1013

Wynik

Powinieneś wypisać listę miejsc, które dostała każda ze stron. W powyższym przykładzie byłoby to coś w rodzaju

8,5,9,2,1,0

Powinny być w tej samej kolejności co strony w danych wejściowych.

Przykłady

5
3,6,1

outputs: 2,3,0

135
1116259,498124,524707,471681,359705,275007,126435

outputs: 45,20,21,19,14,11,5

Premia

-20% bonusu, jeśli weźmiesz nazwę partii jako dane wejściowe i podasz je w danych wyjściowych, na przykład:

25
cio:12984,pcc:7716,irc:13009,icb:4045,cub:1741,bb:1013

outputs

cio:8
pcc:5
irc:9
icb:2
cub:1
bb:0

CJam, 35,2 28,8 28,0 26,4

q2*~,m*mr{~)f/1=~}$<:(f{1$e=1\tp}

Ten pełny program ma 33 bajty długości i kwalifikuje się do premii.

Wypróbuj online w interpretatorze CJam .

Przykładowy przebieg

$ cjam seats <<< '[["cio"12984]["pcc"7716]["irc"13009]["icb"4045]["cub"1741]["bb"1013]]25'
["cio" 8]
["pcc" 5]
["irc" 9]
["icb" 2]
["cub" 1]
["bb" 0]

Jak to działa

q2*~   e# Repeat the input from STDIN twice. Evaluate.
       e# STACK: Array seats Array seats
,      e# Range: seats -> [0 ... seats-1]
m*     e# Take the cartesian product of the array from the input and the range.
mr     e# Shuffle the array. This makes sure tie breakers are randomized.
{      e# Sort by the following key:
  ~    e#     Dump: [["party" votes] number] -> ["party" votes] number
  f/   e#     Divide each: ["party" votes] number -> ["party"/number votes/number]
  1=   e#     Select: ["party"/number votes/number] -> votes/number
  ~    e#     Bitwise NOT.
}$     e#
<      e# Keep only the elements that correspond to seats.
:(     e# Shift each array.
       e# RESULT: S := [[number] ["party" votes] [number] ["party" votes] ...]
f{     e# For each A := ["party" votes]:
       e#     Push S.
  1$   e#     Push a copy of A.
  e=   e#     Count the occurrences of A in S.
  1\t  e#     Replace the vote count with the number of occurrences.
  p    e#     Print.
}      e#

Pyth, 36 bajtów - 20% = 28,8

J<_hCo/@eCQhNheN.S*UQUvzvz.e,b/JkhCQ

To kwalifikuje się do premii.

Wypróbuj online: Demonstracja lub Uprząż testowa

Wyjaśnienie:

                                       implicit: z = 1st input (as string)
                                                 Q = 2nd input (evaluated)

                      vz               evaluate z (#seats)
                     U                 generate the list [0,1,...,seats-1]
                   UQ                  generate the list [0,1,...,len(Q)-1]
                  *                    Cartesian product of these lists
                .S                     shuffle (necessary for break ties randomly)
     o                                 order these tuples N by:
        eCQ                               list of votes
       @   hN                             take the N[0]th vote count
      /      heN                          and divide by N[1]+1
   hC                                  extract the party index of the tuples
  _                                    reverse the list
 <                      vz             take the first #seats elements
J                                      and store them in J

                          .e     hCQ   enumerated map over the names of the parties
                                       (k = index, b = name):
                            ,             generate the pair:
                             b/Jk            name, J.count(k)
                                       print implicitely

JavaScript, 210 bajtów

v=(a,b,c,d,e,f,g)=>{d=Object.assign({},b),c={};for(g in b)c[g]=0;for(;a--;)e=0,f=Object.keys(d),f.forEach(a=>e=d[a]>e?d[a]:e),f=f.filter(a=>d[a]===e),f=f[~~(Math.random()*f.length)],d[f]=b[f]/-~++c[f];return c}

Uwagi:

• Wymaga nowoczesnej przeglądarki / silnika z obsługą ES6. Testowane w przeglądarce Firefox.
• Korzysta z bardzo ważnego /-~++operatora :)

Przykładowe użycie:

v(25, {cio:12984,pcc:7716,irc:13009,icb:4045,cub:1741,bb:1013})

Pyth - 54 bajty

AGZQ=kZK*]0lZVGJhOfqeTh.MZZ.e(kb)Z XJK1 XZJ/@kJ+@KJ1;K

Format wejściowy (stdin):

[25,[12984,7716,13009,4045,1741,1013]]

Format wyjściowy (standardowe wyjście):

[8, 5, 9, 2, 1, 0]

Zastosowane zmienne:

G = total number of seats
K = array of seats currently assigned to each party
k = number of votes for each party
Z = k/(K+1)
J = which party should have the next seat

Perl, 110

#!perl -pa
$n=pop@F;@x=map
0,@F;/a/,$x[$'/$n]++for(sort{$b-$a}map{map{($'/$_|0).rand.a.$i++}//..$n}@F)[0..$n-1];$_="@x"

Przestrzeń wejściowa oddzielona ostatnią liczbą miejsc.

Spróbuj mnie .