Introdução

Em uma eleição geral, alguém gostaria de calcular um preço constante por assento no parlamento. Isso significa que, para N >= 0distribuir assentos e uma lista nsde votos por partido, gostaríamos de encontrar um número dtal que

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

Para tornar as coisas interessantes (e mais parecidas com o mundo real), adicionamos mais dois fatos:

1. Dois partidos podem se reunir em uma 'coalizão', de modo que os assentos sejam dados à 'coalizão' pela soma dos votos para todos os partidos nela. Em seguida, os assentos que a 'coalizão' obteve são divididos entre os partidos de maneira semelhante (encontre divisor, etc.)

2. Um partido que não aprovou uma certa porcentagem dos votos (por exemplo, 3,25%) obtém automaticamente 0 assentos, e seus votos não contam para uma 'coalizão'.

Desafio

Você recebe:

1. Uma lista de listas, cada uma das listas aninhadas, contém números inteiros (número de votos) e tem o comprimento 1 para um único partido ou o comprimento 2 para uma 'coalizão'.
2. Porcentagem mínima de votos (também conhecida como "barra" para "barragem") para obter assentos, como uma fração (portanto, 3,25% é dado como 0,0325)
3. Número total de assentos a serem distribuídos entre todas as partes (número inteiro)

Você deve imprimir a mesma estrutura de lista aninhada, com o número de votos substituído por cadeiras no parlamento.

Vencedor é o código com a menor quantidade de bytes.

Caixas de canto:

• Pode haver (e geralmente haverá) mais de um divisor possível. Como não está na saída, isso realmente não importa.
• Imagine N=10e ns = [[1]], portanto, o divisor pode ser 0,1 (não um número inteiro)
• Alguns casos não podem ser resolvidos, por exemplo ns=[[30],[30],[100]], bar=0, N=20. Há um limite com o d=7.5qual a soma dos valores com base salta de 19 para 21. Não é esperado que você resolva esses casos. (obrigado ao membro da comunidade Arnauld por apontar este caso)

Exemplo de entrada e saída

Um exemplo muito otimizado do 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))

Exemplo de entrada:

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

E sua saída:

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

Mais alguns exemplos de saídas:

Se bar=0.1obtivermos um impasse interessante entre duas partes, uma vez que nenhuma das partes menores é contada:

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

E se N=0(canto), é claro que ninguém recebe nada:

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

05AB1E , 42 39 bytes

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

Experimente online!

05AB1E não possui boa recursão, portanto, implementar uma pesquisa binária como no código de referência seria doloroso. Felizmente, não precisamos encontrar o divisor!

Vamos usar um exemplo simples: [600, 379, 12, 9] votos, 100 assentos, nenhuma coalizão, nenhuma barra. Primeiro, calculamos quantos assentos fracionários cada parte obtém, definindo assentos fracionados comoparty_votes * seats / sum_of_votes . No nosso exemplo, isso gera [60, 37,9, 1,2, 0,9].

O interessante é que, se uma festa conseguir fassentos fracionários, terá assentos iguais int(f)ou int(f) + 1reais. Isso significa que já sabemos como 60 + 37 + 1 = 98 dos assentos serão alocados e ficamos com 2 "assentos de bônus" para distribuir entre as quatro partes (nenhuma das partes pode obter mais de um assento de bônus). A quem esses assentos de bônus vão? As partes com a maior proporção def / (int(f) + 1) (prova deixada como exercício para o leitor). Em nossos exemplos, as proporções são [0.98, 0.997, 0.6, 0.9], portanto, as duas primeiras partes recebem um assento de bônus cada.

Vamos dar uma olhada no código. Primeiro, substituímos a contagem de votos de todas as partes que não atenderam à ordem por 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

Agora, para contornar a falta de recursão, usamos um awkard 2Fpara repetir o código principal duas vezes. No primeiro passo, distribuirá o total de assentos entre a coalizão e, no segundo, distribuirá os assentos de cada coalizão entre seus partidos. Como o primeiro passe é executado apenas uma vez, mas o segundo passa para cada coalizão, isso envolve bastante trabalho ocupado.

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

Ok, depois desse pedaço obscuro, o topo da pilha agora é uma lista de votos (votos da coalizão no primeiro passe, votos dos partidos no segundo), e abaixo desse número está o número de assentos a serem alocados. Usamos isso para calcular a lista de assentos fracionários:

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

Agora, calculamos as proporções:

Ð            # triplicate
 ±           # bitwise not
  /          # divide

Bitwise não funciona lindamente, aqui. Ele trunca para inteiro, adiciona 1 e nega, tudo em um único byte. Por que negar? Em 05AB1E, a divisão por 0 retorna 0, e precisamos deles para classificar por último.

D {# cópia ordenada dos índices ®1% # votos fracionários mod 1 (também conhecido como casas decimais) O # soma do acima (este é o número de assentos bônus) ò # arredondado para o mais próximo (necessário devido ao ponto flutuante bs) é # índice nas proporções ordenadas

Isso nos dá a (n + 1) th melhor relação, onde n é o número de assentos de bônus (+1 porque a indexação é baseada em 0). Assim, as partes que obtêm um assento de bônus são aquelas que têm uma proporção estritamente menor que isso.

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

Python 2 , 220 bytes

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]

Experimente online!

Basicamente, apenas um golfe da implementação de referência ...

Geléia , 63 36 bytes

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

Experimente online!

Um programa completo com três argumentos: o número de votos no formato descrito pela pergunta, bar e N nessa ordem. Retorna uma lista de listas de assentos. O rodapé no TIO é apenas para destacar a estrutura da lista da saída. (Caso contrário, Jelly esconde[] para listas de itens únicos.)

Explicação

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

Submissão original (maior, porém mais eficiente)

Geléia , 63 bytes

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

Experimente online!

Wolfram - sem golfe

Estava curioso para resolvê-lo usando o LinearProgramming , não um candidato a golfe, mas talvez uma abordagem interessante para um problema:

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

Leia algumas explicações e experimente!