Problem J
Sweater
Languages
da
en
is
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, \ldots , 100$. Formelt er pubcrawl-rækkefølgen en permutation $\pi $ af disse tal med $\pi (i) \neq 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,\ldots , 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,\ldots , 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.
| Read | Sample Interaction 1 | Write |
|---|
4
? 10 4
8
? 54 9
4
? 54 8
42
! 42
