Universal Cup Judging System

Universal Cup

Límite de tiempo: 2.0 s Límite de memoria: 1024 MB Puntuación total: 100 Dificultad: [mostrar] Interactivo Hackeable ✓
Estadísticas

Problembeschreibung

Natürlich ist das ein Problem.

Dies ist ein interaktives Problem. Gegeben ist ein unbekannter ungerichteter Graph mit $n$ Knoten und $m$ Kanten, ohne Mehrfachkanten oder Selbstschleifen. Jedes Mal kannst du der Interaktionsbibliothek die folgende Frage stellen:

  • Gegeben eine Knotenmenge $S \subseteq \{1, 2, \dots, n\}$, frage, ob diese Knotenmenge eine unabhängige Menge ist.

Hierbei bedeutet eine unabhängige Menge, dass es zwischen je zwei verschiedenen Knoten in der Menge $S$ keine Kante gibt.

Dein Ziel ist es, die gesamte Kantenmenge des Graphen mit höchstens $M = n + m(2 + \lceil\log_2 n\rceil)$ Abfragen zu bestimmen.

Beachte, dass du den Wert von $m$ im Voraus nicht kennst und die Interaktionsbibliothek adaptiv ist, d. h. der Graph steht nicht von Anfang an fest, sondern wird dynamisch entsprechend deinen Abfragen angepasst.

Eingabe

Die erste Zeile enthält eine ganze Zahl $T$ ($1 \le T \le 100$), die die Anzahl der Testfälle angibt.

Für jeden Testfall enthält eine Zeile eine ganze Zahl $n$ ($1 \le n \le 500$), die die Anzahl der Knoten des unbekannten ungerichteten Graphen angibt.

Es wird garantiert, dass die Summe von $n$ über alle Testfälle $500$ nicht überschreitet, $0 \le m \le 500$ gilt und die Summe von $m$ ebenfalls $500$ nicht überschreitet.

Interaktion

Wenn du eine Abfrage stellen möchtest, gib eine Zeile aus:

? k v_1 v_2 ... v_k

wobei $k$ die Größe der Knotenmenge bezeichnet und $v_1, v_2, \dots, v_k$ die Indizes der Knoten in der abgefragten Menge sind, alle paarweise verschieden.

Die Interaktionsbibliothek gibt eine ganze Zahl zurück: $1$, falls die Knotenmenge eine unabhängige Menge ist; andernfalls $0$.

Wenn du alle Kanten des Graphen bestimmt hast, gib eine Zeile aus:

! m u_1 v_1 u_2 v_2 ... u_m v_m

wobei $m$ die Anzahl der Kanten im ungerichteten Graphen ist und $(u_i, v_i)$ eine Kante im Graphen darstellt. Du kannst die Kanten in beliebiger Reihenfolge ausgeben.

Wenn danach keine weiteren Testfälle übrig sind, muss dein Programm sofort beendet werden; andernfalls sollte es mit dem nächsten Testfall fortfahren.

Beispiele

Eingabe 1

1
4
0
1
0
0
1
0

Ausgabe 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

Hinweis

Das Beispiel zeigt einen interaktiven Prozess, bei dem einzeln abgefragt wird, ob jede Kante existiert.

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.