← 返回题目列表

Codeforces · 2022/D1

D1. Asesino(简单版)

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

这是问题的简单版本。在此版本中,您最多可以提出 $$$n+69$$$ 问题。只有当问题的两个版本都得到解决时,你才能进行黑客攻击。

这是一个交互问题。

玩“Asesino”游戏是墨西哥国家IOI训练中的传统,该游戏类似于“Among Us”或“Mafia”。

今天,编号从$$$1$$$到$$$n$$$的$$$n$$$玩家将扮演“Asesino”,扮演以下三个角色:

- 骑士:骑士是总是说实话的人。
- 无赖:无赖是指总是说谎的人。
- 冒名顶替者:冒名顶替者是指每个人都认为是骑士,但实际上却是无赖的人。

每个玩家都会在游戏中被分配一个角色。只会有一名冒名顶替者,但可以有任意数量(可能为零)的骑士和无赖。

作为游戏主持人,您不小心忘记了每个人的角色,但您需要确定冒名顶替者的玩家。

要确定冒名顶替者,您将提出一些问题。在每个问题中,您将选择两个玩家 $$$i$$$ 和 $$$j$$$ ($$$1 \leq i, j \leq n$$$; $$$i \neq j$$$) 并询问玩家 $$$i$$$ 是否认为玩家 $$$j$$$ 是骑士。问题结果如下表所示。

KnightKnaveImpostorKnightYesNoYesKnaveNoYesNoImpostorNoYes— 行 $$$a$$$ 和列 $$$b$$$ 中的单元格的响应是当 $$$i$$$ 具有角色 $$$a$$$ 且 $$$j$$$ 具有行 $$$b$$$ 时提出问题的结果。例如,右上角单元格中的“是”属于“骑士”行和“冒名顶替者”列,因此它是当 $$$i$$$ 是骑士并且 $$$j$$$ 是冒名顶替者时的响应。

在最多 $$$n + 69$$$ 问题中找到冒名顶替者。

注意:评分器是自适应的:玩家的角色一开始并不固定,可能会根据您的问题而改变。然而,可以保证在该问题的约束下存在与之前提出的所有问题一致的角色分配。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 10^5$$$) — 玩游戏的人数。

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

互动

要提出问题,请按以下格式输出一行:

- "? i j" ($$$1 \leq i,j \leq n$$$; $$$i \neq j$$$) – 询问玩家 $$$i$$$ 是否认为玩家 $$$j$$$ 是骑士。

如果玩家 $$$i$$$ 认为玩家 $$$j$$$ 是骑士,陪审团将输出“1”,否则输出“0”。

当你确定冒名顶替者是哪个玩家后,按以下格式输出一行:

- "! i" ($$$1 \leq i \leq n$$$) — 冒名顶替者是玩家 $$$i$$$。

请注意,回答不计入您的 $$$n+69$$$ 问题限制。

如果您做出了无效的输出、使用了超过 $$$n+69$$$ 问题或错误地确定了冒名顶替者,陪审团将回复“-1”,并且您将收到错误答案判决。收到“-1”后,您的程序必须立即终止。否则,您可能会收到任意判决,因为您的解决方案可能正在从封闭的流中读取。

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

- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- Python 中的 sys.stdout.flush() ;
- Rust 中的 std::io::stdout().flush() ;
- 请参阅其他语言的文档。

黑客格式

对于 hack,请使用以下格式。

第一行应包含一个整数 $$$t$$$ — 测试用例的数量。

每个测试用例的第一行应包含整数 $$$n$$$ 后跟字符串“manual”。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$-1 \le a_i \le 1$$$) - 每个玩家的角色。 $$$1$$$ 表示骑士,$$$0$$$ 表示无赖,$$$-1$$$ 表示冒名顶替者。必须有一个 Impostor,即必须有一个索引 $$$i$$$ 使得 $$$a_i=-1$$$。

例如,示例输入的 hack 格式为:

示例

输入 #1

2
7

1

0

0

1

1

0

0

1

4

0

1

1

1

输出 #1

? 1 3

? 7 6

? 2 5

? 6 2

? 4 5

? 4 6

? 1 4

? 2 4

! 4

? 1 2

? 2 3

? 3 4

? 4 1

! 3

注意

请注意,示例测试用例并不代表提问的最佳策略,只是为了演示交互格式而显示。具体来说,我们无法从示例中提出的问题确定哪个玩家是冒名顶替者。

在示例的第一个测试用例中,索引 $$$2$$$ 和 $$$6$$$ 的玩家是骑士,索引 $$$1$$$、$$$3$$$、$$$5$$$ 和 $$$7$$$ 的玩家是无赖,而冒名顶替者是索引 $$$4$$$。以下是对所问问题的解释:

- 在第一个查询中,玩家 $$$i$$$ 是一个无赖,而玩家 $$$j$$$ 是一个无赖。答案是“是”,因为无赖总是撒谎。
- 在第二个查询中,玩家 $$$i$$$ 是一名无赖,而玩家 $$$j$$$ 是一名骑士。答案是否定的,因为无赖总是撒谎。
- 在第三个查询中,玩家 $$$i$$$ 是骑士,玩家 $$$j$$$ 是无赖。答案是否定的,因为骑士总是说实话。
- 在第四个查询中,玩家 $$$i$$$ 是一名骑士,玩家 $$$j$$$ 是一名骑士。答案是“是”,因为骑士总是说实话。
- 在第五个查询中,玩家 $$$i$$$ 是冒名顶替者,玩家 $$$j$$$ 是无赖。答案是“是”,因为冒名顶替者总是撒谎。
- 在第六个查询中,玩家 $$$i$$$ 是冒名顶替者,玩家 $$$j$$$ 是骑士。答案是否定的,因为冒名顶替者总是撒谎。
- 在第七个查询中,玩家 $$$i$$$ 是无赖,玩家 $$$j$$$ 是冒名顶替者。答案是否定的,因为无赖总是撒谎,而无赖认为冒名顶替者是骑士。
- 在第八个查询中,玩家 $$$i$$$ 是骑士,玩家 $$$j$$$ 是冒名顶替者。答案是“是”,因为骑士总是说实话,并且骑士认为冒名顶替者是骑士。