题目描述

题目译自 CEOI 2024 Day1 T2「COVID tests」

亚当的学校最近爆发了新一波 COVID 疫情。为了防止疫情进一步蔓延，学校决定用唾液抗原检测试剂对所有学生进行检测。

由于老师们很久没用过这些试剂了，亚当自告奋勇地成为了检测志愿者。他拿到了来自 $N$ 个学生的唾液样本（出于隐私保护，他只能看到编号从 $0$ 到 $N-1$ 的标识符），他的任务是确定哪些样本呈阳性。

然而，亚当很快意识到，挨个检测所有学生的样本实在太耗时费力了。他灵机一动，想到了一种比逐个检测更巧妙的方法。如果他将部分样本混合在一起进行检测，他就能知道整个混合物是全部阴性，还是至少有一个阳性。这样一来，他就可以通过这种方式减少所需的检测次数！

每个样本的唾液量都足够进行多次检测。而且，这些检测试剂非常精准，同一个样本绝不会出现不同的检测结果。

在这样的条件下，亚当希望优化检测流程，尽量减少使用的检测次数。但是他目前正在进行检测，所以优化过程就交给你啦！

通过当地的统计数据，亚当了解到任何一个样本呈阳性的概率都等于 $P$，并且一个样本是阳性还是阴性不会影响其他样本的检测结果。也许你可以利用这些信息来帮助亚当优化检测方案？

输入格式

这是一道交互题。

你的程序将会处理若干个测试数据。每个测试数据（即程序的一次运行）中，你需要解决 $T$ 个不同的场景。所有场景中，学生数量 $N$ 和阳性样本概率 $P$ 都保持不变，但是哪些学生的样本呈阳性（很可能）在每个场景中都会不同。

你可以自己实现交互协议，也可以使用提供的模板。你可以在「文件」中找到名为 template.cpp 的附件，它就是提供的模板。

首先，你的程序应该从标准输入读取一行，包含空格隔开的三个整数 $N, P, T$，分别表示学生数量、阳性样本概率和场景数量。

然后，程序可以向标准输出输出询问信息。每个询问信息应该单独占一行，格式为 Q、空格和一个长度为 $N$ 的字符串 $s$。字符串 $s$ 中的每个字符 $s_i$ 都为 1 或 0，1 表示应该将第 $i$ 个学生的样本加入混合物进行检测，0 表示不加入。输出完询问信息后，程序需要刷新标准输出缓冲区，然后从标准输入读取一个字符。这个字符会是 P（表示混合物中至少有一个样本呈阳性）或 N（表示混合物中所有样本均为阴性）。

程序也可以输出最终答案。答案信息应该单独占一行，格式为 A、空格和一个长度为 $N$ 的字符串 $s$。字符串 $s$ 中的每个字符 $s_i$ 都为 1 或 0，1 表示第 $i$ 个学生的样本呈阳性，0 表示呈阴性。输出完答案信息后，程序同样需要刷新标准输出缓冲区，然后从标准输入读取一个字符。

如果读取到的字符为 C，则表示你的答案正确。在这种情况下，程序可以开始处理下一个场景的询问，或者如果是第 $T$ 个场景的答案，则程序可以退出。

如果读取到的字符为 W，则表示你的答案错误。程序应该立即退出。

请注意，在收到 W 后退出对于交互器给出正确的反馈非常重要。如果你的程序继续运行，它可能会崩溃或收到其他错误的判定。

交互器不会根据你的程序运行结果来动态调整测试数据。这意味着每个样本的阳性与否会在程序运行之前就确定好。并且，每个样本的阳性与否都是通过公平的随机数生成器，以概率 $P$ 独立决定的。

如果你使用 template.cpp 中的交互协议实现，你需要实现函数 std::vector<bool> find_positive()。这个函数会在每个场景中被调用一次。它需要返回一个长度为 $N$ 的布尔型向量，其中第 $i$ 个元素为 true 当且仅当第 $i$ 个学生的样本呈阳性。

实现过程中，你可以使用函数 bool test_students(std::vector<bool> mask)。这个函数可以对部分样本进行混合检测。它唯一的参数是一个长度为 $N$ 的布尔型数组，其中第 $i$ 个元素为 true 表示应该将第 $i$ 个样本加入混合物进行检测。该函数返回 true 当且仅当混合物中至少有一个样本呈阳性。

你也可以使用全局变量 N 和 P，它们分别代表着总学生人数和阳性样本概率。你可以在 main 函数中，首次调用 scanf 之后进行初始化操作。

示例输入	示例输出
10 0.4 2
	Q 1000000000
P
	Q 0000001000
P
	Q 0000000001
P
	Q 0111110110
N
	A 1000001001
C
	A 0000000000
W

提示

本题分为两个子任务。

Subtask 1 (10 分)

• 学生总数 $N = 1000$
• 场景数 $T = 1$
• 阳性样本概率 $P$ 在 $0$ 到 $1$ 之间

如果程序能正确回答并且每个测试数据的询问次数不超过 $2$ 倍的总学生人数 $2N$，则认为该程序通过测试。

Subtask2 (90 分)

• 学生总数 $N = 1000$
• 场景数 $T = 300$
• 阳性样本概率 $P$ 在 $0.001$ 到 $0.2$ 之间

该子任务具有部分分。

如果你的程序在任何场景的回答错误，你将得 $0$ 分。否则，每个测试数据的得分将基于平均询问次数计算。一般来说，询问次数越少，得分越高。记作程序在所有场景的平均询问次数为 $Q$，四舍五入到小数点后一位。对于每个测试数据，我们计算了一个值 $F$（见下文）。给定测试数据的得分将根据以下规则计算：

• 如果 $Q > 10$ 倍的 $F$，你将得 $0$ 分 (错误答案)。
• 如果 $F < Q \leq 10$ 倍的 $F$，得分由以下公式计算：$$90 \cdot \frac{F}{F + 4 \cdot (Q-F)}$$
• 如果 $Q \leq F$，你将获得满分 $90$ 分。

你的程序将会在不同 $P$ 值的测试数据上进行评分。你将获得的总分是所有测试数据（所有概率 $P$）中的最低分。

测试数据如下：

$P$	$F$
$0.001$	$15.1$
$0.005256$	$51.1$
$0.011546$	$94.9$
$0.028545$	$191.5$
$0.039856$	$246.3$
$0.068648$	$366.2$
$0.104571$	$490.3$
$0.158765$	$639.1$
$0.2$	$731.4$

交互器会为每个测试数据提供反馈。这些反馈将包括你在得分非零的测试数据上的平均询问次数 $Q$。