← 返回题目列表

Codeforces · 1617/D1

D1. 冒名顶替者太多(简单版)

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

这是一个交互问题。简单版和困难版之间的唯一区别是问题数量的限制。

有 $$$n$$$ 玩家标记为从 $$$1$$$ 到 $$$n$$$。保证 $$$n$$$ 是 $$$3$$$ 的倍数。

其中有$$$k$$$冒名顶替者和$$$n-k$$$船员。冒名顶替者的数量 $$$k$$$ 不会提供给您。保证 $$$\frac{n}{3} < k < \frac{2n}{3}$$$。

在每个问题中,您可以选择三个不同的整数 $$$a$$$、$$$b$$$、$$$c$$$ ($$$1 \le a, b, c \le n$$$) 并询问:“在标记为 $$$a$$$、$$$b$$$ 和 $$$c$$$ 的玩家中,有更多冒名顶替者还是更多船员?”如果冒充者多于船员,您将获得整数 $$$0$$$,否则为 $$$1$$$。

在询问最多 $$$2n$$$ 问题后,找出冒名顶替者 $$$k$$$ 的数量以及冒充者玩家的指数。

陪审团是自适应的,这意味着冒名顶替者的指数可能不会预先确定,并且可能取决于您的问题。保证至少有一组冒名顶替者满足约束条件并随时回答您的问题。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 100$$$)。测试用例的描述如下。

每个测试用例的第一行也是唯一一行包含一个整数 $$$n$$$ ($$$6 \le n < 10^4$$$, $$$n$$$ 是 $$$3$$$ 的倍数) — 玩家数量。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^4$$$。

互动

对于每个测试用例,交互从读取 $$$n$$$ 开始。

那么你最多可以通过以下方式提出 $$$2n$$$ 问题:

"? a b c" ($$$1 \le a, b, c \le n$$$, $$$a$$$, $$$b$$$ 和 $$$c$$$ 成对不同)。

在每一个之后,你应该读到一个整数 $$$r$$$,如果标记为 $$$a$$$、$$$b$$$ 和 $$$c$$$ 的玩家中冒名顶替者多于船员,则该整数等于 $$$0$$$,否则等于 $$$1$$$。

回答$$$-1$$$而不是$$$0$$$或$$$1$$$表示您进行了无效查询或超出了查询次数。收到$$$-1$$$后立即退出,您将看到错误的答案判决。否则,您可以获得任意判决,因为您的解决方案将继续从关闭的流中读取。

当您找到所有冒名顶替者的索引后,打印一行“!”(不带引号),后跟冒名顶替者的数量 $$$k$$$,然后是表示冒名顶替者索引的 $$$k$$$ 整数。请注意,您必须将所有这些信息打印在同一行上。

打印答案后,您的程序必须继续解决剩余的测试用例,或者如果所有测试用例都已解决则退出。

打印查询和答案后,不要忘记输出行尾并刷新输出缓冲区。否则,您将得到超出空闲限制的判决。要进行冲洗,请使用:

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

黑客

你无法解决这个问题。

示例

输入 #1

2
6

0

1

9

1

输出 #1

? 1 2 3

? 3 4 5

! 3 4 1 2

? 7 1 9

! 4 2 3 6 8

注意

示例交互说明(注意,该示例仅用于演示交互过程,并不提供任何解决方案的提示):

对于第一个测试用例:

问题“?1 2 3”返回$$$0$$$,因此$$$1$$$、$$$2$$$和$$$3$$$玩家中冒名顶替者比船员多。

问题“?3 4 5”返回$$$1$$$,因此$$$3$$$、$$$4$$$和$$$5$$$玩家中船员的数量多于冒名顶替者的数量。

输出“! 3 4 1 2”意味着奇迹般地发现了所有冒名顶替者。有 $$$k = 3$$$ 冒名顶替者。冒名顶替者的玩家是玩家 $$$4$$$、$$$1$$$ 和 $$$2$$$。

对于第二个测试用例:

问题“?7 1 9”返回$$$1$$$,因此$$$7$$$、$$$1$$$和$$$9$$$玩家中船员的数量多于冒名顶替者的数量。

输出“!4 2 3 6 8”意味着人们奇迹般地发现了所有冒名顶替者。有 $$$k = 4$$$ 冒名顶替者。冒名顶替者的玩家是玩家 $$$2$$$、$$$3$$$、$$$6$$$ 和 $$$8$$$。