← 返回题目列表

Codeforces · 2222/E

E. 寻求真相

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

七风 - 连接世界

这是一个交互问题。

有两个隐藏整数 $$$k$$$ 和 $$$c$$$ 使得 $$$k\in \{1,2,3\}$$$ 和 $$$1\le c\le 2^n-1$$$。 请注意 $$$c\neq 0$$$。

在进行任何互动之前,您需要告诉陪审团 非负 整数$$$a\le 2^n-1$$$。然后,评分者将使用 $$$a$$$ 作为集合 $$$S$$$ 中的初始元素,即最初 $$$S = \{a\}$$$。

接下来,您最多可以进行以下两种类型的 $$$n+3$$$ 查询:

  1. 选择一个整数 $$$x$$$,使得 $$$0\leq x\le 2^n-1$$$。陪审团会将 $$$f(x)$$$ 插入 $$$S$$$ 中,然后以 $$$|S|$$$ 响应(即插入后 $$$S$$$ 的大小);
  2. 选择一个整数 $$$y$$$,使得 $$$0\leq y\le 2^n-1$$$。陪审团将回答整数 $$$z$$$ 的数量,使得 $$$z\in S$$$ 和 $$$z\geq y$$$。

$$$f(x)$$$ 的定义如下:

$$f(x)= \begin{cases} x\,\&\,c & \text{if}\, k=1,\\ x\,|\,c & \text{if}\, k=2,\\ x\oplus c & \text{if}\, k=3.\\ \end{cases}$$

这里,$$$\&$$$表示按位与运算,$$$|$$$表示按位或运算,$$$\oplus$$$表示按位异或运算。

您的任务是使用最多 $$$n+3$$$ 交互来确定 $$$k$$$ 和 $$$c$$$ 的值。

请注意,报告答案不计入 $$$n+3$$$ 互动。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 60$$$)。然后,进行互动。

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

互动

首先,您需要输出一个整数 $$$a$$$ ($$$0\leq a\le 2^n-1$$$) — 您为集合 $$$S$$$ 选择的初始元素。

要进行交互,请按以下格式输出一行:

  1. $$$\mathtt{I}\;x$$$ ($$$0\leq x\le 2^n-1$$$) — 将 $$$f(x)$$$ 插入集合 $$$S$$$ 中。之后,评审团将返回$$$|S|$$$。
  2. $$$\mathtt{Q}\;y$$$ ($$$0\leq y\le 2^n-1$$$) — 查询集合 $$$S$$$ 中有多少个 $$$z$$$-s 满足 $$$z \geq y$$$。陪审团将返回此类 $$$z$$$-s 的计数。

要给出最终答案,请按以下格式输出一行:

  • $$$\mathtt{A}\;k\;c$$$ ($$$1\leq k\le 3$$$, $$$1\leq c\le 2^n-1$$$) — $$$k$$$ 和 $$$c$$$ 的值。

打印每个查询后,不要忘记输出行尾并刷新$$$^{\text{*}}$$$ 输出。否则,你会得到 超出空闲限制 判决。

如果在任何交互步骤中您读取 $$$-1$$$ 而不是有效数据,您的解决方案必须立即退出。这意味着您的解决方案将收到 错误答案 由于无效查询或任何其他错误。未能退出可能会导致任意判决,因为您的解决方案将继续从关闭的流中读取。

请注意,评分者是 非自适应。这意味着 $$$k$$$ 和 $$$c$$$ 的值在开始时是固定的,不会根据您的交互而改变。

黑客

要破解,请使用以下格式。

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

每个测试用例的唯一行应包含三个整数 $$$n$$$、$$$k$$$ 和 $$$c$$$ ($$$2 \leq n \leq 60$$$、$$$1\leq k\le 3$$$、$$$1\leq c\le 2^n-1$$$)。

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

$$$^{\text{*}}$$$要刷新,请使用:

  • fflush(标准输出) or cout.flush() 在 C++ 中;
  • sys.stdout.flush() 在 Python 中;
  • 请参阅其他语言的文档。

示例

输入
复制

3
2


1

2


2

1

2

2

3

2


2

2

2

输出
复制


3
I 3

A 1 3

1
I 0

Q 2

Q 1

Q 0

I 3

A 2 2

1
I 1

I 0

A 3 1

注意

示例中的交互过程如下:

解决方案评审团说明
3有 $$$3$$$ 测试用例。
2$$$n=2$$$。隐藏的整数值为 $$$k=1$$$ 和 $$$c=3$$$。
3最初,$$$S = \{3\}$$$。
我 31将 $$$f(3)=3\,\& \,3=3$$$ 插入 $$$S$$$ 中。那么$$$S=\{3\}$$$,所以响应是$$$|S|=1$$$。 请注意,集合 $$$S$$$ 中的元素不允许重复。
A 1 3该解决方案的结论是 $$$k=1$$$ 和 $$$c=3$$$。
2$$$n=2$$$。隐藏的整数值为 $$$k=2$$$ 和 $$$c=2$$$。
1最初,$$$S = \{1\}$$$。
我02将 $$$f(0)=0\,|\,2=2$$$ 插入 $$$S$$$ 中。那么$$$S=\{1,2\}$$$,所以响应是$$$|S|=2$$$。
问题21当$$$z$$$为$$$2$$$时,满足$$$z\in S$$$和$$$z\geq 2$$$,因此响应为$$$1$$$。
问题12当$$$z$$$为$$$1$$$或$$$2$$$时,满足$$$z\in S$$$和$$$z\geq 1$$$,因此响应为$$$2$$$。
问02当$$$z$$$为$$$1$$$或$$$2$$$时,满足$$$z\in S$$$和$$$z\geq 0$$$,因此响应为$$$2$$$。
我 33将 $$$f(3)=3\,|\,2=3$$$ 插入 $$$S$$$ 中。那么$$$S=\{1,2,3\}$$$,所以响应是$$$|S|=3$$$。
A 2 2该解决方案的结论是 $$$k=2$$$ 和 $$$c=2$$$。
2$$$n=2$$$。隐藏的整数值为 $$$k=3$$$ 和 $$$c=1$$$。
1最初,$$$S = \{1\}$$$。
我 12将 $$$f(1)=1\oplus 1=0$$$ 插入 $$$S$$$ 中。那么$$$S=\{0,1\}$$$,所以响应是$$$|S|=2$$$。
我02将 $$$f(1)=0\oplus 1=1$$$ 插入 $$$S$$$ 中。那么$$$S=\{0,1\}$$$,所以响应是$$$|S|=2$$$。 请注意,集合 $$$S$$$ 中的元素不允许重复。
A 3 1该解决方案的结论是 $$$k=3$$$ 和 $$$c=1$$$。

示例输入和输出中的空行只是为了更好的可读性;您不需要在解决方案中输出它们。

请注意,在示例中,给定的查询实际上不足以唯一地确定值;它们仅用于说明输入/输出格式。