Þetta verkefni er gagnvirkt. Eftir að hver lína er prentuð út þarftu að tæma úttaksbiðminnið (flush). Þú getur notað cout << flush í C++, System.out.flush() í Java og sys.stdout.flush() í Python. Þú verður að fylgja leiðbeiningunum í kaflanum Samskipti í hvívetna; annars gætirðu fengið niðurstöður eins og rangt svar (wrong answer), tímatakmarki náð (time limit exceeded) eða annað.

Þar sem öll verkefnin hafa goðsagnakennda dverga sem aðalpersónur gæti loksins verið þess virði að hugsa um eitthvað áþreifanlegt.

Til er falin runa $A$ af lengd $N$ sem samanstendur af heiltölum á bilinu $[0, 2^N - 1]$. Verkefni þitt er að endurheimta hana með takmörkuðum fjölda fyrirspurna. Í hverri fyrirspurn gefur þú upp runu $B$ af lengd $N$ með stökum á bilinu $[0, 2^N - 1]$. Svarið er reiknað á eftirfarandi hátt:

• Runan $C$ er búin til þar sem $i$-ta stakið í $C$ er bitbundið xor (bitwise xor) af $i$-tu stökunum í $A$ og $B$. Við táknum xor með $\oplus$.
• Mengið $S$ er smíðað sem mengi allra gilda sem hægt er að fá með því að taka xor af einhverju hlutmengi staka úr $C$. Sér í lagi er xor fyrir tóma hlutmengið jafnt og $0$.
• Svarið við fyrirspurninni er $|S|$.

Til dæmis, ef $A = (1, 4, 3)$ og $B = (0, 4, 7)$, þá er $C = (1 \oplus 0, 4 \oplus 4, 3 \oplus 7) = (1, 0, 4)$ og $S = \{0, 1, 4, 5\}$, svo svarið er $4$.

Bitbundið xor tveggja talna $x$ og $y$ hefur bita $i$ settan ef og aðeins ef nákvæmlega önnur talnanna $x$ og $y$ hefur bita $i$ settan. Til dæmis er $5 \oplus 3 = (101)_2 \oplus (011)_2 = (110)_2 = 6$. Í C++ og Python er xor virkinn ^.

Samskipti

Runan $A$ er ákveðin í upphafi og ræðst ekki af fyrirspurnunum sem gerðar eru.

Lestu fyrst línu sem inniheldur eina heiltölu $1 \le N \le 60$. Síðan getur þú spurt fyrirspurna.

Til að spyrja fyrirspurnar skaltu prenta línu sem inniheldur ? ásamt $N$ heiltölum á bilinu $[0, 2^N - 1]$. Sem svar lestu eina heiltölu sem er svarið.

Þegar þú ert tilbúinn skaltu prenta ! ásamt heiltölunum $N$ í földu rununni. Síðan á forritið þitt að hætta keyrslu án frekara úttaks.

Mundu að tæma úttaksbiðminnið (flush) eftir hverja fyrirspurn og eftir að svarið er skrifað. Settu bil á milli talna og táknanna ?, !.

Dæmi

Inntak 1

3
4
8

Úttak 1

? 1 2 3
? 0 0 0
! 1 3 4

Athugasemd

Skýringin á dæmasamskiptunum: $N = 3$ Fyrirspurn ? 1 2 3: $B = (1, 2, 3)$, $C = (1 \oplus 1, 3 \oplus 2, 4 \oplus 3) = (0, 1, 7)$, $S = \{0, 1, 6, 7\}$, svarið er $4$. Fyrirspurn ? 0 0 0: $B = (0, 0, 0)$, $C = (1 \oplus 0, 3 \oplus 0, 4 \oplus 0) = (1, 3, 4)$, $S = \{0, 1, \dots, 7\}$, svarið er $8$. Úttak ! 1 3 4: Falda runan er $A = (1, 3, 4)$.

Staðbundin prófun

Í hlutanum Files finnurðu B.zip sem inniheldur dæmapróf og prófara grader.cpp. Til að prófa lausnina þína skaltu þýða hana og senda síðan nafn prófsins og keyrsluskrána þína í þýdda ./grader forritið:

./grader [test] [executable]

Til dæmis: ./grader 0b.in ./abc

Ekki er tryggt að dæmaprófarinn hegði sér nákvæmlega eins og sá opinberi. Hvorugur þeirra er þó aðlögunarhæfur (adaptive).