Problem E
Prinsessen på ærten

En enkelt ært har forputtet sig i et af hoffets $M$ madrasser, og det er din opgave at finde den inden for $N$ nætter. Heldigvis vil den godhjertede prinsesse godt hjælpe dig. Efter en nats søvn på en stak af madrasser kan hun med sikkerhed afgøre, om hun lå oven på ærten eller ej. Desværre er hun en rigtig prinsesse, så hun bliver ganske brun og blå over hele kroppen, når hun har ligget på ærten. I så fald behøver hun $S$ nætters søvn i sine egne gemakkers luksuøse og garanteret bælgfrugtsfrie seng, inden hun står til rådighed igen. Du kan bruge dagtimerne til at flytte rundt på stakken af madrasser.

Interaktion

Først indlæses en linje med heltallene $M$, $N$ og $S$, adskilte af mellemrum.

Derefter foregår interaktionen i runder. I hver runde kan du enten fortage en måling eller annoncere svaret.

1. For at foretage en måling skriver du et spørgsmålstegn efterfulgt at numrene på de madrasser, som du gerne vil have undersøgt. For eksempel skriver du »? 17 3 4 10« for at bede prinsessen om at overnatte på madrasserne $3$, $4$, $10$ og $17$. (Læg mærke til, at rækkefølgen er uvæsentlig. Hun er jo en rigtig prinsesse.) Generelt skriver du en linje på formen »? $m_1$ $\cdots $ $m_ r$«, hvor $m_1$, $\ldots $, $m_ r$ er forskellige heltal adskilte af mellemrum, med $0<r\leq M$ og $0\leq m_ i < M$ for $1\leq i \leq r$. Det svarer til at bede prinsessen om at overnatte på de $r$ angivne madrasser. Den derpå følgende morgen rapporterer hun, om hun sov på en ært (indlæsningen er »1« og hun bliver brun og blå) eller ej (indlæsningen er »0« og hun er stadig veltilpas). Dette koster 1 nat. Hvis prinsessen er brun og blå, skal hun have yderligere $S$ nætters hvile, inden hun kan hjælpe dig igen.

2. For at annoncere svaret skriver du et udråbstegn efterfulgt af et madrasnummer, adskilte af mellemrum. For eksempel skriver du »! 3« for at annoncere for hele hoffet ved morgenmaden, at »ærten ligger i madras 3«. Generelt skriver du en linje på formen »! $m$«, hvor $0\leq m< M$, for at annoncere, at ærten befinder sig i den $m$te madras. Dette afslutter interaktionen. Hvis ærten virkelig befinder sig i den $m$te madras, bliver dit program accepteret, ellers bliver det afvist med bedømmelsen forkert svar.

Hvis antallet af nætter overstiger $N$, bliver dit program afvist med bedømmelsen forkert svar.

Madrasserne er nummereret fra $0$ til $M - 1$. Der er præcis én ært. I begyndelsen er prinsessen veltilpas.

Pointsætning

Der er seks testgrupper. Der gælder altid $1\leq M \leq 1000$, $0\leq N\leq 1000$ og $0\leq S\leq 1000$. Desuden opfylder $N$, $M$ og $S$, at en optimal metode kan finde ærten inden for $N$ nætter.

Skylning af udskriftsbufferen

Interaktive problemer bliver kørt mod et dommerprogram. Udskriften fra dit program kan muligvis blive hængende for længe i en såkaldt udskriftsbuffer, hvilket fører til bedømmelsen uden for tidsgrænsen. For at forhindre dette bør du sørge for at udtrykkeligt tømme udskriftsbufferen ved hver udskrift. Dette kaldes populært at skylle eller spule bufferen.

I Python3:

print(x, flush=True)

I Java:

System.out.println(x);
System.out.flush();

I C++:

std::cout << x << "\n" << std::flush;

Forklaring af eksempler

Interaktionen begynder med, at du indlæser tallene $M=3$, $N=3$ og $S=1$. Der er altså $3$ madrasser, og du har $3$ nætter til at finde ud af, i hvilken madras ærten gemmer sig. Hvis prinsessen sover på ærten, skal hun bruge $1$ nats søvn yderligere, før hun er klar til at hjælpe dig igen. Den første dag arrangerer du madrasserne, så prinsessen kommer til at sove på madras $0$ og $1$.

I det første eksempel er ærten i madras $0$. Efter den første nat fortæller prinsessen dig derfor »$1$«, dvs. at hun har sovet på ærten og er blevet brun og blå. Derfor kan hun ikke hjælpe dig igen før den tredje nat. (Hun tilbringer den anden nat i sine egne gemakker for at komme sig.) Den tredje nat får du prinsessen til at sove på madras $0$. Prinsessen svarer igen »$1$« (hun har sovet på ærten), bliver brun og blå, og ville ikke hjælpe dig igen før den femte nat. Så lang tid kan du dog ikke vente, da du har opbrugt de $3$ nætter, du har til rådighed. Heldigvis kan vi af prinsessens svar udlede, at ærten må være i madras $0$.

I det andet eksempel er ærten i madras $2$. Efter første nat (hvor du bad hende om at sove på madrasserne $0$ og $1$) har prinsessen det fint og svarer »$0$«. Du kan straks udlede, at ærten må befinde sig i madras $2$, og annoncerer dette stolt allerede på andendagen.

3 3 1

? 0 1

1

? 0

1

! 0

3 3 1

? 0 1

0

! 2