← 返回题目列表

Codeforces · 1543/D2

D2. RPD 和说唱表(硬版)

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

这是问题的困难版本。唯一的区别是这里$$$2\leq k\leq 100$$$。只有当问题的两个版本都得到解决时,你才能进行黑客攻击。

这是一个交互问题!

每个十进制数都有一个等价的 $$$k$$$ 基数。 $$$k$$$ 基数的各个数字称为 $$$k$$$-its。我们将两个 $$$k$$$-其 $$$a$$$ 和 $$$b$$$ 的 $$$k$$$-itwise XOR 定义为 $$$(a + b)\bmod k$$$。

两个基本 $$$k$$$ 数字的 $$$k$$$-itwise XOR 等于通过对其相应的 $$$k$$$-it 进行 $$$k$$$-itwise XOR 所形成的新数字。两个十进制数 $$$a$$$ 和 $$$b$$$ 的 $$$k$$$-itwise XOR 由 $$$a\oplus_{k} b$$$ 表示,并且等于 $$$a$$$ 和 $$$b$$$ 的基本 $$$k$$$ 表示的 $$$k$$$-itwise XOR 的十进制表示形式。除非另有说明,以下声明中使用的所有其他数字均为十进制。

您已经侵入了罗克波特警察局 (RPD) 的犯罪数据库,也称为犯罪记录表。但为了访问它,您需要密码。你不知道,但你很确定它位于 $$$0$$$ 和 $$$n-1$$$ 之间(包括 $$$0$$$ 和 $$$n-1$$$)。所以,你决定猜一猜。幸运的是,您最多可以尝试 $$$n$$$ 次而不会被系统阻止。但该系统是自适应的。每次您猜错时,它都会更改密码。具体来说,如果猜测之前的密码是$$$x$$$,而您猜到了不同的数字$$$y$$$,则系统将密码更改为数字$$$z$$$,使得$$$x\oplus_{k} z=y$$$。猜测密码并闯入系统。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1\leq t\leq 10\,000$$$) 表示测试用例的数量。 $$$t$$$ 测试用例如下。

每个测试用例的第一行包含两个整数 $$$n$$$ ($$$1\leq n\leq 2\cdot 10^5$$$) 和 $$$k$$$ $$$(2\leq k\leq 100)$$$。

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

互动

对于每个测试用例,首先读取两个整数 $$$n$$$ 和 $$$k$$$。然后您最多可以提出 $$$n$$$ 查询。

对于每个查询,打印单个整数 $$$y$$$ ($$$0\leq y\leq 2\cdot 10^7$$$)。令当前密码为$$$x$$$。之后,读取一个整数$$$r$$$。

如果 $$$x=y$$$,您将读取 $$$r=1$$$ 并且测试用例已解决。然后您必须继续解决剩余的测试用例。

否则,您将读取$$$r=0$$$。此时密码更改为数字$$$z$$$,使得$$$x\oplus_{k} z=y$$$。

打印查询后,不要忘记输出行尾并刷新输出。否则,您将得到超出空闲限制的判决。

为此,请使用:

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

如果您提出无效查询或超过 $$$n$$$ 查询,您将读取 $$$r=-1$$$ 并且您将收到错误答案判决。确保立即退出以避免意外的判决。

请注意,交互器是自适应的。也就是说,原始密码一开始并不是固定的,可能取决于您的查询。但可以保证在任何时刻至少有一个初始密码,以便所有查询的答案都是一致的。

黑客:

要使用 hack,请使用以下测试格式:

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

每个测试用例的第一行也是唯一一行应包含两个整数 $$$n$$$ ($$$1\leq n\leq 2\cdot 10^5$$$) 和 $$$k$$$ ($$$2\leq k\leq 100$$$) 分别表示查询数和基数。最佳原始密码由自适应交互器自动决定。

您必须确保所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。

示例

输入 #1

2
5 2

0

0

1
5 3

0

0

1

输出 #1

3

4

5


1

4

6

注意

测试用例1:

在本例中,隐藏密码是 $$$2$$$。

第一个查询是 $$$3$$$。它不等于当前密码。因此,返回$$$0$$$,并且由于$$$2\oplus_2 1=3$$$,密码更改为$$$1$$$。

第二个查询是$$$4$$$。它不等于当前密码。因此,返回$$$0$$$,并且由于$$$1\oplus_2 5=4$$$,密码更改为$$$5$$$。

第三个查询是$$$5$$$。它等于当前密码。因此,$$$1$$$ 被返回,工作就完成了。

测试用例2:

在本例中,隐藏密码是 $$$3$$$。

第一个查询是 $$$1$$$。它不等于当前密码。因此,返回$$$0$$$,并且由于$$$3\oplus_3 7=1$$$,密码更改为$$$7$$$。 $$$[3=(10)_3$$$、$$$7=(21)_3$$$、$$$1=(01)_3$$$ 和 $$$(10)_3\oplus_3 (21)_3 = (01)_3]$$$。

第二个查询是$$$4$$$。它不等于当前密码。因此,返回$$$0$$$,并且由于$$$7\oplus_3 6=4$$$,密码更改为$$$6$$$。 $$$[7=(21)_3$$$、$$$6=(20)_3$$$、$$$4=(11)_3$$$ 和 $$$(21)_3\oplus_3 (20)_3 = (11)_3]$$$。

第三个查询是$$$6$$$。它等于当前密码。因此,$$$1$$$ 被返回,工作就完成了。

请注意,使用这些初始密码只是为了便于解释。实际上,评分器的行为可能会有所不同,因为它具有适应性。