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.
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:
Példa
| valaszt.be | valaszt.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 |