题目描述

注意：在 LibreOJ 上，由于语言限制，目前只支持以下语言的提交：

• C++ 11
• C++ 11 (Clang)
• C++ 11 (NOI)
• C++ 17
• C++ 17 (Clang)

研究蘑菇的专家安德鲁在研究新加坡的本地蘑菇。作为研究的一部分，安德鲁采集了 $n$ 个蘑菇，编号为 $0$ 到 $n-1$。每个蘑菇均为两种蘑菇种类之一，称为 A 或 B。

安德鲁知道蘑菇 $0$ 属于种类 $A$，但是由于这两种蘑菇看起来很相似，他不知道蘑菇 $1$ 到 $n-1$ 属于哪一种。

幸运的是，安德鲁的实验室里有一台机器可以帮助他。在使用这台机器时，需要将两个或者多个蘑菇放到机器里，并摆成一排（以任意顺序），然后打开机器。接下来，这台机器会计算所有不属于同一种类的相邻蘑菇对的个数。例如，如果你把种类为 $[A,B,B,A]$ 的蘑菇（按照这个顺序）放到机器中，结果应该是 $2$。

但是，因为机器操作非常昂贵，机器只能使用有限的次数。此外，在机器的所有使用中，放置到机器中的蘑菇总数不能超过 $10^5$。请使用这台机器帮助安德鲁来数一数他采集了多少个种类为 $A$ 的蘑菇。

实现细节

在程序开始，你需要引入 mushrooms.h 库。

你需要实现以下函数：

int count_mushrooms(int n)

• $n$：安德鲁采集到的蘑菇数量。
• 该函数应该被调用恰好一次，而且要返回种类为 A 的蘑菇的个数。

以上函数可以调用以下函数：

int use_machine(int[] x)

• $x$：一个长度介于 $2$ 和 $n$ 的数组（包括 $2$ 和 $n$），按顺序给出放在机器中的蘑菇的编号。
• $x$ 的元素必须是在 $0$ 到 $n-1$ 之间（包括 $0$ 和 $n-1$）互不相同的整数。
• 假设数组 $x$ 的长度为 $d$。那么，此函数返回不同的下标 $j$ 的个数，满足 $0\le j\le d-2$ 并且 $x_j$ 和 $x_{j+1}$ 属于不同种类。
• 该函数最多可以被调用 $2\times 10^4$ 次。
• 在对函数 use_machine 的所有调用中，所有被传到该函数 use_machine 的 $x$ 的总长度不能超过 $10^5$。

评测程序示例

评测程序示例读入一个整数数组 $s$，该数组给出了蘑菇的种类。对于所有 $0\le i\le n-1$，$s_i=0$ 表示蘑菇 $i$ 的种类是 A，$s_i=1$ 表示蘑菇 $i$ 的种类是 B。评测程序示例读取如下格式的输入数据：

• 第 $1$ 行：$n$
• 第 $2$ 行：$s_0\ s_1\ \ldots \ s_{n-1}$

评测程序示例的输出为如下格式：

• 第 $1$ 行：count_mushrooms 的返回值。
• 第 $2$ 行：调用 use_machine 的次数。

注意评测程序示例不是自适应的。

样例

样例输入 1

3
0 1 1

样例说明 1

考虑以下场景：有 $3$ 个蘑菇，种类依次为 $[A,B,B]$。函数 count_mushrooms 用以下方式调用：

count_mushrooms(3)

该函数可以调用 use_machine([0, 1, 2])，在该场景下调用返回 $1$。函数接着调用 use_machine([2, 1])，该调用返回 $0$。

此时，已经有足够的信息来推出只有 $1$ 个 A 类蘑菇。所以，函数 count_mushrooms 应该返回 $1$。

样例输入 2

4
0 1 0 0

样例说明 2

考虑一个例子：有 $4$ 个蘑菇，种类依次为 $[A,B,A,A]$。 函数 count_mushrooms 被调用如下：

count_mushrooms(4)

该函数可以调用 use_machine([0, 2, 1, 3])，该调用返回 $2$。接着调用 use_machine([1, 2])，该调用返回 $1$。

此时，已有足够的信息推出：有 $3$ 个 A 类蘑菇。因此，函数 count_mushrooms 应该返回 $3$。

数据范围与提示

对于全部数据，保证 $2\le n\le 2\times 10^4$。

计分

在所有测试用例中，如果对函数 use_machine 的调用不符合上面所述的要求，或者 count_mushrooms 的返回值不正确，你的解答得分将为 $0$。否则，令 $Q$ 为所有测试样例中对函数 use_machine 的最大调用次数。那么，得分将按照以下表格进行计算：

条件	得分
$20\ 000<Q$	$0$
$10\ 010<Q\le 20\ 000$	$10$
$904<Q\le 10\ 010$	$25$
$226<Q\le 904$	$\frac{226}{Q}\cdot 100$
$Q\le 226$	$100$

在有些测试用例上，评测程序的行为是自适应的。也就是说，在这些测试用例中，评测程序并没有一个固定的蘑菇种类序列。相反，评测程序中所给出的回答可能依赖于此前对 use_machine 的调用。但是可以保证，评测程序中所给出的回答满足：在每次交互之后，至少存在一个蘑菇种类序列，它能够与当前所给出过的所有回答都相符。