Táto úloha je programátorská. Ako svoje riešenie odovzdaj program vo svojom obľúbenom jazyku a automaticky sa dozvieš, koľko si dostal/a bodov. Ak si takýto typ úloh ešte nikdy neriešil/a, skús sa pozrieť ako by mal vyzerať ideálny program. Ak zatiaľ programovať nevieš, ale chcel/a by si sa naučiť, môžeš skúsiť našu KSP School.
Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Miške na [email protected]
V dedine bolo našej výprave dobre ale už sú tu pár mesiacov a možno by sa aj patrilo ísť konečne domov. Lenže kde je to ten domov? Ako sa tak pozerá Štepi s Miškou na tú hustú džunglu, tak ani na tom, že kde je vlastne sever sa nevedia dohodnúť. Tu je mach, tam je mach, vlastne všade je ten hlúpy mach a bez nejakej tej mapy to asi nepôjde. Palindromatický jazyk domorodcov už ovládajú plynulo a po chvíľke vypytovania, že kde by našli mapapam je Štepi nasmerovaní k rozpadávajúcej sa chatrči, kde prebýva miestny mystický šaman Strížožírts. V celej chatke vládne bordel. A uprostred toho bordelu, usadený na obrovskej čiernej skrinke, je uškŕňajúci sa Strížožírts, ktorý sa rovno púšta do vysvetľovania:
“Podo mnou je štvorcová skrinka s dĺžkou strany $N$, v nej sa nachádzajú mapy, ktoré chcete. Každá mapa je štvorec s dĺžkou strany $M$. Pokiaľ správne uhádnete dĺžku $M$, mapy vám darujem. Aby som vám troška pomohol, pred tým než si finálne tipnete, môžete sa ma pýtať, či sa $K$ zmestí alebo nezmestí do $M$. Keď si myslíte, že viete správnu odpoveď poviete mi ju, ale pozor! Po nejakej chvíli ma prestane baviť odpovedať vám na otázky.”
Z toho ako sa Strížožírts posmešne pozerá na ustráchaného Štepiho je zjavné, že ani jeden si nemyslí, že to Štepi zvládne. Chcete Štepimu rýchlo a efektívne pomôcť, kým to šamana ešte baví.
Komunikujete so šamanom (počítačovým programom) a posielate mu jeden z dvoch typov výstupu:
? K je otázka, na ktorú vám šaman odpovedá
ANO, ak platí že $K <= M$NIE, ak platí že $K > M$= K je finálna odpoveď, ktorou sa ukončí program
Je zaručené, že $1 \leq M \leq N$.
Na prvom riadku vstupu dostanete hodnotu $N$, ďalšie riadky sú odpovede na vaše otázky - ANO alebo NIE.
Exituje 5 sád vstupov, každá za 20 bodov. V jednotlivých sadách platia obmedzenia:
| Sada | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| $1 \leq N \leq$ | $100$ | $1\,000$ | $100\,000$ | $10^7$ | $10^9$ |
Na výstup vypíš riadok s otázkou, na ktorú chceš odpoveď, alebo tvoj finálny tip.
Aby testovanie fungovalo ako má, je nutné po vypísaní každého riadku flushnúť výstup, aby ho testovač uvidel. V C++ by malo stačiť cout << nieco << endl;, ale môžete explicitne použiť príkaz cout.flush();. V Pythone vypisujte príkazom print(cislo, flush=True) alebo po vypísaní zavoljate sys.stdout.flush(). Pre iné jazyky hľadajte ekvivalent k príkazu flush.
>>> 1000
<<< ? 200
>>> ANO
<<< ? 201
>>> ANO
<<< ? 900
>>> NIE
<<< = 742
(>>> znamená, že ide o vstup tvojho programu, <<< zas, že ide o jeho výstup. Tieto značky sú len ilustračné, na testovači sa nevyskytujú.)
Najprv dostaneme ako vstup maximálnu hodnotu $N$. Potom sa trikrát pýtame a dostávame odpoveďe od šamana. Prvé dve čísla sú menšie alebo rovné $M$. Tretie je väčšie ako M. Na konci je číslo, ktoré si myslíme že je odpoveď (nie je to nutne správna odpoveď).
Možné veľkosti mapy si predstavme ako postupnosť čísiel, ktorá začína jednotkou a končí $N$-kom. Ak by sme sa na čísla pýtali postupne tak až po číslo $M$ (číslo $M$ je riešenie úlohy) by sme dostávali odpoveď ANO, lebo všetky čísla sú určite menšie alebo rovné $M$. Ak by sme sa pýtali dalej, tak na všetky dalšie čísla by sme dostávali odpoveď NIE, lebo všetky ďalšie čísla sú určite väčšie ako $M$. Najprimitívnejšie riešenie prechádza cez všetky čísla postupne a hľadá zlom medzi odpoveďou ANO a NIE. Časová zložitosť tohto riešenia je $O(n)$. Stačí aby si pamätal iba číslo na ktorom bol naposledy, a to znamená, že pamäťová zložitosť je $O(1)$.
Riešenie hore je hlúpe. Čo ak je náš hľadaný rozmer niekde na konci postupnosti? Kým by sme ho našli, prešli by sme cez všetky ostatné rozmery. Pravdepodobne teda budeme chcieť niektoré čísla preskakovať a budeme to chcieť robiť na základe odpovedí, ktoré dostávame. Môžete sa nad tým zamyslieť pre tým než si prečítate vzorové riešenie.
Možno ste si všimli, že odpovede, ktoré dostávame hovoria niečo o tom, kde sa nachádza správne riešenie. Pokiaľ sme dostali odpoveď ANO, správne riešenie sa nachádza na číselnej osi vpravo, pokiaľ sme dostali odpoveď NIE, správne riešenie sa nachádza vĺavo. Formálnejší dôkaz je, že ak platí že K <= M, tak platí K - x < M ($K$ je číslo, na ktoré sa pýtame a $x$ je ľubovoľné kladné číslo), z toho teraz vieme odvodiť, že pre správne riešenie, označme ho S, platí že K <= S = M.
Túto informáciu vieme teraz šikovne využiť. Na začiatku vieme, že riešenie sa určite nachádza na intervale $1 \dots N$. Vypočítame si stred intervalu ($c$) a opýtame sa na neho. Pokiaľ je odpoveď ANO, tak vieme, že v prvej polovici riešenie určite nie je a interval môžem nastaviť na $c \dots N$. Pokiaľ je odpoveď NIE, tak viem, že riešenie naopak je v prvej polovici a interval nastavím na $1 \dots c$. Jednou operáciou sme vyhodili polovicu čísiel a dostali nový interval, v ktorom vieme, že sa nachádza riešenie. Toto vieme zopakovať, vezmeme nový interval, vypočítam stred a opýtame sa na neho. Podla toho čo nám odpovie program nastavíme stred na ľavý alebo pravý okraj. Program skončí keď interval pokrýva iba jedno číslo, inak povedané, lavý a pravý okraj intervalu sa rovnajú. Tento algoritmus sa volá binárne vyhľadávanie. Keďže s každým opýtaním vyradím polovicu z ostávajúcich čísel program bude mať logaritmickú časovú zložitosť $O(log n)$. Takže ak je N napríklad $10^6$ tak $log(10^6)$ bude približne $20$ a to je násobne lepšie ako prechádzanie všetkých $10^6$ čísel. Pamäťová zložitosť ostáva $O(1)$ len si namiesto jedného čísla pamätáme tri, ľavý okraj, pravý okraj a stred intervalu.