← 返回题目列表

Codeforces · 1363/D

D. 猜猜最大值

中文机器翻译题面 查看原题

这是一个交互问题。

Ayush 设计了一种新方案来设置他的锁的密码。该锁有 $$$k$$$ 个槽,每个槽可以容纳从 $$$1$$$ 到 $$$n$$$ 的整数。密码 $$$P$$$ 是 $$$k$$$ 整数的序列,每个整数在 $$$[1, n]$$$ 范围内,其中第 $$$i$$$ 个元素进入锁的第 $$$i$$$ 个插槽。

为了设置他的锁的密码,Ayush 提出了一个由 $$$n$$$ 整数组成的数组 $$$A$$$,每个整数都在 $$$[1, n]$$$ 范围内(不一定不同)。然后,他选择 $$$k$$$ 索引 $$$S_1, S_2, ..., S_k$$$ $$$(S_i \underset{i \neq j} \cap S_j = \emptyset)$$$ 的非空相互不相交子集,并将其密码设置为 $$$P_i = \max\limits_{j \notin S_i} A[j]$$$。换句话说,密码中的第 $$$i$$$ 整数等于 $$$A$$$ 中索引不属于 $$$S_i$$$ 的所有元素的最大值。

您将获得 Ayush 选择的索引子集。您需要猜测密码。要进行查询,您可以选择数组索引的非空子集,并询问索引在此子集中的数组所有元素中的最大值。您最多可以提出 12 个疑问。

输入

输入的第一行包含一个整数 $$$t$$$ $$$(1 \leq t \leq 10)$$$ — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ $$$(2 \leq n \leq 1000, 1 \leq k \leq n)$$$ - 数组的大小和子集的数量。接下来是 $$$k$$$ 行。第 $$$i$$$ 行包含一个整数 $$$c$$$ $$$(1 \leq c \lt n)$$$ — 子集 $$$S_i$$$ 的大小,后跟 $$$c$$$ 范围内的不同整数 $$$[1, n]$$$ — 子集 $$$S_i$$$ 的索引。

保证任意两个子集的交集为空。

互动

要提出查询,请打印一行:

- 在开头打印“? c”(不带引号),其中 $$$c$$$ $$$(1 \leq c \leq n)$$$ 表示正在查询的索引子集的大小,后跟 $$$c$$$ 范围 $$$[1, n]$$$ 内的不同空格分隔整数。

对于每个查询,您将收到一个整数 $$$x$$$ — 数组中所有查询索引中的最大值。如果查询的索引子集无效或超出查询数量(例如其中一个索引大于 $$$n$$$),那么您将得到 $$$x = -1$$$。在这种情况下,您应该立即终止该程序。

当您猜出密码后,打印一行“!”(不带引号),后跟 $$$k$$$ 空格分隔的整数 - 密码序列。

猜测密码不计入询问次数。

之后,您应该读取一个字符串。如果您猜对密码,您将收到字符串“正确”。在这种情况下,您应该继续解决剩余的测试用例。如果猜测的密码不正确,您将收到字符串“In Correct”。在这种情况下,您应该立即终止该程序。

交互器不自适应。数组 $$$A$$$ 不会随查询而改变。

打印查询后,不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:

- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。

黑客

要破解该解决方案,请使用以下测试格式:

输入的第一行应包含一个整数 $$$t$$$ $$$(1 \leq t \leq 10)$$$ — 测试用例的数量。

每个测试用例的第一行应包含两个整数 $$$n$$$ 和 $$$k$$$ $$$(2 \leq n \leq 1000, 1 \leq k \leq n)$$$ - 数组的大小和子集的数量。下一行应由 $$$n$$$ 空格分隔的整数组成,范围为 $$$[1, n]$$$ — 数组 $$$A$$$。 $$$k$$$ 行应该跟随。第 $$$i$$$ 行应包含一个整数 $$$c$$$ $$$(1 \leq c \lt n)$$$ — 子集 $$$S_i$$$ 的大小,后跟 $$$c$$$ 范围内的不同整数 $$$[1, n]$$$ — 子集 $$$S_i$$$ 的索引。

任意两个子集的交集必须为空。

示例

输入 #1

1
4 2
2 1 3
2 2 4

1

2

3

4

Correct

输出 #1

? 1 1

? 1 2

? 1 3

? 1 4

! 4 3

注意

示例中的数组 $$$A$$$ 为 $$$[1, 2, 3, 4]$$$。密码长度为$$$2$$$。密码的第一个元素是 $$$A[2]$$$、$$$A[4]$$$ 中的最大值(由于第一个子集包含索引 $$$1$$$ 和 $$$3$$$,因此我们采用剩余索引中的最大值)。密码的第二个元素是 $$$A[1]$$$、$$$A[3]$$$ 中的最大值(因为第二个子集包含索引 $$$2$$$、$$$4$$$)。

猜测密码后不要忘记读取字符串“正确”/“错误”。