这是问题的困难版本。您可以在 Div 中找到简单版本。 2 竞赛。两个版本的区别仅在于您可以邀请朋友品尝咖啡的次数。
这是一个交互问题。
您正在考虑搬到另一个城市,您的一位朋友已经住在那里。这个城市有 $$$n$$$ 咖啡馆,其中 $$$n$$$ 是 2 的幂。第 $$$i$$$ 咖啡馆生产单一品种的咖啡 $$$a_i$$$。
作为一名咖啡爱好者,在决定搬家或搬家之前,您想知道这个城市生产的不同品种咖啡的数量$$$d$$$。
您不知道值 $$$a_1, \ldots, a_n$$$。幸运的是,您的朋友的内存大小为 $$$k$$$,其中 $$$k$$$ 是 2 的幂。
每天一次,你可以让他品尝一杯$$$c$$$咖啡馆生产的咖啡,他会告诉你在过去的$$$k$$$天里他是否品尝过类似的咖啡。
您还可以要求他服用可以重置记忆的药物。他会忘记之前喝过的所有咖啡。您最多可以重置他的记忆 $$$30\ 000$$$ 次。
更正式地说,你朋友的内存是一个队列$$$S$$$。对 Cafe $$$c$$$ 进行查询将:
- 告诉你 $$$a_c$$$ 是否在 $$$S$$$ 中;
- 在$$$S$$$后面添加$$$a_c$$$;
- 如果 $$$|S| > k$$$,弹出$$$S$$$前面的元素。
执行重置请求将从 $$$S$$$ 中弹出所有元素。
您的朋友总共最多可以品尝 $$$\dfrac{3n^2}{2k}$$$ 杯咖啡。求多样性 $$$d$$$(数组 $$$a$$$ 中不同值的数量)。
请注意,要求您的朋友重置记忆并不会计入您要求您的朋友品尝一杯咖啡的次数。
在某些测试用例中,交互器的行为是自适应的。这意味着数组 $$$a$$$ 在交互开始之前可能没有固定,并且可能取决于您的查询。保证在交互的任何时刻,至少有一个数组 $$$a$$$ 与迄今为止给出的所有答案一致。
输入
第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le k \le n \le 1024$$$、$$$k$$$ 和 $$$n$$$ 是 2 的幂)。
保证 $$$\dfrac{3n^2}{2k} \le 15\ 000$$$。
互动
您通过阅读 $$$n$$$ 和 $$$k$$$ 开始交互。
- 要请你的朋友品尝一杯由咖啡馆 $$$c$$$ 生产的咖啡,在单独的一行输出中? $$$c$$$其中$$$c$$$必须满足$$$1 \le c \le n$$$。不要忘记冲水,以获得答案。作为回应,您将收到一个字母 Y(是)或 N(否),告诉您品种 $$$a_c$$$ 是否是他记忆中最后的 $$$k$$$ 咖啡品种之一。
- 要重置您朋友的记忆,请在单独的行中输出大写的单个字母 R。您最多可以执行此操作 $$$30\ 000$$$ 次。
- 当你确定不同咖啡品种的数量 $$$d$$$ 时,输出! $$$d$$$
如果您的查询无效,您询问的类型超过 $$$\frac{3n^2}{2k}$$$ 查询?或者您询问了超过 $$$30\ 000$$$ 类型的 R 查询,程序将打印字母 E 并完成交互。您将收到错误答案的判决。确保立即退出,以避免得到其他判决。
打印查询后,不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:
- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。
黑客格式
第一行应包含“fixed”一词
第二行应包含两个整数 $$$n$$$ 和 $$$k$$$,以空格分隔($$$1 \le k \le n \le 1024$$$、$$$k$$$ 和 $$$n$$$ 是 2 的幂)。
必须满足 $$$\dfrac{3n^2}{2k} \le 15\ 000$$$。
第三行应包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$,以空格分隔 ($$$1 \le a_i \le n$$$)。
示例
输入 #1
4 2 N N Y N N N N
输出 #1
? 1 ? 2 ? 3 ? 4 R ? 4 ? 1 ? 2 ! 3
输入 #2
8 8 N N N N Y Y
输出 #2
? 2 ? 6 ? 4 ? 5 ? 2 ? 5 ! 6
注意
在第一个示例中,数组为 $$$a = [1, 4, 1, 3]$$$。该市生产 $$$3$$$ 不同品种的咖啡($$$1$$$、$$$3$$$ 和 $$$4$$$)。
您朋友连续品尝的咖啡品种为 $$$1, 4, \textbf{1}, 3, 3, 1, 4$$$(粗体答案对应 Y 答案)。注意两者之间? 4问,有一个复位内存请求R,所以回答第二个? 4问是N。如果没有重置内存请求,那么第二个问题的答案是什么? 4问是Y。
在第二个示例中,数组为 $$$a = [1, 2, 3, 4, 5, 6, 6, 6]$$$。该市生产 $$$6$$$ 不同品种的咖啡。
您的朋友连续品尝的咖啡品种为 $$$2, 6, 4, 5, \textbf{2}, \textbf{5}$$$。