Problem F
Mandatfordeling

Betragt et valg, hvor $m$ mandater skal fordeles på $n$ partier. Lad $v_i$ betegne antallet af stemmer på parti $i\in \{1,\dots ,n\}$.

For at fordele de $m$ pladser mellem partierne nogenlunde i forhold til deres stemmeandel kan man bruge den såkaldte D’Hondts metode. Den virker på følgende måde: For hvert parti beregnes en brøk; i første omgang brøken $v_i/1$, som er lig med antallet af stemmer på partiet. Partiet med den største brøk tildeles nu et mandat, og partiets brøk genberegnes. Denne proces bliver gentaget, til alle $m$ mandater er blevet tildelt. Udtrykket for brøken er

hvor $s_i$ betegner antallet af mandater, der hidtil er blevet tildelt parti $i$; i første omgang er $s_i=0$ for alle partier.

Indlæsning

På første linje står antallet $n$ af partier og antallet $m$ af mandater, med $n,m\in \{1,\dots ,20000\}$, adskilte af et enkelt mellemrum. På hver af det følgende $n$ linjer står heltallet $v_i$, som opfylder $1\le v_i\le 50000000$ og $v_1+\cdots +v_n\ge m$. Indlæsningen er konstrueret således, at det sidste mandat er entydigt bestemt; man behøver altså ikke at bekymre sig om mekanismer for stemmeligehed.

Testgrupper

Der er to testrupper. Testgruppe 1, som er værd 80 ud af det sammenlagt 100 points, opfylder desuden begrænsningen $m\cdot v_i\le 2^{31}$. Dermed undgås nogle afrundningsproblemer, som kan opstå i nogle programmeringssprog i afhængighed af den valgte brøk- eller decimaltalsrepræsentationen.

Udskrift

Mandatfordelingen for hvert parti på en linje for sig. Rækkefølgen er den samme som i indlæsningen.

Forklaring af eksempel 4

Parti 1 får det første mandat, fordi det har flest stemmer; dets brøk bliver genberegnet til $\frac{17}{2}$. Parti 2 får næste mandat, fordi $10>\frac{17}{2}$; partiets brøk bliver genberegnet til $\frac{10}{2}=5$. Det tredje mandat går til parti 1, fordi $\frac{17}{2}>5$; partiets nye brøk er $\frac{17}{3}$. Sågar det sidste mandat går til parti 1, fordi $\frac{17}{3}>5$. Parti 1 får altså 3 mandater, parti 2 får 1 mandat.

2 2
10
10000000

0
2

2 3
12
11

2
1

2 4
12
11

2
2

2 4
17
10

3
1

4 14
38
35
36
37

4
3
3
4