Volby

Mafiáni nakonec byli chytřejší, než v organizaci pro boj s organizovaným zločinem čekali. Když zjistili, že podle tradičních pravidel není žádný mafián vhodným kandidátem na kápa, rozhodli se nechat tradici tradicí a uspořádat demokratické volby. Každý mafián napsal na listeček jedno jméno – přezdívku mafiána, kterému dává svůj hlas. Všechny lístečky se pak shromáždily na jednom místě a teď se čeká na jejich spočítání. Pokud nějaký kandidát dostane aspoň polovinu všech hlasů, stane se novým kápem, v opačném případě budou muset mafiáni vymyslet nějaký jiný způsob, jak kápa zvolit.

Informátorovi se podařilo proniknout až do místnosti, kde se budou hlasy přepočítávat, a chtěl by zjistit, zda někdo získal nadpoloviční většinu hlasů a případně kdo. Zbývá mu proštrachat se úhledně poskládanou hromádkou volebních lístků na stole. Aby to nebylo tak snadné, má informátor k dispozici jen svou hlavu, ve které si dokáže zapamatovat jen konstantní množství informací. Aby se vyhnul odhalení, může navíc s hromádkou manipulovat jen velmi opatrně: vždy může nějaký volební lístek vzít, přečíst si ho, a pak ho musí zase vrátit na své místo. Pomůžete mu?

Řečeno formálněji, váš algoritmus zná celkový počet lístků N a kromě toho má k dispozici orákulum, kterého se může ptát na jméno na i-tém volebním lístku. Vaším cílem je zjistit, zda se nějaké jméno vyskytuje více než N/2-krát, přičemž smíte použít jen konstantní množství paměti. Jména jsou konstantně velká a umíte porovnávat, zda se dvě jména rovnají, ale už o nich nemůžete předpokládat nic dalšího (nejde například říct, zda je jedno jméno "menší" než druhé, nejdou hešovat atd.).