Zadanie

Mr. Miro sa nenaučil na test, tak sa musí spoľahnúť na svoje hekerské schopnosti. Okrem Mr. Mira sa testu účastní $n > 1$ študentov. Skúšajúci postupne zadáva otázky testu. Každú otázku najprv prečíta a dá na výber dve možnosti, z ktorých je práve jedna správna. Skôr, ako Mr. Miro napíše svoju odpoveď, je schopný pri každej otázke zistiť všetky odpovede ostatných študentov. Potom, čo všetci študenti (vrátane Mr. Mira) napíšu svoju odpoveď, skúšajúci ohlási správnu odpoveď a pokračuje ďalšou otázkou. Správna odpoveď je hodnotená $0$ bodmi a nesprávna $-2$ bodmi, avšak nesprávna odpoveď Mr. Mira je hodnotená len $-1$ bodom, lebo Mr. Miro hekol hodnotiaci systém. Taktiež si Mr. Miro pri hekovaní nastavil $2^{n-1}$ bodov, pričom ostatní študenti začínali s $0$ bodmi. Dokážte, že Mr. Miro môže zahlásiť: „Easy!“ a isto vie v teste skončiť najlepšie spomedzi všetkých študentov bez ohľadu na to, koľko otázok má test.

Na začiatok spravíme niekoľko úvah, ktorými si úlohu trochu spríjemníme, aby sa nám s ňou ľahšie pracovalo. Bodovanie v teste je trochu divné, preto ho pozmeňme. Za správnu odpoveď bude \(1\) bod, za nesprávnu \(-1\) bod pre študentov a \(0\) bodov pre Mr. Mira. Môžeme si to predstaviť tak, že skúšajúci dá po každej otázke každému skúšanému (aj Mr. Mirovi) po jednom bode. Takáto úprava nezmení poradie študentov, ktoré nás zaujíma, preto ju môžeme urobiť. Taktiež vieme povedať, že ak všetci študenti odpovedia rovnako, Mr. Miro dá rovnakú odpoveď ako oni. Takéto otázky poradie vôbec neovplyvnia, takže ich nemusíme uvažovať. Musíme taktiež zobrať do úvahy, že Mr. Miro môže mať jednoducho smolu – môže sa stále mýliť. Tak si rovno pridajme do našich predpokladov, že Mr. Miro odpovedá na každú otázku nesprávne.

Premyslite si, že ak Mr. Miro skončí najlepšie za takýchto podmienok, skončí najlepšie aj za podmienok a bodovania, ktoré sú v zadaní úlohy. Dospeli sme tak k nasledovnej interpretácii úlohy. Pri každej otázke sa študenti svojimi odpoveďami rozdelia na dve neprázdne množiny a Mr. Miro vyberie, ktorá množina študentov stratí bod a ktorá množina získa bod. Peknú moc sme našimi úvahami dostali, však? Úloha už znie viac uchopiteľnejšie. Poďme teraz opísať, ako bude Mr. Miro odpovedať.

Mr. Miro si rozdelí študentov podľa ich odpovedí na dve množiny. Pokiaľ sa takéto rozdelenie vyskytlo prvýkrát, pridá bod ľubovoľnej množine. Ak sa už takéto rozdelenie vyskytlo, pričom naposledy pridal bod množine \(A\), teraz množine \(A\) bod strhne.

V otázkach s rovnakým rozdelením študentov dostáva každý študent striedavo \(+1\) a \(-1\) bod. Preto jeden študent môže získať najviac \(1\) bod pre jedno rozdelenie. Všetkých rozdelení \(n\) študentov na dve neprázdne množiny je \(2^{n-1} - 1\) (premyslite si to). Preto môže jeden študent dosiahnuť najviac \(2^{n-1} - 1\) bodov v celom teste, čo je ostro menej ako body Mr. Mira. Týmto spôsobom teda Mr. Miro skončí v teste najlepšie.

Komentár

Pri tejto úlohe bolo ťažké prísť na hlavnú myšlienku, ako Mr. Miro bude odpovedať. Na to bolo potrebné identifikovať, čo znamená číslo \(2^{n-1}\) v zadní úlohy, a uvedomiť si, že súvisí s počtom rozdelení \(n\) študentov na dve množiny. Po tomto geniálnom nápade sa úloha môže zdať aj jednoduchá. Jadro riešenia sa dalo pekne stručne spísať, ako to možno vidieť v posledných dvoch odsekoch vzoráku.

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.