UOJ Logo Universal Online Judge

UOJ

#568. 【IOI2020】Mushrooms

附件下载 统计

研究蘑菇的专家安德鲁在研究新加坡的本地蘑菇。

作为研究的一部分,安德鲁采集了 $n$ 个蘑菇,编号为 $0$ 到 $n - 1$。每个蘑菇均为两种蘑菇种类之一,称为 $A$ 或 $B$。

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

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

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

实现细节

你需要实现以下函数:

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]$ 属于不同种类。
  • 该函数最多可以被调用 $20000$ 次。
  • 在对函数 use_machine 的所有调用中,所有被传到该函数 use_machine 的 $x$ 的总长度不能超过 $100000$。

例子

例一

考虑以下场景:有 $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$。

例二

考虑一个例子:有 $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$。

评测程序示例

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

  • 第 1 行:$n$
  • 第 2 行: $s[0] s[1] \dots s[n-1]$

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

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

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

如果你要提交 hack,一种格式是:

  • 第 1 行:plain (仅一个字符串)
  • 第 2 行:$n$
  • 第 3 行: $s[0] s[1] \dots s[n-1]$

限制与约定

$2 \le n \le 20000$。

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

条件 得分
$20000 < Q$ $0$
$10010 < Q \le 20000$ $10$
$904 < Q \le 10010$ $25$
$226 < Q \le 904$ $\left\lfloor \frac{226}{Q} \cdot 100 \right\rfloor$
$Q \le 226$ $100$

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

时间限制:$2\texttt{s}$

空间限制:$2\texttt{GB}$

下载

样例及测评库下载