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

Úloha

Komunikujete so šamanom (počítačovým programom) a posielate mu jeden z dvoch typov výstupu:

1. ? K je otázka, na ktorú vám šaman odpovedá

   1. ANO, ak platí že $K <= M$
   2. NIE, ak platí že $K > M$

2. = K je finálna odpoveď, ktorou sa ukončí program

Je zaručené, že $1 \leq M \leq N$.

Formát vstupu

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:

Formát výstupu

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.

Príklad vstupu

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