Informatika gyűjtemény

Egy szinttel feljebb Választási rendszerek

2004050607080910

NézetNyomtat

Választási rendszerek

Olyan választásokat vizsgálunk, ahol $n \ge 2$ választó $m \ge 3$ jelölt közül választ. Feltesszük, hogy minden választónak van egy egyértelmű preferencia listája, vagyis a jelölteket sorba tudja állítani aszerint, hogy kit szeretne leginkább, és kit legkevésbé.
Például, ha A,B és C közül választhatunk, akkor egy v választó listája így nézhet ki: B > C > A, ami azt jelenti, hogy B-t szeretné választani, de ha őt nem lehet, akkor C-nek jobban örülne, mint A-nak.
A választók preferencia listájának halmazát választói profilnak nevezzük. Ezt célszerű táblázatban is ábrázolni.
A négy legismertebb rendszer:

Relatív többség

Minden választó egyetlen szavazatot ad le (természetesen a saját preferencia listája első helyén álló jelöltre), és az a jelölt nyer, aki a legtöbb szavazatot kapta.

Abszolút többség

Minden választó egyetlen szavazatot ad le (természetesen a saját preferencia listája első helyén álló jelöltre). Ha van olyan jelölt, aki az összes szavazat felénél több szavazatot kap, megnyeri a választást. Ha nincs, akkor a két legtöbb szavazatot kapott jelölt egy második fordulóban újra összecsap. Holtverseny esetén az ábécérendben előbb állók jutnak a második fordulóba.

Condorcet-párharcok

A jelölteket páronként hasonlítjuk össze. (Bármely két jelölt közül bármely választó az egyiket előrébb sorolja.) Az nyer, aki az összes párharcot megnyerte.

Borda-pontozás

A választók a teljes preferencia listájukat felfedik. Az első helyre sorolt jelölt $p_1$ pontot kap, a második $p_2$-t és így tovább. Összeadjuk a pontokat, és az nyer, akinél legnagyobb ez az összeg. Feltesszük, hogy $p_1 > p_2 > p_3 > \ldots > p_n$. A legegyszerűbb Borda-pontozás, amikor mindenki annyi pontot kap egy választótól, ahány jelölt mögé került a preferencia listán.

Részletek, irodalom

Feladat

Írj programot, ami beolvas egy választói profilt, és mind a négy rendszerre megadja a választás győztesét. Ha valamelyik módszer szerint nincs győztes, akkor ezt is ki kell írni, ha több győztes van (holtverseny), akkor minden győztest meg kell adni.

Bemenet

Az első sor a választók $2\le n \le 10000$ számát és a jelöltek $3\le m \le 20$ számát tartalmazza, szóközzel elválasztva. A második sor a $p_1 > p_2 > p_3 > \ldots > p_n$ Borda-pontokat adja meg. A következő $n$ sorban a választói profil található, minden sor egy választó preferencia listája, a jelölteket az angol ábécé kisbetűi jelzik.

Kimenet

A négy módszerre adjuk meg a választás győztesét (győzteseit), összesen 4 sorban:
R: a
A: a
C: b
B: ac

Példa

valaszt.bevalaszt.ki
17 4
3 2 1 0
adcb
adcb
adcb
adcb
adcb
adbc
adbc
adbc
bcda
bcda
bcda
bcda
bcda
cdba
cdba
cdba
cdba
R: a
A: b
C: c
B: d