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

Mô tả bài toán

Tất nhiên, đây là một bài toán.

Đây là một bài toán tương tác. Bạn được cho một đồ thị vô hướng chưa biết gồm $n$ đỉnh và $m$ cạnh, không có đa cạnh hay khuyên. Mỗi lần, bạn có thể hỏi thư viện tương tác câu hỏi sau:

  • Cho một tập đỉnh $S \subseteq \{1, 2, \dots, n\}$, hỏi xem tập đỉnh này có phải là một tập độc lập hay không.

Ở đây, tập độc lập có nghĩa là không có cạnh nào nối giữa hai đỉnh phân biệt bất kỳ trong tập $S$.

Mục tiêu của bạn là xác định toàn bộ tập cạnh của đồ thị bằng cách sử dụng không quá $M = n + m(2 + \lceil\log_2 n\rceil)$ truy vấn.

Lưu ý rằng bạn không biết trước giá trị của $m$, và thư viện tương tác là thích ứng (adaptive), tức là đồ thị không cố định ngay từ đầu mà sẽ được điều chỉnh linh hoạt theo các truy vấn của bạn.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $T$ ($1 \le T \le 100$), biểu thị số lượng bộ dữ liệu.

Với mỗi bộ dữ liệu, một dòng chứa một số nguyên $n$ ($1 \le n \le 500$), biểu thị số đỉnh của đồ thị vô hướng chưa biết.

Dữ liệu đảm bảo tổng của $n$ trong tất cả các bộ dữ liệu không vượt quá $500$, $0 \le m \le 500$, và tổng của $m$ không vượt quá $500$.

Tương tác

Khi bạn cần thực hiện một truy vấn, hãy in ra một dòng:

? k v_1 v_2 ... v_k

trong đó $k$ biểu thị kích thước của tập đỉnh, và $v_1, v_2, \dots, v_k$ là chỉ số của các đỉnh trong tập hợp bạn đang hỏi, đôi một phân biệt.

Thư viện tương tác sẽ trả về một số nguyên: $1$ nếu tập đỉnh là một tập độc lập; $0$ trong trường hợp ngược lại.

Khi bạn đã xác định được tất cả các cạnh của đồ thị, hãy in ra một dòng:

! m u_1 v_1 u_2 v_2 ... u_m v_m

trong đó $m$ là số cạnh của đồ thị vô hướng, và $(u_i, v_i)$ biểu diễn một cạnh trong đồ thị. Bạn có thể in các cạnh theo bất kỳ thứ tự nào.

Sau đó, nếu không còn bộ dữ liệu nào, chương trình của bạn phải kết thúc ngay lập tức; ngược lại, nó cần tiếp tục xử lý bộ dữ liệu tiếp theo.

Ví dụ

Dữ liệu vào 1

1
4
0
1
0
0
1
0

Kết quả 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

Giải thích

Ví dụ minh họa quá trình tương tác khi hỏi riêng lẻ xem từng cạnh có tồn tại hay không.

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.