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 翻译