5. Taktická záchrana

Kde bolo tam bolo, v \(n\) posteliach si nažívajú mnohofarebné ploštice. Ich spokojnú existenciu však narušil príchod Klubu: Stop Plošticiam. A zrejme už detekovali prítomnosť ploštíc a idú ich posteľ-po-posteli vyhubiť! Centrálny Mozog Ploštíc¹ už pripravuje evakuáciu – obetuje ploštice v prvej vyhadzovanej posteli a evakuuje medzitým ostatné (kým je Klub zamestatný deratizáciou tej postele). Problém je, Centrálny Mozog Ploštíc nevie ktorá posteľ bude deratizovaná ako prvá, a preto by sa rád pripravil na všetky možnosti. Menovite, chcel by vedieť, pre každú posteľ, aké farby ploštíc sa zachránia. Ďalší problém je, že Centrálny Mozog Ploštíc neviem aké farby ploštíc žijú na akej posteli. Jediné, čo vie robiť, je sa pozrieť na nejakú množinu postelí, a zistiť aké farby ploštíc sú prítomné na nejakej z nich. Pozor! Deratizéry sa blížia, a Centrálny Mozog nemá veľa času pýtať sa!

Úloha

Táto úloha je interaktívna. Namiesto klasického vstupy a výstupu sa váš program bude pýtať otázky a dostávať na ne odpovede.

Existuje \(63\) farieb ploštíc, a \(n\) postelí kde sa ploštice nachádzajú. Farby ploštíc na \(i\)-tej posteli si vieme reprezentovať celým číslom \(p_i\) – prítomnosť ploštíc \(j\)-tej farby je indikovaná tým, či \(j\)-tý bit v binárnej reprezentácii čísla \(p_i\) je \(1\) (ak je \(0\), ploštice danej farby sa tam nenachádzajú).

V tejto úlohe váš program pomáha Centrálnemu Mozgu Ploštíc. Vašou úlohou je zistiť, pre každú z postelí, aké farby ploštíc sa nachádzajú na ostatných posteliach. Konkrétne to chcete zistiť pomocou pýtania sa niekoľko (čo najmenej) otázok typu “aké farby ploštíc sú v tejto množine postelí”.

Formát vstupu

Na prvom riadku vstupu je číslo \(t \leq 100\) udávajúce počet sád.

Pre každú zo sád dostanete na novom riadku číslo \(1 \leq n\leq 1000\) – počet postelí.

Na každú vašu otázku dostanete odpoveď – celé číslo ktorého binárny zápis reprezentuje prítomnosti farieb, na novom riadku.

Po každej vašej odpovedi na danú sadu, nasleduje nová sada.

Formát výstupu

Otázky sa vás program pýta v nasledujúcom formáte: pre jednu otázku, na jednom riadku vypíšte ? (otáznik), nasledovaný medzerou a celým číslom \(0\leq m\leq n\), veľkosť množiny na ktorú sa chcete opýtať. Potom nasleduje \(m\) medzerou oddelených čísel \(1\leq i_1, \dots, i_m \leq n\) – čísla postelí v množine na ktorú sa pýtate.

Pre vypísanie výsledku pre aktuálnu sadu, vypíšte jediný riadok, začínajúci ! (výkričníkom) nasledovaný \(n\) číslami oddelenými medzerou – \(i\)-té z nich reprezentuje aké farby ploštíc sa nachádzajú na všetkých posteliach okrem \(i\)-tej.

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.

Testovač je adaptívny a teda rozloženie ploštíc na posteliach môže závisieť od otázok vášho programu. Je garantované, že všetky odpovede sú konzistentné s nejakým rozložením ploštíc po posteliach.

Varovanie

V prípade, že váš program vypíše výstup v zlom formáte, testovanie skončí s nula bodmi. V tomto prípade váš program vie dostať verdikt “Prekročeny časový limit”.

Hodnotenie

Hodnotenie v tejto úlohe bude špeciálne a bude záležať na počte otázok, ktoré ste sa opýtali. Existuje jediný vstup, na ktorom bude váš program testovaný. Body dostanete, len ak na všetky testovacie sady odpoviete správne.

• Plný počet dostaanete, ak váš program na každú sadu odpovie správne s použitím nanajvýš \(13\) otázok

• \(6\) bodov vie váš program získať ak na každú sadu odpovie správne s použitím nanajvýš \(2\lceil \log n \rceil\) otázok (kde \(n\) je počet postelí v tej sade)

• \(4\) body dostane váš program ak na každú sadu odpovie správne s použitím nanajvýš \(2\lceil \sqrt n \rceil\) otázok

• Nanajvýš \(2\) body dostanete, ak na každú sadu odpovie váš program správne s použitím nanajvýš \(n / 2 + 2\) otázok

• Najviac \(1\) bod vie získať riešenie, ktoré nikdy nepoužije viac otázok ako je postelí.

Príklady

>>> 1
>>> 3
<<< ? 1 1
>>> 1
<<< ? 1 2
>>> 2
<<< ? 1 3
>>> 4
<<< ! 6 5 3

Pre jednoduchosť je vstup aj výstup spolu. “>>>” a “<<<” sú v príklade len na prehľadnosť. V tomto prípade na \(i\)-tej posteli žijú práve ploštice \(i\)-tej farby, takže ak si Klub vyberie prvú posteľ, zachránia sa ploštice farieb \(2\) a \(3\), ak si Klub vyberie druhú posteľ zachránia sa ploštice farieb \(1\) a \(3\), a ak si vyberú tretiu posteľ, zachránia sa ploštice farieb \(1\) a \(2\).