Problem J
Jakki
Languages
da
en
is
Þú týndir uppáhaldsjakkanum þínum í gærkvöldi þegar þú varst á kráarferð með fimmtán vinum þínum. Þú mannst lítið en þökk sé sjálfum í símanum þínum hefur þér tekist að ákvarða að jakkinn var þegar týndur þegar þú varst á kránni $p$. Enn fremur sérðu útfrá annarri sjálfu og tímasetningu þess að þú varst enn með jakkan á kránni á undan $p$, en þú getur ekki séð hvaða krá það er útfrá myndinni.
Hópurinn fer alltaf á sömu krár í sömu röð, en þú hefur almennt ekki fylgst svo vel með, þú fylgir bara hópnum. Annað en þú kunna vinir þínir kráarröðina utan að. Til að vinir þínir átti sig ekki þá því hvað þú ert utan við þig muntu einungis spyrja hvern þeirra spurningu á forminu “Hvað er nafn kráarinnar sem við förum á $k$ krám eftir krá $q$?”. Hér er $q$ nafn kráar og $k$ jákvæð heiltala. Þú hlýtur að geta fundið jakkann þinn með nokkrum vel völdum spurningum!
Bærinn hefur $100$ krár númeraðar $1, \ldots , 100$. Formlega séð er kráarferðin umröðun $\pi $ á þessum tölum með $\pi (i) \neq i$; eftir að fara á krá $i$ fer hópurinn ávallt á krá $\pi (i)$. Umröðunin er ekki nauðsynlega rásuð. Kráarferðin byrjar á einhverri krá og heldur svo áfram samkvæmt $\pi $ þar til þreytan tekur yfir og fólk fer heim.
Interaction
Þetta er gagnvirkt verkefni. Forrit þitt verður keyrt á móti yfirferðarforriti sem les staðalúttak forrits þíns og skrifar gögn á staðalinntak forrits þíns. Yfirferðarforritið byrjar á að skrifa eina heiltölu $p\in \{ 1,\ldots , 100\} $, nafn kránnar sem þú fórst á beint eftir að þú gleymdir jakkanum. Þetta mun aldrei vera fyrsta krá kráarferðar síðasta kvölds. Þú getur spurt allt að $15$ spurninga. Hver spurning verður að vera á forminu “? $q$ $k$”, þar sem $q,k \in \{ 1,\ldots , 100\} $. Yfirferðarforritið mun svara nafni kránnar sem er $k$ krám síðar en krá $q$ í kráarferðinni. Eftir mest $15$ spurningar verður forrit þitt að ljúka með því að prenta streng á forminu “! $j$”, þannig að $j$-ta kráin er þar sem þú týndir jakkanum þínum, það er að segja, $\pi (j)= p$.
Í hverju prófunartilfelli er kráarferðin $\pi $ og vísirinn $j$ fyrirfram ákveðnir af yfirferðarforritinu.
| Read | Sample Interaction 1 | Write |
|---|
4
? 10 4
8
? 54 9
4
? 54 8
42
! 42
