pengantar

Dalam pemilihan umum, orang ingin menghitung harga konstan per kursi parlemen. Ini berarti bahwa untuk N >= 0kursi yang akan didistribusikan dan daftar nssuara per partai, kami ingin menemukan nomor dsedemikian rupa

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

Untuk membuat hal-hal menarik (dan lebih mirip dunia nyata), kami menambahkan dua fakta lagi:

1. Dua partai dapat berkumpul dalam 'koalisi', sehingga kursi diberikan kepada 'koalisi' dengan jumlah suara untuk semua pihak di dalamnya. Kemudian kursi yang didapat 'koalisi' terbelah antara partai-partai dengan cara yang sama (temukan pembagi, dll.)

2. Partai yang tidak lulus persentase tertentu dari suara (mis. 3,25%) secara otomatis mendapat 0 kursi, dan suaranya tidak masuk dalam 'koalisi'.

Tantangan

Anda diberikan:

1. Daftar daftar, masing-masing daftar bersarang berisi bilangan bulat (jumlah suara), dan panjangnya 1 untuk satu partai, atau panjang 2 untuk 'koalisi'.
2. Persentase minimal suara (alias "bilah" untuk "rentetan") untuk mendapatkan kursi, sebagai fraksi (jadi 3,25% diberikan sebagai 0,0325)
3. Total jumlah kursi yang akan didistribusikan antara semua pihak (integer)

Anda harus mencetak struktur daftar bersarang yang sama, dengan jumlah suara diganti dengan kursi parlemen.

Pemenang adalah kode dengan jumlah byte terkecil.

Kasus sudut:

• Mungkin ada (dan biasanya akan) lebih dari satu pembagi yang mungkin. Karena tidak ada dalam output, itu tidak masalah.
• Bayangkan N=10dan ns = [[1]], jadi pembagi mungkin 0,1 (bukan bilangan bulat)
• Beberapa kasus tidak dapat diselesaikan, misalnya ns=[[30],[30],[100]], bar=0, N=20. Ada batas di d=7.5mana jumlah nilai dasar melompat dari 19 hingga 21. Anda tidak diharapkan menyelesaikan kasus ini. (terima kasih kepada anggota komunitas Arnauld untuk menunjukkan kasus ini)

Contoh Input dan Output

Contoh Python3 yang sangat tidak dioptimalkan:

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))

Input contoh:

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

Dan hasilnya:

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

Beberapa contoh lagi keluaran:

Jika bar=0.1kami mendapat pertikaian yang menarik antara dua pihak karena tidak ada satu pun dari partai yang lebih kecil dihitung:

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

Dan jika N=0(kasus sudut) maka tentu saja tidak ada yang mendapat apa-apa:

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

05AB1E , 42 39 byte

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

Cobalah online!

05AB1E tidak memiliki rekursi yang baik, jadi menerapkan pencarian biner seperti pada kode referensi akan menyakitkan. Untungnya, kita tidak perlu menemukan pembagi sama sekali!

Mari kita gunakan contoh sederhana: [600, 379, 12, 9] suara, 100 kursi, tidak ada koalisi, tidak ada bar. Pertama, kami menghitung berapa banyak kursi fraksional masing-masing pihak, mendefinisikan kursi fraksional sebagai party_votes * seats / sum_of_votes. Dalam contoh kami, itu menghasilkan [60, 37.9, 1.2, 0.9].

Yang menarik adalah bahwa jika suatu pesta mendapat fkursi fraksional, itu akan mendapatkan kursi baik int(f)atau int(f) + 1nyata. Ini berarti kita sudah tahu bagaimana 60 + 37 + 1 = 98 kursi akan dialokasikan, dan kita dibiarkan dengan 2 "kursi bonus" untuk didistribusikan di antara 4 pihak (tidak ada pihak yang bisa mendapatkan lebih dari 1 kursi bonus). Kepada siapa kursi bonus ini pergi? Pihak-pihak dengan rasio tertinggi f / (int(f) + 1)(bukti dibiarkan sebagai latihan untuk pembaca). Dalam contoh kami, rasionya adalah [0.98, 0.997, 0.6, 0.9], jadi dua pihak pertama masing-masing mendapat kursi bonus.

Mari kita lihat kodenya. Pertama, kami mengganti jumlah suara semua pihak yang tidak memenuhi bilah dengan 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

Sekarang, untuk mengatasi kekurangan rekursi, kami menggunakan awkard 2Funtuk mengulangi kode utama dua kali. Pada pass pertama akan mendistribusikan total kursi antara koalisi, dan pada pass kedua akan mendistribusikan kursi masing-masing koalisi antara pihak-pihaknya. Karena operan pertama berjalan hanya sekali, tetapi operan kedua berjalan untuk setiap koalisi, ini melibatkan banyak pekerjaan yang sibuk.

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

Oke, setelah bit yang tidak jelas ini, bagian atas tumpukan sekarang daftar suara (suara koalisi pada pass pertama, suara partai pada yang kedua), dan di bawah itu adalah jumlah kursi yang dialokasikan. Kami menggunakan ini untuk menghitung daftar kursi fraksional:

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

Sekarang, kami menghitung rasio:

Ð            # triplicate
 ±           # bitwise not
  /          # divide

Bitwise tidak berfungsi dengan baik, di sini. Ini memotong ke integer, menambahkan 1, dan meniadakan, semua dalam satu byte. Mengapa meniadakan? Di 05AB1E, pembagian dengan 0 menghasilkan 0, dan kami membutuhkan ini untuk mengurutkan terakhir.

D {# salinan disortir dari rasio ®1% # suara fraksional mod 1 (alias bagian desimal) O # jumlah di atas (ini adalah jumlah kursi bonus) ò # putaran ke terdekat (diperlukan karena titik mengambang bs) è indeks ke dalam rasio yang diurutkan

Ini memberi kita (n +1) rasio terbaik, di mana n adalah jumlah kursi bonus (+1 karena pengindeksan adalah berbasis 0). Dengan demikian, pihak-pihak yang mendapatkan kursi bonus adalah mereka yang memiliki rasio sangat kurang dari ini.

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

Python 2 , 220 byte

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]

Cobalah online!

Pada dasarnya hanya golf dari implementasi referensi ...

Jelly , 63 36 byte

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

Cobalah online!

Program lengkap yang mengambil tiga argumen: jumlah suara dalam format yang dijelaskan oleh pertanyaan, bilah, dan N dalam urutan itu. Mengembalikan daftar daftar jumlah kursi. Footer pada TIO hanya untuk menyoroti struktur daftar output. (Kalau tidak, Jelly menyembunyikan []daftar item tunggal.)

Penjelasan

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

Pengajuan Asli (lebih besar tetapi lebih efisien)

Jelly , 63 byte

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

Cobalah online!

Wolfram - tidak ada golf

Hanya ingin tahu untuk menyelesaikannya menggunakan LinearProgramming , bukan kandidat golf, tapi mungkin pendekatan yang menarik untuk masalah:

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

Baca beberapa penjelasan dan cobalah!