Universal Cup Judging System

Universal Cup

Limite de temps : 2.0 s Limite de mémoire : 1024 MB Points totaux : 100 Difficulté: [afficher] Interactif Hackable ✓
Statistiques

Problembeskrivelse

Selvfølgelig er dette et problem.

Dette er et interaktivt problem. Du får gitt en ukjent urettet graf med $n$ noder og $m$ kanter, uten multikanter eller løkker. Hver gang kan du stille interaksjonsbiblioteket følgende spørsmål:

  • Gitt en nodemengde $S \subseteq \{1, 2, \dots, n\}$, spør om denne nodemengden er en uavhengig mengde.

Her betyr en uavhengig mengde at det ikke er noen kant mellom noen to forskjellige noder i mengden $S$.

Målet ditt er å bestemme hele kantmengden til grafen ved å bruke høyst $M = n + m(2 + \lceil\log_2 n\rceil)$ spørringer.

Merk at du ikke kjenner verdien av $m$ på forhånd, og at interaksjonsbiblioteket er adaptivt, dvs. at grafen ikke er fastsatt fra starten av, men justeres dynamisk i henhold til spørringene dine.

Inndata

Den første linjen inneholder et heltall $T$ ($1 \le T \le 100$), som angir antall testtilfeller.

For hvert testtilfelle inneholder én linje et heltall $n$ ($1 \le n \le 500$), som angir antall noder i den ukjente urettede grafen.

Det er garantert at summen av $n$ over alle testtilfeller ikke overstiger $500$, $0 \le m \le 500$, og at summen av $m$ ikke overstiger $500$.

Interaksjon

Når du trenger å stille en spørring, skriv ut én linje:

? k v_1 v_2 ... v_k

der $k$ angir størrelsen på nodemengden, og $v_1, v_2, \dots, v_k$ er indeksene til nodene i mengden du spør om, alle parvis forskjellige.

Interaksjonsbiblioteket vil returnere et heltall: $1$ hvis nodemengden er en uavhengig mengde; $0$ ellers.

Når du har bestemt alle kantene i grafen, skriv ut én linje:

! m u_1 v_1 u_2 v_2 ... u_m v_m

der $m$ er antall kanter i den urettede grafen, og $(u_i, v_i)$ representerer en kant i grafen. Du kan skrive ut kantene i hvilken som helst rekkefølge.

Etter det, hvis det ikke er flere testtilfeller igjen, må programmet ditt avsluttes umiddelbart; ellers skal det gå videre til neste testtilfelle.

Eksempler

Inndata 1

1
4
0
1
0
0
1
0

Utdata 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

Merk

Eksempelet viser en interaktiv prosess der man spør individuelt om hver kant eksisterer.

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.