Problem E
Ekki minn forseti

Mynd fengin af wikimedia.org

Á Íslandi getur það ekki gerst að frambjóðandinn með lægri fjölda atkvæða frá þjóðinni sigri þann sem er með flest atkvæði. Þó svo kosningakerfið okkar sé ekki viðkvæmt fyrir nákvæmlega þessum galla að þá er það langt frá fullkomnun. Forsetakosningakerfi Íslands er þannig háttað að hver kjósandi velur sér einn frambjóðanda til að kjósa og sá frambjóðandi sem fær hæstan fjölda atkvæða sigrar.

Ólafur Þórður Harðarson, prófessor í stjórnmálafræði við Háskóla Íslands, hefur gagnrýnt kosningakerfi Íslands í áratugi. Í gamalli grein skrifaði hann um einn galla núverandi kerfis. Þar skoðaði hann möguleikann á um það bil jafnri dreifingu milli frambjóðanda. Með tveimur frambjóðendum þyrfti sigurvegarinn að fá yfir helming atkvæða til að sigra sem hljómar eins sanngjarnt og hægt er. Hins vegar ef tíu manns eru í framboði að þá getur dugað að fá einungis rétt yfir $10\% $ atkvæða til að ná kjöri. Þar sem að einungis er skoðað fyrsta kost hvers kjósanda að þá er möguleiki að hátt í $90\% $ þjóðarinnar vilji síst hafa þann sem er kjörinn sem forseta í því tilviki.

Annar galli kerfisins sem oft er gagnrýndur er það sem kallast glötuð atkvæði. Oft kemur fram í skoðanakönnum fyrir kosningar hvaða tveir frambjóðendur eru líklegastir til sigurs. Munurinn getur verið það mikill milli þeirra og þriðja, fjórða eða jafnvel níunda sætis að það sé víst að skoðanakönnunin sýni hvaða tveir frambjóðendur verða efstir. Þá gæti kjósanda fundist atkvæði sitt glatast því það mun ekki hafa áhrif á barráttu efstu tveggja sætanna. Sumir kjósendur jafnvel velja þá á milli efstu tveggja frambjóðendanna og kjósa þann sem þeim lýst best, eða skást, á.

Ein lausn væri að hafa fleiri umferðir til að tryggja að atkvæði hvers kjósanda hafi áhrif en fyrir litla þjóð eins og Ísland getur það reynst óþarflega kostnaðarsamt. Sem betur fer er til kerfi sem krefst aðeins einnar umferðar kosninga og hefur ekki áðurnefnda galla. Kerfið byggist á því að raða frambjóðendum eftir því hversu vel kjósanda líst á frambjóðandann. Helsti galli þessa kerfis er þá að það er örlítið flóknara að kjósa. Fyrsta val hvers kjósanda ákvarðar þá upprunalegu niðurstöðu kosningarinnar, sem er þá sama niðurstaða og núverandi kerfi myndi enda á. Það sem breytist er að á meðan enginn frambjóðandi er með meirihluta atkvæða, þá er frambjóðandinn með fæstan fjölda atkvæða fjarlægður úr kosningunum. Atkvæði með þann frambjóðanda eru því uppfærð og næsta val kjósandans tekur því við. Þegar einhver frambjóðandi nær meirihluta að þá hefur sigurvegari kosningarinnar verið ákvarðaður.

KFFÍ notaði tímavélina sína til að ferðast á kosningatímabilin og spyrja alla landsmenn hvernig atkvæðið þeirra hefði verið í þessu nýja kosningakerfi. Félagið ferðaðist aftur í tímann hægt og rólega og fór það mjög vel. Sérhver kjósandi skilaði röðuðum lista með hverjum einasta frambjóðanda. Þegar kom að því að ferðast fram í tímann til að komast aftur til ársins $2023$ að þá kom í ljós að tímavélin virkaði ekki í báðar áttir. Meðlimir KFFÍ eru því fastir á árinu $1952$ og ekki var mikið um tölvur á Íslandi þá. Geta þeir því ekki skrifað forrit til að herma eftir kosningunum með nýju atkvæðunum. Þeir ákveða að frysta sig til að komast aftur til ársins $2023$ og Arnar skildi eftir þessar leiðbeiningar í von um að einhver útfæri forritið fyrir sig.

Inntak

Fyrsta línan í inntakinu inniheldur tvær heiltölur $n$, fjölda atkvæða, og $m$, fjölda frambjóðenda, aðskilnar með bili.

Næst koma $m$ línur þar sem hver lína inniheldur nafn frambjóðanda. Nöfn innihalda einungis enska stafi. Fjöldi tákna í hverju nafni er á bilinu $1$ upp í $50$.

Að lokum koma $n$ línur þar sem hver lína inniheldur atkvæði. Hvert atkvæði samanstendur af $m$ heiltölum, tölurnar $1$ upp í $m$, þar sem hver þeirra kemur fyrir nákvæmlega einu sinni, og lýsir því í hvaða röð kjósandinn setur frambjóðendurnar. Fyrsta talan í línuni vísar því í fyrsta kost frambjóðandans, næsta vísar í annan kost og svo framvegis. Tölurnar vísa í frambjóðendur í röðinni sem þeir komu í inntakinu.

Ef tveir frambjóðendur eru með jafnmörg atkvæði á einhverjum tímapunkti í ferlinu að þá er frambjóðandinn sem kemur á undan í inntakinu talinn vera ofar í röðinni.

Úttak

Skrifaðu út eina línu með nafni sigurvegara kosninganna.

Stigagjöf

10 3
Arnar
Bjarki
Unnar
1 2 3
1 3 2
1 3 2
2 1 3
2 3 1
2 3 1
2 3 1
3 1 2
3 1 2
3 2 1

Arnar

12 2
Winner
Loser
1 2
1 2 
2 1
2 1
1 2
2 1
1 2
1 2
1 2
1 2
1 2
1 2

Winner

11 4
Bjarki
Asta
Unnar
Arnar
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
2 1 3 4
2 1 3 4
2 1 3 4
3 4 2 1
4 3 2 1
4 3 2 1

Asta