Problem J
Sweater

Foto: Joan Rocaguinard; licens CC BY-SA 3.0.

Du har mistet din yndlingssweater under gårsdagens pubcrawl med dine femten venner. Du husker meget lidt, men takket være nogle selfies på din telefon har du været i stand til at identificere en pub $p$, hvor du allerede havde mistet sweateren. Desuden afslører tidsstemplet på en anden selfie, at du stadig havde sweateren på den pub, der blev besøgt umiddelbart før pub $p$. Men du kan ikke afgøre ud fra billedet, hvilken pub det er.

Din vennegruppe besøger altid pubberne i samme rækkefølge, som du dog aldrig har lært dig — du plejer bare at følge med gruppen. I modsætning til dig kender alle dine venner pubcrawl-rækkefølgen ud og ind. For at undgå at virke for glemsom, vil du stille dem spørgsmål af formen »Hvad hedder den pub, som vi altid besøger $k$ pubber efter pub $q$?« Her er $q$ navnet på en pub, og $k$ er et positivt heltal. Mon ikke du finde din sweater med nogle velvalgte spørgsmål?

Byen har $100$ pubber med navnene $1,\dots ,100$. Formelt er pubcrawl-rækkefølgen en permutation $\pi$ af disse tal med $\pi (i)\ne i$; efter at have besøgt pub $i$ fortsætter gruppen altid til pub $\pi (i)$. Permutationen behøver ikke at være cyklisk. En pubcrawl starter på en vilkårlig pub og fortsætter med at besøge pubberne som beskrevet af $\pi$, indtil I bliver trætte og går hjem.

Interaction

Dette er et interaktivt problem. Din indsendelse vil blive kørt mod et interaktor-program, som læser dit programs standardudskrift og skriver til dit programs standardindlæsning. Interaktoren begynder med at skrive et enkelt heltal $p\in \{1,\dots ,100\}$, navnet på den pub, der blev besøgt umiddelbart efter, at du mistede din sweater. Dette vil aldrig være den første pub, som din gruppe besøgte i går aftes. Du kan derefter stille op til $15$ spørgsmål. Hvert spørgsmål skal være på formen »? $q$ $k$«, hvor $q,k\in \{1,\dots ,100\}$. Interaktoren vil svare med navnet på den pub, der er $k$ pubber frem i pubcrawl-rækkefølgen fra pub $q$. Efter de maksimalt $15$ spørgsmål skal du afslutte ved at skrive en streng på formatet »! $j$«, hvor $j$ er pubben, hvor du mistede din sweater, dvs. $\pi (j)=p$.

For hvert testfald er pubcrawl-permutationen $\pi$ og indekset $j$ fastsat på forhånd af interaktoren.

4

? 10 4

8

? 54 9

4

? 54 8

42

! 42