题库练习 MAD Interactive Problem
← 上一题 下一题 →

A16700 | MAD Interactive Problem

时间限制1s
内存限制256MB
通过 / 提交0/0

题目描述

这是一个交互题。

有一个秘密序列 $a_1, a_2, \ldots, a_{2n-1}, a_{2n}$,其中每个 $1$ 到 $n$ 的整数恰好出现两次。

你的任务是通过如下类型的询问来猜测这个序列:

- "? $k\;j_1\;j_2\;\ldots\;j_k$" —— 你可以选择一个整数 $k$($1 \leq k \leq 2n$)以及 $k$ 个互不相同的下标 $j_1, j_2, \ldots, j_k$($1 \leq j_1, j_2, \ldots, j_k \leq 2n$)。对于你的询问,裁判会返回 $\operatorname{MAD}([a_{j_1}, a_{j_2}, \ldots, a_{j_k}])$。

我们定义一个整数序列的 $\operatorname{MAD}$(最大重复出现数)为在序列中至少出现两次的最大整数。如果没有任何数至少出现两次,则 $\operatorname{MAD}$ 的值为 $0$。以下是一些示例:

- $\operatorname{MAD}([1, 2, 1]) = 1$;
- $\operatorname{MAD}([2, 2, 3, 3]) = 3$;
- $\operatorname{MAD}([1, 2, 3, 4]) = 0$。

请使用不超过 $3n$ 次询问来确定这个秘密序列。

输入格式

每组测试数据包含多组测试用例。第一行为测试用例数 $t$($1 \leq t \leq 3000$)。接下来描述每个测试用例。

每个测试用例的第一行包含一个整数 $n$($2 \leq n \leq 300$)。

保证所有测试用例的 $n^2$ 之和不超过 $10^5$。

在你读入这行输入后,交互将在你第一次询问时开始。

输出格式

(本题为交互题,无传统输出格式。要按照交互协议进行答题。)

输入输出样例

输入 #1
2
2

2

0

1

2

0

1

1
输出 #1
? 2 2 1

? 2 1 3

? 3 1 3 4

! 2 2 1 1

? 2 1 2

? 2 1 3

? 3 1 3 4

! 1 2 1 2
C++ 编辑器
输入
输出