Вступление

На всеобщих выборах хотелось бы рассчитать постоянную цену за место в парламенте. Это означает, что для N >= 0распределения мест и списка nsголосов для каждой партии мы бы хотели найти число d,

sum(floor(n/d) for n in ns) == N 

Чтобы сделать вещи интересными (и больше похожими на реальный мир), мы добавим еще два факта:

1. Две партии могут собираться в «коалицию», так что места в «коалиции» предоставляются суммой голосов за все партии в ней. Затем места, которые получила «коалиция», распределяются между партиями аналогичным образом (найдите делитель и т. Д.)

2. Партия, которая не набрала определенный процент голосов (например, 3,25%), автоматически получает 0 мест, и ее голоса не учитываются как «коалиция».

Вызов

Тебе дали :

1. Список списков, каждый из вложенных списков содержит целые числа (количество голосов) и имеет длину 1 для одной партии или длину 2 для «коалиции».
2. Минимальный процент голосов (он же «бар» за «заграждение»), чтобы получить места, в виде дроби (таким образом, 3,25% дается как 0,0325)
3. Общее количество мест, которое будет распределено между всеми сторонами (целое число)

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

Победитель - это код с наименьшим количеством байтов.

Угловые чехлы:

• Там может (и обычно будет) более одного возможного делителя. Поскольку его нет в выводе, это не имеет значения.
• Представьте себе, N=10и ns = [[1]], таким образом, делитель может быть 0,1 (не целое число)
• В некоторых случаях не может быть решена, например ns=[[30],[30],[100]], bar=0, N=20. Существует граница, с d=7.5которой сумма скачанных значений возрастает с 19 до 21. Вы не должны решать эти случаи. (спасибо члену сообщества Арно, который указал на это дело)

Пример ввода и вывода

Очень неоптимизированный пример 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))

Пример ввода:

l = [[190970, 156473], 
    [138598, 173004], 
    [143666, 193442], 
    [1140370, 159468], 
    [258275, 249049], 
    [624, 819], 
    [1125881], 
    [152756], 
    [118031], 
    [74701]]
bar = 0.0325
N = 120

И его вывод:

[[6, 4], [0, 5], [4, 6], [35, 5], [8, 8], [0, 0], [35], [4], [0], [0]]

Еще несколько примеров выходных данных:

Если bar=0.1мы получим интересное противостояние между двумя сторонами, так как ни одна из меньших сторон не учитывается в:

[[0, 0], [0, 0], [0, 0], [60, 0], [0, 0], [0, 0], [60], [0], [0], [0]]

И если N=0(угловой случай), то, конечно, никто ничего не получает:

[[0, 0], [0, 0], [0, 0], [0, 0], [0, 0], [0, 0], [0], [0], [0], [0]]

05AB1E , 42 39 байт

ÐOOI*@*DO¸I¸¸2Fнζε`sDO/*Щ±/D{®1%Oòè‹+ï

Попробуйте онлайн!

05AB1E не хватает хорошей рекурсии, поэтому реализация бинарного поиска, как в ссылочном коде, была бы болезненной. К счастью, нам вообще не нужно искать делитель!

Давайте рассмотрим простой пример: [600, 379, 12, 9] голосов, 100 мест, нет коалиций, нет бара. Сначала мы вычисляем, сколько дробных мест получает каждая сторона, определяя дробные места какparty_votes * seats / sum_of_votes . В нашем примере это дает [60, 37,9, 1,2, 0,9].

Интересным моментом является то, что если партия получает fдробные места, она получает либо реальные, int(f)либо int(f) + 1реальные места. Это означает, что мы уже знаем, как будет распределено 60 + 37 + 1 = 98 мест, и у нас осталось 2 «бонусных места» для распределения между 4 сторонами (ни одна из сторон не может получить более 1 бонусного места). Кому предоставляются эти бонусные места? Стороны с наибольшим соотношением f / (int(f) + 1)(доказательство оставлено в качестве упражнения для читателя). В наших примерах соотношения таковы [0.98, 0.997, 0.6, 0.9], что первые две партии получают бонусное место для каждой.

Давайте посмотрим на код. Сначала мы заменяем счетчик голосов всех партий, которые не соблюдали планку, на 0:

Ð          # triplicate the first input (list of votes)
 OO        # flattened sum
   I*      # multiply by the second input (bar)
     @     # greater than? (returns 0 or 1)
      *    # multiply

Теперь, чтобы обойти отсутствие рекурсии, мы используем awkard 2Fдля повторения основного кода дважды. На первом проходе он распределяет все места между коалициями, а на втором проходе он распределяет места каждой коалиции между ее партиями. Поскольку первый проход выполняется только один раз, а второй проходит для каждой коалиции, это предполагает довольно большую занятую работу.

DO¸I¸¸2Fнζε`s    # i don’t want to detail this tbh

Хорошо, после этого непонятного бита вершина стека теперь является списком голосов (голоса коалиции на первом проходе, партия голосует на втором), а ниже это количество мест, которые нужно выделить. Мы используем это для вычисления списка фракционных мест:

D        # duplicate
 O       # sum  
  /      # divide each vote count by the sum
   *     # multiply by the number of seats
    ©    # save the fractional seats in variable r

Теперь мы вычисляем соотношения:

Ð            # triplicate
 ±           # bitwise not
  /          # divide

Побит не работает красиво, здесь. Он усекает целое число, добавляет 1 и отрицает все в одном байте. Зачем отрицать? В 05AB1E деление на 0 возвращает 0, и нам нужно, чтобы они сортировались последними.

D {# отсортированная копия соотношений ® 1% # дробных голосов мод 1 (иначе десятичные части) O # сумма вышеупомянутого (это количество бонусных мест) ò # раунд до ближайшего (требуется из-за числа с плавающей запятой bs) è # индекс в отсортированных соотношениях

Это дает нам (n + 1) -й лучший коэффициент, где n - количество бонусных мест (+1, потому что индексирование основано на 0). Таким образом, стороны, которые получают бонусное место, - это те, чье соотношение строго меньше этого.

‹      # less than
 +     # add to the fractional seats
  ï    # truncate to integer

Python 2 , 220 байт

def d(l,n,a=0,b=1.):s=sum(x//b for x in l);return s-n and d(l,n,*[a,b,(a+b)/2,b*2][s>n::2])or b
def f(l,b,n):l=[[x*(x>=b*sum(sum(l,[])))for x in r]for r in l];return[[v//d(x,sum(x)//d(map(sum,l),n))for v in x]for x in l]

Попробуйте онлайн!

В основном просто гольф эталонной реализации ...

Желе , 63 36 байт

F×S<ḷ×ḷµ§⁵:,1_×¥:@"§IṠʋ÷9ɗ¥ƬṪṪƲ¥¥@⁺"

Попробуйте онлайн!

Полная программа, принимающая три аргумента: количество голосов в формате, описанном вопросом, планка и N в указанном порядке. Возвращает список списков мест. Нижний колонтитул на TIO просто для того, чтобы выделить структуру списка вывода. (В противном случае желе прячется[] за списки из одного элемента.)

объяснение

F×S<ḷ×ḷµ§⁵:,1_×¥:@"§IṠʋ÷9ɗ¥ƬṪṪƲ¥¥@⁺"

F                                   | Flatten vote counts
 ×                                  | Multiply by bar
  S                                 | Sum
   <ḷ                               | Less than original vote counts (vectorises and respects input list structure)
     ×ḷ                             | Multiply by original vote counts
       µ                            | Start a new monadic link with processed vote counts as input
        §                           | Vectorised sum

         ⁵                      ¥@  | Apply the following as a dyad with the number of seats as the right argument and the vectorised sum of votes as left

           ,                  Ʋ¥    |(*)- Pair vote counts with seat sum and find divisor using the following as a monad:
            1             ¥Ƭ        |     - Starting with 1 as a guess for divisor, and using the paired vote counts and seat sum as the right argument, apply the following as a dyad, collecting intermediate results, until the results repeat
                         ɗ          |       - Following as a dyad:
                      ʋ             |         - Following as a dyad:
                :@"                 |           - Integer divide with arguments zipped and reversed, i.e. divide cote counts by current divisor guess and leave total seats alone
                   §                |           -  Vectorised sum (will sum vote counts but leave seat number alone)
                    I               |           - Find differences i.e. desired total seats minus current calculation based on current divisor guess. Will return a list.
                     Ṡ              |           - Sign of this (-1, 0 or 1)
                       ÷9           |         - Divide by 9 (-0.111, 0 or 0.111)
             _×¥                    |     - Now multiply the current divisor guess by this and subtract it from that guess to generate the next guess. If the current guess is correct, the guess will be unchanged and so the Ƭ loop will terminate
                            ṪṪ      |     - Take the last item twice (first time to get the final
                               output of the Ƭ loop and second to remove the list introduced by I
         :                          | - Integer divide the vote counts by the output of the above

                                  ⁺"| Apply the above dyad from the step labelled (*) again, this time with the output of the previous step (total votes per coalition) as right argument and the vote counts as left argument, zipping the two together and running the link once for each pair

Оригинальная подача (больше, но эффективнее)

Желе , 63 байта

:S_3ƭƒṠ©ḢḤ;$;ṪƲṖÆm;ḊƲ®‘¤?ߥ/}ṛ¹?,
1,0;çḢḢ
FS×Ċ’<ḷ×ḷµ:"§:⁵ç$$ç"Ɗ

Попробуйте онлайн!

Вольфрам - без гольфа

Было просто любопытно решить ее с помощью LinearProgramming , а не кандидата в гольф, но, возможно, интересный подход к проблеме:

findDivisor[l_, n_] := Quiet@Module[{s, c, r, m, b, cons, sol},
   s = Length[l];
   c = Append[ConstantArray[0, s], 1];
   r = Thread[Append[IdentityMatrix[s], -l]];
   m = Append[Join[r, r], Append[ConstantArray[1, s], 0]];
   b = Append[Join[ConstantArray[{0, -1}, s], ConstantArray[{-1, 1}, s]], {n, 0}];
   cons = Append[ConstantArray[Integers, s], Reals];
   sol = LinearProgramming[c, m, b, 0, cons];
   {1/sol[[-1]], Most@sol}
   ]
solve[l_, bar_, n_] := 
 With[{t = l /. x_ /; x <= bar Total[l, 2] -> 0},
  With[{sol = findDivisor[Total /@ t, n]}, 
   {First@sol, MapThread[findDivisor, {t, Last@sol}]}]
  ]

Прочитайте объяснение и попробуйте!