Universal Cup Judging System

Universal Cup

Süre Sınırı: 2.0 s Bellek Sınırı: 1024 MB Toplam puan: 100 Zorluk: [göster] Etkileşimli Hack'lenebilir ✓
İstatistikler

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.

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
#1842EditorialOpenNew Editorial for Problem #18123wangmaruiView

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.