4. O žabách a hadoch

Žabiak Michal a žabka Lucka dostali na Vianoce hru Hady a Žaby. Táto hra je pre dvoch hráčov. Jeden hráč si zvolí postupnosť štyroch farebných žiab zo šiestich možných farieb. Farby žiab sa môžu aj opakovať. Druhý hráč háda, aká je táto postupnosť. Aby to však nemal až také ťažké, po každom tipe mu prvý hráč povie dve čísla. Prvé hovorí, koľko žiab trafil presne, teda na danom mieste je žaba správnej farby. Druhé hovorí koľko žiab mu zjedli hady (teda sú na zlom mieste). Inak povedané, toto číslo hovorí o koľko viac žiab mohol trafiť, ak by svoj tip usporiadal inak. Žabiakovi Mišovi sa táto hra veľmi zapáčila, no žabku Lucku už pomaly aj prestala baviť. Žabiak si oblúbil úlohu prvého hráča, ktorý to má síce celkom jednoduché, ale za to sa môže protihráčovi smiať vždy, keď neuhádne.

Žabiak si teda naprogramoval svojho druhého hráča, s ktorým sa môže hrať, koľko len bude chcieť. Tento jeho protihráč bol však veľmi hlúpy a hádal náhodné postupnosti. Začalo to byť rýchlo nudné. Dokážete žabiakovi naprogramovať lepšieho protihráča?

Úloha

Táto úloha je interaktívna. Váš program musí vypísať svoj tip, potom si prečítať odpoveď od žabiaka a vypísať ďalší tip, a tak ďalej, až kým nebude odpoveď 4 0. Táto odpoveď znamená, že tip je správny, teda že váš program trafil všetky štyri žaby.

Formát vstupu

Po každom tipe dostanete na vstup dve medzerou oddelené čísla – počet žiab a počet hadov.

Aby testovanie fungovalo ako má, je nutné, aby sa po vypísaní tipu výstup presunul z pamäte na štandardný výstup pomocou príkazu cout.flush() v C++ alebo sys.stdout.flush() v Pythone. Pre iné jazyky hľadajte ekvivalent k príkazu flush.

Formát výstupu

Každý tip vypíšte ako \(4\) medzerou odelené čísla od \(1\) do \(6\), ktoré predstavujú farby štyroch žiab.

Hodnotenie

Je \(10\) sád vstupov. Každá sada má obmedzený počet tipov, ktoré sa môžete opýtať. Ak budete potrebovať viac tipov na zistenie riešenia, dostanete odpoveď WA. Maximálny počet otázok je v prvých sadách postupne \(1000, 100, 50, 30\) a \(10\). V ďalších sadách je počet vždy o jedno menší až po \(5\) v poslednej sade.

V popise riešenia sa sústreďte na to, aby bolo jasné prečo vaše riešenie vždy nájde odpoveď. Časovú zložitosť určite v závislosti od počtu farieb a od počtu hádaných žiab.

Príklad

>>> 1 3 2 3
<<< 1 2
>>> 3 4 2 1
<<< 0 4
>>> 1 2 3 4
<<< 4 0

Heslo je 1 2 3 4.