CF1291F.Coffee Varieties (easy version)

这是该问题的简单版本。你可以在 Div. 1 比赛中找到难度更高的版本。两个版本的区别仅在于你可以让你的朋友品尝咖啡的次数不同。

这是一个交互式问题。

你正在考虑搬到另一个城市，你的一个朋友已经住在那里。这个城市有 $n$ 家咖啡馆，其中 $n$ 是 $2$ 的幂次方。第 $i$ 家咖啡馆只生产一种咖啡，种类为 $a_i$。

作为咖啡爱好者，在决定是否搬家之前，你想知道这个城市一共有多少种不同的咖啡品种 $d$。

你并不知道 $a_1, \ldots, a_n$ 的具体数值。幸运的是，你的朋友有一个容量为 $k$ 的记忆（$k$ 也是 $2$ 的幂次方）。

你每天可以让他品尝一家咖啡馆 $c$ 生产的咖啡，他会告诉你在过去 $k$ 天内是否品尝过相同的咖啡。

你还可以让他服用一种药物来重置他的记忆。他会忘记之前品尝过的所有咖啡。你最多可以重置他的记忆 $30\,000$ 次。

更正式地说，你朋友的记忆是一个队列 $S$。对咖啡馆 $c$ 进行一次查询会：

• 告诉你 $a_c$ 是否在 $S$ 中；
• 将 $a_c$ 加入 $S$ 的末尾；
• 如果 $|S| > k$，则弹出 $S$ 的队首元素。

进行一次重置操作会清空 $S$ 中的所有元素。

你的朋友最多可以总共品尝 $\dfrac{2n^2}{k}$ 杯咖啡。请你求出不同咖啡品种的数量 $d$（即数组 $a$ 中不同数值的个数）。

注意，重置记忆的操作不计入你让朋友品尝咖啡的总次数限制。

在某些测试点中，交互器的行为是自适应的。这意味着数组 $a$ 在交互开始前可能不是固定的，并且可能会根据你的查询动态变化。保证在交互的任何时刻，至少存在一个数组 $a$ 与目前所有回答一致。

第一行包含两个整数 $n$ 和 $k$（$1 \le k \le n \le 1024$，$k$ 和 $n$ 都是 $2$ 的幂次方）。

保证 $\dfrac{2n^2}{k} \le 20\,000$。

你通过读取 $n$ 和 $k$ 开始交互。

• 若要让你的朋友品尝第 $c$ 家咖啡馆的咖啡，在单独一行输出 ? c，其中 $1 \le c \le n$。不要忘记刷新输出，以获得回复。

  你会收到一个单独的大写字母 Y（是）或 N（否），表示该咖啡品种 $a_c$ 是否在他最近 $k$ 次记忆中出现过。

• 若要重置你朋友的记忆，在单独一行输出大写字母 R。你最多可以进行 $30\,000$ 次重置操作。

• 当你确定了不同咖啡品种的数量 $d$ 时，输出 ! d。

如果你的查询无效、? 查询次数超过 $\frac{2n^2}{k}$，或 R 查询次数超过 $30\,000$，程序会输出字母 E 并结束交互。你会收到 Wrong Answer 判定。请确保立即退出以避免其他判定。

每次输出查询后不要忘记输出换行并刷新输出，否则会因超时被判为 Idleness limit exceeded。具体刷新方法如下：

• C++：fflush(stdout) 或 cout.flush()
• Java：System.out.flush()
• Pascal：flush(output)
• Python：stdout.flush()
• 其它语言请查阅相关文档。

Hack 格式

第一行应为单词 fixed。

第二行包含两个整数 $n$ 和 $k$，用空格分隔（$1 \le k \le n \le 1024$，$k$ 和 $n$ 都是 $2$ 的幂次方）。

必须满足 $\dfrac{2n^2}{k} \le 20\,000$。

第三行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$，用空格分隔（$1 \le a_i \le n$）。

在第一个样例中，数组为 $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}$。

由 ChatGPT 4.1 翻译