题目描述

译自 NOISG 2023 Final T5. Toxic Gene

兔子本森的飞机被毒性细菌侵袭，他必须进行调查！

本森有 $n$ 种细菌，每种细菌恰好属于以下三种类型之一：普通（Regular）、强韧（Strong）、毒性（Toxic）。其中 $t$ 种为毒性细菌。保证至少有 $1$ 种毒性细菌，即 $t \geq 1$。注意，本森不知道 $t$ 的值。

本森希望确定每种细菌的类型。为了分析细菌，他可以将细菌样本放入一台机器中。他可以指定每种细菌的种类，并可将任意数量（包括 $0$）的每种细菌加入机器，形成一个样本。由于空间限制，样本中的细菌总数不得超过 $300$。

三种细菌类型的特性如下：

• 普通细菌：若样本中没有毒性细菌，则存活；若样本中至少有一种毒性细菌，则死亡。
• 强韧细菌：总是存活。
• 毒性细菌：产生毒素，杀死样本中所有非强韧细菌。毒性细菌本身总是死亡。

选择样本后，机器会告诉本森总共有多少细菌存活。每次使用机器都需要时间，而本森时间有限，最多只能使用机器 $600$ 次。帮助本森以尽可能少的样本确定每种细菌是普通、强韧还是毒性。

实现细节

这是一个交互题。不得从标准输入读取数据或向标准输出写入数据。

你需要实现以下函数：

void determine_type(int n)

此函数在每个测试点中最多被调用 $100$ 次。每次调用可能包含普通、强韧和毒性细菌的不同组合。对于每个测试点，你必须在时间和内存限制内解决所有函数调用。

允许调用以下函数：

int query_sample(std::vector<int> species)
void answer_type(int x, char c)

函数 query_sample 接受一个一维数组 species，描述程序选择的样本中每种细菌的种类。species 的大小不得超过 $300$。此外，传递给 query_sample 的数组不会被修改。换句话说，调用 query_sample 后，数组 species 保持不变。

函数 answer_type 接受一个整数 $x$ 和一个字符 $c$。当程序确定种类 $x$ 的细菌类型为 $c$ 表示的类型时，可调用此函数。$c$ 可以是 R、S 或 T，分别表示普通、强韧和毒性细菌类型。程序必须为所有细菌种类调用此函数。

以下情况将导致答案错误判定并立即终止程序：

• 若 query_sample 或 answer_type 使用无效参数调用。
• 若 answer_type 错误识别细菌类型。
• 若 determine_type 终止时，未通过 answer_type 识别所有 $n$ 种细菌。
• 若在一次 determine_type 调用中，query_sample 被调用超过 $600$ 次。

请注意，此题的交互器不是自适应的。这意味着每个测试点的答案是固定的，在程序执行期间不会改变。

样例

假设 $n=5$。细菌种类 $1$ 和 $2$ 为毒性，种类 $3$ 和 $4$ 为普通，种类 $5$ 为强韧。对应的字符串为 TTRRS。

你的函数将以下列参数调用：

determine_type(5)

可能的交互如下：

• query_sample([1,2,3,4,5]) = 1

此查询使用每种细菌各一个样本。只有细菌 $5$ 存活，因此交互器返回 $1$。

• query_sample([3,3,4,5]) = 4

此查询使用两个细菌种类 $3$ 的样本和各一个细菌种类 $4$ 和 $5$ 的样本。由于没有毒性细菌，所有样本存活，交互器返回 $4$。

此时，程序认为已获得足够信息来确定每种细菌的类型，并进行以下 $5$ 次调用：

• answer_type(1, 'T')
• answer_type(2, 'T')
• answer_type(3, 'R')
• answer_type(4, 'R')
• answer_type(5, 'S')

这些调用不返回任何值。由于程序正确识别了所有 $n=5$ 种细菌类型，且使用的查询次数不超过 $600$ 次，此测试点将被视为正确。

请注意，此示例测试用例不满足下面的输入限制，仅用于测试目的，无需解决此样例即可获得满分。

评分

程序将在满足以下限制的输入数据上进行评测：

• $n=300$
• $1 \leq t \leq 30$

此题的得分取决于在所有测试点中所有 determine_type 调用中使用的最大查询次数，记为 $m$：

• 若 $m > 600$，得分为 $0$。
• 若 $340 < m \leq 600$，得分为 $2 + 7 \times \frac{600-m}{260}$。
• 若 $275 < m \leq 340$，得分为 $9 + 15 \times \frac{340-m}{65}$。
• 若 $190 < m \leq 275$，得分为 $24 + 22 \times \frac{275-m}{85}$。
• 若 $150 < m \leq 190$，得分为 $46 + 54 \times \frac{190-m}{40}$。
• 若 $m \leq 150$，得分为 $100$。

测试

你可以在「文件」中下载交互器文件、头文件和代码模板。提供两个输入文件供测试：sample1.txt 对应样例，sample2.txt 包含 $tc=100$ 和 $n=300$ 的测试点。请使用脚本 compile.sh 编译和运行你的代码进行测试。

输入格式

第一行包含两个整数 $tc$ 和 $n$，$tc$ 为 determine_type 的调用次数。

接下来的 $tc$ 行，每行包含一个长度为 $n$ 的字符串（由 R、S 或 T 组成），按顺序描述所有细菌种类的类型。

输出格式

每次 determine_type 调用的结果表示为一个整数，另起一行输出。

若程序进入任何答案错误的情况，交互器输出 $-1$ 并立即终止。剩余的 determine_type 调用将不会进行。

否则，交互器输出 query_sample 的调用次数。