4375. 蜜丽

【题目背景】

这是一道交互题。

LikablePie79015 最近频繁的追忆过去，一天晚上 LikablePie79015 梦到了十几年前爱看的动画片，这让 LikablePie79015 追忆起了美好的时光。

在梦里，LikablePie79015 穿着 Milli 变化的衣服，手拿 Geo 的 Shape Splitter，坐着由 Bot 驾驶的 UmiCar，唱着《开心超人》主题曲，和螺小诺、螺小西和可乐兔一起畅游在小伶姐姐的玩具世界里。

突然，LikablePie79015 面前突然出现了一个巨大的草丛方阵。

【题目描述】

LikablePie79015 急需要穿过这个草丛方阵，但是其中一些地方被 TroubleMakers 埋下了陷阱！LikablePie79015 当然不想踩到这些陷阱里！

草丛方阵是由 $n$ 行 $m$ 列个草丛组成的（$n - 2 \lt m$），并且已知：

1. 第一行和最后一行没有陷阱。
2. 每一行有且仅有一个草丛有陷阱。
3. 每一列至多有一个草丛有陷阱。

LikablePie79015 可以进行任意次行动，对于每一次行动：

1. LikablePie79015 选择第一行任意一个草丛作为起点。
2. LikablePie79015 从起点开始沿上、下、左、右任意行走。
3. 若 LikablePie79015 走到了陷阱，则会被传送到第一行开始新一轮行动。
4. 若 LikablePie79015 走到了最后一行，行动结束，LikablePie79015 成功穿过草丛方阵。

LikablePie79015 希望使用尽量少的行动次数穿过草丛方阵，因此 LikablePie79015 需要你的帮助！

可以认为 LikablePie79015 拥有强大的记忆力，能够记住经过的所有草丛是否有陷阱。

【实现细节】

选手不需要，也不应该实现 main 函数。

选手需要确保提交的程序包含头文件 milli.h，即在程序开头加入以下代码：

#include "milli.h"

选手需要在提交的程序源文件 milli.cpp 中实现以下函数：

void init(int c, int t);

• $c, t$ 分别表示测试点编号与测试数据组数。$c = 0$ 表示该测试点为样例。
• 对于每个测试点，该函数会在程序开始运行时被交互库调用恰好一次。

void milli(int n, int m);

• $n, m$ 表示草丛方阵的大小。
• 选手需要在函数内实现若干次行动以及控制 LikablePie79015 的走动。
• 对于每个测试点，该函数会被交互库调用恰好 $t$ 次。

选手可以调用以下函数：

void StartMazing(int i);

• 选手必须在每次行动开始之前调用该函数，否则该测试点得 $0$ 分。
• $i$ 表示选择从第一行第 $i$ 列开始行动。

int move(int d)

• $d$ 表示这次移动选择的方向，$d=1/2/3/4$ 表示移动方向是上/下/左/右。
• 该函数返回一个整数 $x$：
• 若 $x = 1$，表示移动到了无陷阱的草丛。
• 若 $x = 0$，表示移动到了有陷阱的草丛。注意下次移动前必须调用 StartMazing 函数。
• 若 $x = -1$，表示移动到了最后一行，成功穿过草丛方阵，当前测试数据结束。

注意：在任何情况下，最终测试时所用的交互库运行所需时间均不会超过 $0.1$ 秒，所用内存为固定大小，且均不超过 $64$ MiB。

【测试程序方式】

试题目录下的 grader.cpp 是交互库参考实现，最终测试时所用的交互库实现与该参考实现有所不同，因此选手的解法不应该依赖交互库实现。

选手可以在本题目录下使用如下命令编译得到可执行程序：

g++ grader.cpp milli.cpp -o milli -std=gnu++14

【输入格式】

对于编译得到的可执行程序：

• 可执行文件将从标准输入读入以下格式的数据：
• 输入的第一行包含两个非负整数 $c, t$，分别表示测试点编号和测试数据组数。
• 接下来依次为每组测试数据，对于每组测试数据：
• 第一行包含两个正整数 $n, m$，表示草丛方阵的大小。
• 第二行包含 $n - 2$ 个正整数 $p_2, p_3, \cdots, p_{n-1}$，其中 $p_i$ 表示第 $i$ 行的陷阱在第 $p_i$ 列草丛中。

【输出格式】

可执行文件将输出以下格式的数据至标准输出：

• 对于每组测试数据：
• 第一行为一个字符串：Test Case #[i]:，其中 [i] 会被替换为当前测试数据编号。
• 第二行包含一个字符串，表示测试的结果。其中：
• Correct. 表示选手正确地控制 LikablePie79015 穿过草丛方阵（走到最后一行）。
• Invalid operation: [reason].，表示选手对 move 函数的调用不合法，[reason] 会被替换为具体原因。
• 若结果为 Correct，则第三行包含一个字符串：Function call count: [m]，其中 [m] 会被替换为选手在当前测试数据调用 StartMazing 函数的次数。
• 若所有测试数据的结果均为 Correct，则可执行文件会在最后输出一行字符串：Max function call count: [M].，其中 M 会被替换为选手在所有测试数据中调用 StartMazing 函数的次数的最大值。

【输入样例 1】

0 1
4 3
1 3

【输出样例 1】

Test Case #1:
    Correct
    Function call count: 2
Max function call count: 2

【样例 1 解释】

可能的交互过程：

• 第一次行动：
• 选手调用 StartMazing(1)，选择在第一行第一列开始行动。
• 选手调用 move(2) 并得到返回值 $0$，移动到了陷阱，第一次行动结束。
• 第二次行动：
• 选手调用 StartMazing(2)，选择在第一行第二列开始行动。
• 选手调用 move(2) 并得到返回值 $1$。
• 选手调用 move(2) 并得到返回值 $1$。
• 选手调用 move(2) 并得到返回值 $-1$，成功穿过草丛方阵，第二次行动结束，程序结束。

【输入样例 2】

0 4
8 7
1 2 3 4 5 6
8 7
4 3 5 2 6 1
8 7
6 5 4 3 2 1
8 7
5 7 6 4 3 2

【输出样例 2】

Test case #1:
    Correct.
    Function call count: 2.
Test case #2:
    Correct.
    Function call count: 3.
Test case #3:
    Correct.
    Function call count: 3.
Test case #4:
    Correct.
    Function call count: 3.
Max function call count: 3.

【输入输出样例 3】

见选手目录下的 milli/milli3.in 与 milli/milli3.ans。

【输入输出样例 4】

见选手目录下的 milli/milli4.in 与 milli/milli4.ans。

【下发文件说明】

在本试题目录下：

1. grader.cpp 是提供的交互库参考实现。
2. milli.h 是头文件，选手不用关心具体内容。
3. template_perm.cpp 是提供的示例代码，选手可参考并实现自己的代码。

选手注意对所有下发文件做好备份。最终评测时只测试本试题目录下的 milli.cpp，对该程序以外文件的修改不会影响评测结果。

【数据范围】

对于所有测试数据：

• $t = 10$；
• $3 \le n, m \le 5000$；
• $n - 2 \lt m$。

【评分方式】

注意：

• 选手不应当通过非法方式获取交互库的内部信息，如直接与标准输入、输出流进行交互。此类行为将被视为作弊；
• 最终的评测交互库与样例交互库的实现不同。

若选手出现以下情况，相应测试点得 $0$ 分：

• 编译错误、运行时错误、超过时间限制、超过空间限制。
• 任意测试数据选手未能控制 LikablePie79015 走到最后一行。
• 每次行动之前没有调用 StartMazing 函数。
• 调用 StartMazing 函数后，行动没有结束，再次调用 StartMazing 函数。
• 调用 StartMazing(int i) 时，$i \lt 1$ 或 $i \gt m$。
• 调用 move(int d) 函数时，$d \lt 1$ 或 $d \ge 4$。
• 调用 move 函数后，LikablePie79015 超出草丛方阵的边界。

在上述条件的基础上，设 $M$ 表示选手在所有测试数据中，调用 StartMazing 函数次数的最大值，则程序将获得 $10 \cdot f(M)$ 分，其中 $g$ 的计算方式如下：

$$ f(x)= \begin{cases} 1 & 1 \le x \le 3 \\ \log_{\frac{1}{100}} \frac{1}{10}x + \frac{1}{2} & 4 \le x \le 10 \\ -\frac{1}{49800200}\left(x-10\right)^{2}+\frac{1}{2} & 11 \le x \le 5000 \\ 0 & x \ge 5001 \end{cases} $$

【附件下载】

【来源】

题目中出现的动画片：

1. Team Umizoomi（中译：呜咪123、数学城小兄妹、数学城小姐弟）：Wiki 百度百科；
2. 螺丝钉：CCTV Wiki；
3. 开心超人：百度百科；
4. 不一样的兔子音乐篇：百度百科；
5. 小伶玩具：Bilibili 官方账号。