Пришло время ... подсчитать голоса!

Сегодня во всей моей стране проходят местные выборы. Здесь количество мест для каждой вечеринки определяется методом Д'Хондта . Ваша цель состоит в том, чтобы реализовать программу или функцию, которая будет определять, сколько мест получает каждая сторона, в кратчайшем количестве байтов.

Для этого метода есть фиксированное количество мест для распределения, и это делается так:

1. Каждой партии присваивается переменный номер, который начинается с количества полученных голосов.
2. Затем первое место отводится партии, которая имеет наибольшее значение в своей переменной, а затем это значение для этой партии становится их общим числом голосов, разделенным на 1+seatsокругленное число, где seatsэто количество мест уже есть (поэтому после получения во-первых, их голоса делятся на 2 и на 3 после получения второго места).
3. После этого голоса сторон снова сравниваются. Процесс продолжается до тех пор, пока не будут назначены все места.

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

вход

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

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

Выход

Вы должны вывести список мест, которые получила каждая партия. В приведенном выше примере это было бы что-то вроде

8,5,9,2,1,0

Они должны быть в том же порядке, что и стороны на входе.

Примеры

5
3,6,1

outputs: 2,3,0

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

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

бонус

Бонус -20%, если взять имя сторон в качестве входных данных и указать их в выходных данных, например:

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}

Эта полная программа имеет длину 33 байта и соответствует условиям бонуса.

Попробуйте онлайн в интерпретаторе CJam .

Пример запуска

$ 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]

Как это устроено

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 байт - 20% = 28,8

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

Это дает право на бонус.

Попробуйте онлайн: демонстрация или тестовая привязь

Объяснение:

                                       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 байт

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}

Примечания:

• Требуется современный браузер / движок с поддержкой ES6. Проверено в Firefox.
• Использует очень важный /-~++оператор :)

Пример использования:

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

Pyth - 54 байта

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

Формат ввода (стандартный):

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

Выходной формат (стандартный вывод):

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

Используемые переменные:

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"

Входное пространство отделено количеством мест в последнюю очередь.

Попробуй меня .