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ď).