Problem P
Surströmming

Valborg har svenske aner og er meget glad for surströmming, en slags fermenteret sild. Den glæde deler Rued bestemt ikke; han kan ikke udstå lugten.

En dag, da Valborg havde efterladt en åben dåse surströmming, tog Rued det voldsomme skridt at grave resterne ned i et dybt hul et sted på gården. Alt var godt i nogen tid, men nu kan Rueds følsomme næse igen begynde at ane stanken fra den nedgravede dåse. Der er ikke andet for end at grave den op igen og for at sende den tilbage til Sverige.

Desværre har Rued glemt, hvor på gården han har nedgravet dåsen, og hans næse er ikke god nok til at finde frem til stedet. Heldigvis kan jordprøver afsløre koncentrationen af de fæle gasarter og dermed afstanden til kilden. Jordprøver tager dog tid og er lidt dyre, så Rued vil helst gennemføre så få som muligt. Han vil skrive et program, der kan styre måleprocessen bedst muligt og bestemme koordinater og dybde af den nedgravede dåse.

Interaktion

Først indlæses en linje med heltallet $N$, som er antallet af målinger, som Rued vil bruge på opgaven. Interaktionen foregår herefter i runder. I hver runde kan programmet enten foretage en måling eller annoncere svaret.

1. For at foretage en måling skal programmet skrive et spørgsmålstegn efterfulgt at overfladekoordinaterne for jordprøven. For eksempel skrives »? 42 17« for at tage en jordprøve på koordinat $(42, 17)$. Naboerne hjælper gerne, så det er også tilladt at måle lidt uden for gården. Generelt skriver du en linje på formen »? $x$ $y$«, hvor $(x,y)$ er to heltal adskilte af mellemrum, med $x,y\in \{ -1000,\ldots , 1000\} $. Derefter kan programmet læse afstanden til dåsen, kvadreret, som et heltal. For at være helt præcis, så er den heltallige kvadrerede afstand $a$ i meter givet ved formlen

   \[ a = {(x-x_\mathrm d)}^2+{(y-y_\mathrm d)}^2+z_\mathrm d^2\, , \]

   hvor $(x,y)$ er koordinaterne for målepunktet på overfladen, og $(x_\mathrm d,y_\mathrm d,z_\mathrm d)$ er koordinaterne for dåsen.

2. For at annoncere svaret skrives et udråbstegn efterfulgt af 3d-koordinaterne, hvor dåsen er begravet. For eksempel skrives »! 32 64 6« for at annoncere, at dåsen er $6$ meter under overfladekoordinaterne $(32, 64)$. Generelt skriver du en linje på formen »! $x$ $y$ $z$«, hvor $x,y,z \in \{ 0,\ldots , 99\} $ for at annoncere, at dåsen er $z$ meter under overfladekoordinaterne $(x,y)$. Dette afslutter interaktionen. Hvis dåsen virkelig befinder sig på koordinat $(x,y,z)$, bliver dit program accepteret, ellers bliver det afvist med bedømmelsen forkert svar.

Hvis antallet af målinger overstiger $N$, bliver programmet afvist med bedømmelsen forkert svar. Der er præcis én begravet dåse, placeret på et koordinat $(x_\mathrm d,y_\mathrm d,z_\mathrm d)$ med $x_\mathrm d,y_\mathrm d,z_\mathrm d \in \{ 0,\ldots ,99\} $.

Testgrupper

Der er fire testgrupper. Der gælder altid $0\leq x_\mathrm d < 100$, $0\leq y_\mathrm d < 100$ og $0\leq z_\mathrm d < 100$.

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

I det første eksempel er dåsen gemt på koordinat $(42, 42, 0)$, og Rued vil bruge op til $10\, 000$ jordprøver på at finde dåsen. Hans første måling er ved $(40,40)$, som er $(2,2,0)$ forskelligt fra dåsens koordinater. Summen af kvadraterne er $2^2+2^2=8$, hvilket han læser som svar på målingen. Dernæst måler han ved $(42,42)$, og får at vide at den kvadrerede afstand er $0$. Der er kun ét punkt, der er i afstand $0$ fra målepunktet, så han kan svare $(42,42,0)$.

I det andet eksempel er dåsen gravet ned på koordinat $(0,17,3)$, og igen med en grænse på $10\, 000$ målinger. De første fire målinger, på koordinaterne $(1,17)$, $(2,18)$, $(2,16)$, og $(3,17)$, har alle en kvadreret afstand på $10$. Den fjerde måling, i midten af de tre målinger, har en kvadreret afstand på $9$. Dermed kan Rued konkludere at $x_\mathrm d=2$, $y_\mathrm d=17$, og $z_\mathrm d^2=9$. Det gør, at han med sikkerhed kan svare $(2,17,3)$.

10000

? 40 40

8

? 42 42

0

! 42 42 0

10000

? 1 17

10

? 2 18

10

? 2 16

10

? 3 17

10

? 2 17

9

! 2 17 3