Zadanie

Ak máte akékoľvek otázky ohľadom tejto úlohy napíšte Mariánovi Horňákovi na

Zrejme ste už počuli mnoho mýtov o Kocúrkove. Je načase, aby vám konečne niekto povedal pravdu.

Skutočné Kocúrkovo pozostáva z troch ulíc: Agátovej, Bielej a Cesnakovej. Každá ulica obsahuje presne tisíc domov, ktoré sú očíslované od \(1\) po \(1\,000\), postupne, pozdĺž ulice. V každom dome majú jedného kocúra (a niekoľko mačiek, ktoré ale nie sú pre túto úlohu podstatné). Každý kocúr je aspoň trochu prefíkaný, niektoré sú viac prefíkané a na každej ulici nájdete presne jedného stopercentne prefíkaného kocúra. Vaša úloha je jednoduchá. Zistite, v ktorom dome sa nachádza stopercentne prefíkaný kocúr.

Hľadanie má, samozrejme, svoje pravidlá. V každom dome vám radi poradia všetko, čo vedia o prefíkaných kocúroch. Táto informácia je na každej ulici iná. Na jednej ulici však môžete navštíviť najviac \(100\) domov, potom vás už do žiadneho nepustia. V závislosti od toho, koľko domov navštívite, dostanete \(1\), \(2\) alebo \(3\) body. Akonáhle nie ste spokojní s výsledkom, môžete sa ľubovoľne veľakrát presunúť do paralelného vesmíru a skúsiť to znovu. V paralelnom vesmíre je všetko okrem kocúrov rovnaké. A keďže kocúr je naozaj prefíkaný, schová sa tam, kde by ste ho najmenej hľadali. Však zistíte.

Bližšie popisy ulíc

Agátová

Na tejto ulici býva jeden prefíkaný kocúr. Vo všetkých domoch vedia, či býva v dome s vyšším alebo nižším číslom, nikde však nevedia jeho presnú adresu (samozrejme okrem domu, kde býva).

Ak nájdete správneho kocúra do \(12\) návštev máte \(3\) body, ak do \(24\) návštev máte \(2\) body, ak do \(100\) návštev máte \(1\) bod.

Biela

Na tejto ulici sú kocúry zoradené podľa prefíkanosti. Najskôr prefíkanosť stúpa k stopercentnému a potom znova klesá. Pozor! Prefíkanosť nestúpa a neklesá rovnomerne, ale tak, aby vás čo najviac zmiatla. V každom dome vedia len prefíkanosť svojho kocúra (v percentách).

Ak nájdete správneho kocúra do \(20\) návštev máte \(3\) body, ak do \(40\) návštev máte \(2\) body, ak do \(100\) návštev máte \(1\) bod.

Cesnaková

Na tejto ulici nájdete aj kocúrov, ktorí sú prefíkaní viac ako stopercentne. Vašou úlohou však zostáva nájsť toho presne stopercentného.

Kedysi dávno tu platilo, že kocúry boli zoradené podľa prefíkanosti: od najmenej prefíkaného v dome \(1\) až po toho najprefíkanejšieho v dome \(1\,000\). Zistili však, že potom ľudia stopecentného kocúra ľahko nájdu (postupom podobným tomu z Agátovej ulice).

Všetky kocúry sa preto jedného dňa dohodli na čísle \(x\) (medzi \(1\) a \(1\,000\), vrátane). Následne sa odohralo nasledovné sťahovanie:

  • Kocúry z domov s číslami \(1\)\(x\) sa presťahovali do domov s číslami \((1\,001-x)\)\(1\,000\).
  • Každý iný kocúr sa presťahoval zo svojho domu do domu s číslom o \(x\) menším.

Teda napríklad ak \(x=2\), tak kocúr z domu \(1\) išiel do domu \(999\), kocúr z domu \(2\) išiel do domu \(1\,000\), a kocúry z domov \(3\)\(1\,000\) sa presťahovali do domov \(1\) až \(998\).

Samozrejme, \(x\) si už dnes nik nepamätá. V každom dome vám vedia povedať len prefíkanosť kocúra, ktorý tam v súčasnosti býva.

Ak nájdete správneho kocúra do \(15\) návštev máte \(3\) body, ak do \(30\) návštev máte \(2\) body, ak do \(100\) návštev máte \(1\) bod.

Odovzdávanie a bodovanie

Simuláciu Kocúrkova a prechodu do paralelných vesmírov nájdete na stránke https://prask.ksp.sk/specialne/prask/1/2/1/. Tu viete na každej ulici získať najviac \(3\) body.

Na to, aby ste získali zvyšné body (dva pre každú ulicu), je potrebné pre každú ulicu poslať slovný popis toho, ako ste túto úlohu riešili. Svoj postup skúste rozšíriť tak, aby fungoval aj na ulice s viac ako \(1\,000\) domami. Skúste odhadnúť, koľko návštev by ste potrebovali, ak by ste chceli nájsť prefíkaného kocúra na ulici s \(1\,000\,000\) domami.

Tento návod potom odovzdajte klasickým spôsobom cez stránku.

Agátová

Na prvej ulici žije iba jeden prefíkaný kocúr a našou úlohou je zistiť, v ktorom dome. Keď prídeme do nejakého domu, v ktorom nebýva kocúr, zakaždým sa dozvieme, či býva v dome s vyšším alebo nižším číslom.

Nebudeme teda otáľať a rovno sa programu spýtame, či prefíkaný kocúr nebýva náhodou v dome \(47\). Možno budeme mať šťastie a uhádneme to na prvý pokus. Neprekvapivo však na obrazovke zbadáme odpoveď .

Otázka je, čo vieme z tejto odpovede zistiť. Zjavne kocúr nebýva v dome \(47\). To však nie je všetko. Z odpovede, ktorú sme dostali vyplýva, že nemôže bývať ani v žiadnom dome s menším číslom. Teda musí bývať v niektorom dome s číslom od \(48\) po \(1000\). Pomocou jednej otázky sme teda neodstránili len jednu možnosť, ale rovno \(47\) možností. A ak by sme mali šťastie a zistili by sme, že kocúr býva v dome s číslom nižším ako \(47\), odstránili by sme až 954 možností, lebo by nemohol bývať v žiadnom dome s väčším číslom.

Ako teda vidíme, ak ako prvý navštívime dom \(x\), v ktorom kocúr nebýva, podľa odpovedi nám ubudne \(x\) alebo \(1001-x\) možností. Ktoré \(x\) sa teda chceme spýtať ako prvé? Ako naznačuje zadanie, na šťastie sa nemôžeme spoliehať, lebo kocúr sa schováva tam, kde by sme ho najmenej čakali. Čo v praxi znamená, že náš program vám odpovedá takým spôsobom, aby ste vždy vylúčili menej možností. Mohli by ste sa teda otázku \(47\) pýtať ako prvú koľkokrát chcete, odpoveď by bola stále tá istá, lebo je to menej výhodné.

To znamená, že ak sa spýtam na dom \(x\), odstránim \(\min(x,1\,001-x)\) možností, pretože takto odpovedá náš program. Boli by sme radi, keby toto číslo bolo čo najväčšie možné. A to nastane pre \(x=500\) (alebo tiež \(x=501\)), teda v polovici intervalu \(1\)\(1\,000\).

A čo ďalej? Stačí opakovať túto myšlienku. Po prvom opýtaní nám zostali už len domy s číslami \(501\)\(1\,000\). Keď sa opýtam na nejaký dom \(x_2\) v tomto intervale, z odpovede dokážem vylúčiť buď časť od \(501\) po \(x_2\), alebo tú od \(x_2\) po \(1\,000\). A opäť bude najlepšie sa spýtať na stred tohto intervalu, teda \(x_2=750\), lebo vtedy nám určite zostane najmenší počet zvyšných možností.

Môžeme si teda náš postup zovšeobecniť. Budeme si udržiavať dve čísla \(zac\) a \(kon\), ktoré budú udávať začiatok a koniec intervalu domov, v ktorých sa môže nachádzať kocúr. Na začiatku \(zac=1\) a \(kon=1\,000\). Následne sa v každom kole spýtam otázku \(x=\frac{zac+kon}{2}\), čo je vlastne číslo v polovici intervalu \(\langle zac,kon \rangle\). Ak je to číslo náhodou desatinné, zaokrúhlim ho nadol. Ak dostanem odpoveď, že kocúr býva v dome s vyšším číslom, upravím \(zac=x+1\), v opačnom prípade zmením \(kon=x-1\). Celý postup skončí, keď sa \(zac=kon\). V dome s číslom \(zac\) sa náš kocúr musí už určite nachádzať.

A tento postup bude fungovať pre ľubovoľne veľa domov (stačí správne nastaviť hodnotu \(kon\)). Princíp, ktorý sme použili sa volá binárne vyhľadávanie a v informatike je vcelku užitočný a používaný1. Dokonca sa často používa aj v reálnom živote, napríklad keď hľadáte konkrétnu stranu v knihe.

Otázkou však je, koľko otázok sa budem musieť spýtať. Uvedomme si, že v každom kroku zmenším počet možností na polovicu, pretože po opýtaní sa na čísla v strede intervalu nám jedna polovica odpadne. Teda počet otázok, ktoré musíme položiť vieme odhadnúť ako počet opakovaných delení čísla \(1\,000\) dvojkou, kým nám nezostane \(1\). Čo je v tomto prípade \(10\). A pre \(1\,000\,000\) bude počet potrebných otázok \(20\). Ako vidíme, tento počet rastie pomerne pomaly. Samozrejme, budeme potrebovať ešte tak 1 alebo 2 otázky naviac, lebo interval sa nie vždy rozdelí na presnú polovicu kvôli zaokrúhľovaniu, ale na to máme dostatočnú rezervu.

Biela

Na Bielej ulici je to trochu inak. Teraz sa v každom dome nachádza kocúr, každý je však inak prefíkaný. Naviac, najskôr prefíkanosť stúpa, až kým nedosiahne \(100\) a potom klesá. Otázka je, v ktorom dome býva kocúr s prefíkanosťou \(100\).

Aby sme sa už nemuseli rozprávať o kocúroch a prefíkanostiach, predstavme si ulicu ako postupnosť \(1\,000\) čísel, ktoré na začiatku rastú, až kým nedosiahnu hodnotu \(100\) a potom klesajú až do konca. Ak viete čo je to graf funkcie, mohli by ste si túto postupnosť predstaviť ako graf funkcie, ktorý vyzerá ako kopec s jedným vrcholom. No a hľadáme práve pozíciu tohoto vrchola – pozíciu maxima.

Poučený z predchádzajúcej podúlohy sa spýtame otázku na \(500\)-té číslo. Dostaneme odpoveď napríklad \(80\). Čo sme sa však dozvedeli o pozícii najväčšieho čísla (100)? Bohužiaľ nič. Hľadaná stovka sa môže stále nachádzať napravo aj naľavo od pozície \(500\). Z jedného čísla totiž nevieme zistiť, či naša postupnosť ešte stúpa a \(100\) sa nachádza až niekde ďalej, alebo už naša postupnosť klesá a \(100\) sa nachádza niekde predtým.

Potrebovali by sme teda zistiť, či naša postupnosť v bode \(500\) rastie alebo klesá. Z jedného čísla to nevieme, ale čo tak z dvoch po sebe idúcich? Spýtame sa preto na \(501\)-vú pozíciu. Ak dostaneme číslo väčšie ako \(80\), vieme že postupnosť ešte len stúpa a maximum sa nachádza v druhej polovici postupnosti. Ak dostaneme číslo menšie, tak postupnosť klesá a maximum je v prvej polovici. V každom prípade, pomocou dvoch otázok sme schopný určiť, v ktorej polovici postupnoti sa nachádza číslo \(100\). A tento postup môžeme opakovať.

Tak ako predtým, budeme mať dve premenné \(zac\) a \(kon\), ktoré budú určovať interval \(\langle zac,kon\rangle\), v ktorom sa môže nachádzať číslo \(100\). Na začiatku \(zac=1\) a \(kon=1\,000\). V každom kole sa spýtame dve otázky \(x=\frac{zac+kon}{2}\) a \(y=\frac{zac+kon+1}{2}\) (opäť zaokrúhľujem nadol). Ak platí, že odpoveď na otázku \(y\) je väčšia ako odpoveď na otázku \(x\), tak to znamená, že postupnosť na pozícii \(x\) rastie, maximum sa nachádza v druhej časti, preto nastavím \(zac=y+1\). V opačnom prípade je opoveď na \(y\) menšia ako odpoveď na \(x\), tak na pozícii \(x\) postupnosť klesá, preto nám na vyskúšanie zostáva len prvá časť a teda nastavíme \(kon=x-1\).

Tak ako v predchádzajúcom prípade aj teraz sa v každom “kole” zbavíme polovice možností. V tomto prípade nás to však bude stáť dve otázky. Preto očakávame približne \(20\) otázok potrebných na nájdenie odpovede. V prípade ulice s \(1\,000\,000\) domami by to teda bolo zhruba \(40\) otázok.

Cesnaková

Táto ulica bola na riešenie asi najťažšia. Hlavne preto, že sa ťažko kontrolovalo, či ju riešite optimálnym spôsobom čo vyústilo v to, že sa vám mohlo podariť ju vyriešiť na \(3\) body aj pomocou neoptimálnej stratégie. V popisoch som si však na to dal pozor a nenechal som sa oklamať neúplnými riešeniami.

Ako teda vyzerá naše zadanie. Na začiatku sme mali postupnosť čísel, ktorá bola celú dobu rastúca. Potom sme však zobrali prvých \(x\) najmenších prvkov a v tom istom poradí sme ich presunuli na jej koniec. Označme si hodnotu prvého prvku výslednej postupnosti \(a\) a hodnotu posledného prvku ako \(b\). Naša postupnosť teraz vyzerá tak, že niekoľko prvkov rastie začínajúc hodnotou \(a\) (presnejšie po prvok na \(1001-x\)-tom mieste, ale my \(x\) nepoznáme, takže nám tento fakt nijak nepomôže), potom nastane prudký pád, kde nasledovný prvok je menší ako predchádzajúci a potom opäť prvky stúpajú až po hodnotu \(b\). Navyše vieme, že platí \(b<a\) (rozmyslite si prečo) a preto všetky prvky v prvej časti sú väčšie ako \(b\) a všetky prvky v druhej časti sú menšie ako \(a\).

Nebudeme otáľať a spýtame sa na \(500\)-tý prvok. Dostaneme odpoveď napríklad \(80\). Čo sme sa dozvedeli o pozícii čísla \(100\)? Opäť nič. Môže sa nachádzať aj napravo od pozície \(500\), ak zlom ešte nenastal alebo sme zlom minuli a nachádza sa niekde naľavo. A nepomôže nám, ani keď sa spýtame na susedné prvky. Totiž okrem jednej dvojice platí, že nasledujúci prvok je väčší. A môžete sa staviť, že tú zaujímavú dvojicu vám náš program neukáže.

Potrebujeme sa teda spýtať takú otázku, ktorá by nám prezradila, či sa maximum nachádza naľavo alebo napravo od pozície \(500\). Alebo, inak formulované, chceli by sme zistiť, na ktorej strane sa nachádza náš zlom. Uvedomme si, že ak by sme mali číslo \(a\) (teda hodnotu prvého prvku postupnosti), vieme to zistiť naozaj jednoducho. Ak je naše zistené číslo (v našom prípade \(80\)) menšie ako \(a\), znamená to, že sa nachádza za zlomom. Ak je väčšie, tak zlom ešte nenastal. No a hodnotu \(a\) zistíme otázkou na pozíciu \(1\).

Náš algoritmus bude teda fungovať nasledovne. Na začiatku položíme jednu otázku na pozíciu \(1\) a odpoveď si zapamätáme do premennej \(a\). Tak ako pred tým, aj teraz budeme mať dve premenné \(zac\) a \(kon\), ktoré budú udávať začiatok a koniec možného intervalu. V každom kole sa spýtame otázku \(x=\frac{zac+kon}{2}\) a dostaneme odpoveď \(y\). Ďalší krok bude mierne zložitejší.

Vyzerá to trochu komplikovane, ale keď sa nad tým trochu zamyslíte a nakreslíte si obrázok, zistíte, že je to veľmi priamočiare.

Ostáva nám už len odhadnúť potrebný počet otázok. Na začiatku položíme jednu otázku, aby sme zistili hodnotu \(a\), ale potom to už funguje ako klasické binárne vyhľadávanie, pýtame sa do stredu intervalu a zakaždým sa rozhodneme, ktorú polovicu už nepotrebujeme. Budeme teda potrebovať zhruba \(11\) otázok, pre postupnosť dlhú \(1\,000\,000\) zhruba \(21\).

Na záver

V tejto úlohe sme si predstavili jeden veľmi zaujímavý algoritmus – binárne vyhľadávanie. Je to veľmi užitočný nástroj, ktorý častokrát aplikujeme aj v skutočnom živote, nehovoriac už o informatike. Jeho hlavnou výhodou je malé množstvo otázok, ktoré sme sa potrebovali spýtať. Ak máme \(1\,000\,000\) prvkov, v ktorých sa snažíme nájsť jeden konkrétny, nemusíme položiť milión otázok, stačí nám ich zhruba \(20\). Má to však komplikáciu, ak niečo takéto chceme použiť, prvky musia byť zoradené od najmenšieho po najväčší.

V našich úlohách síce tomu nebolo vždy tak, ale ak si všimnete, vo všetkých boli prvky zoradené pomerne pekným, jednoduchým a takmer usporiadaným spôsobom. Je dobré si zapamätať túto dôležitú podmienku a pred použitím binárneho vyhľadávania si rozmyslieť, či je splnená.


  1. Aj na miestach, kde by ste ho naozaj nečakali.

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ť.

  • Ján Zubo

    26. november 2017 8:44

    jzs