Lýsing
Auðvitað er þetta dæmi.
Þetta er gagnvirkt verkefni. Gefið er óþekkt óstefnt net með $n$ hnútum og $m$ leggjum, án margfaldra leggja eða sjálflykkja. Í hvert sinn getur þú spurt samskiptasafnið eftirfarandi spurningar:
- Gefið hnútmengi $S \subseteq \{1, 2, \dots, n\}$, spyrðu hvort þetta hnútmengi sé óháð mengi.
Hér þýðir óháð mengi að enginn leggur sé á milli neinna tveggja ólíkra hnúta í menginu $S$.
Markmið þitt er að ákvarða allt leggjamengi netsins með því að nota ekki fleiri en $M = n + m(2 + \lceil\log_2 n\rceil)$ fyrirspurnir.
Athugaðu að þú veist ekki gildi $m$ fyrirfram, og samskiptasafnið er aðlögunarhæft (adaptive), þ.e. netið er ekki fast frá upphafi heldur verður það aðlagað dýnamískt eftir fyrirspurnum þínum.
Inntak
Fyrsta línan inniheldur heiltölu $T$ ($1 \le T \le 100$), sem táknar fjölda prófunartilvika.
Fyrir hvert prófunartilvik inniheldur ein lína heiltölu $n$ ($1 \le n \le 500$), sem táknar fjölda hnúta í óþekkta óstefnda netinu.
Tryggt er að summa $n$ yfir öll prófunartilvik fari ekki yfir $500$, $0 \le m \le 500$, og summa $m$ fari ekki yfir $500$.
Samskipti
Þegar þú þarft að senda fyrirspurn skaltu prenta eina línu:
? k v_1 v_2 ... v_k
þar sem $k$ táknar stærð hnútmengisins, og $v_1, v_2, \dots, v_k$ eru vísar hnútanna í menginu sem þú spyrð um, allir innbyrðis ólíkir.
Samskiptasafnið mun skila heiltölu: $1$ ef hnútmengið er óháð mengi; $0$ annars.
Þegar þú hefur ákvarðað alla leggi netsins skaltu prenta eina línu:
! m u_1 v_1 u_2 v_2 ... u_m v_m
þar sem $m$ er fjöldi leggja í óstefnda netinu, og $(u_i, v_i)$ táknar legg í netinu. Þú mátt prenta leggina í hvaða röð sem er.
Eftir það, ef engin prófunartilvik eru eftir, verður forritið þitt að hætta keyrslu samstundis; annars á það að halda áfram í næsta prófunartilvik.
Dæmi
Inntak 1
1 4 0 1 0 0 1 0
Úttak 1
? 2 1 2 ? 2 1 3 ? 2 1 4 ? 2 2 3 ? 2 2 4 ? 2 3 4 ! 4 1 2 2 3 3 4 1 4
Athugasemd
Dæmið sýnir gagnvirkt ferli þar sem spurt er um tilvist hvers leggs fyrir sig.