官方题解。来源：清华大学学生算法协会仓库

CRT或是简单枚举即可得到答案 $83$

$\newcommand{\binom}[2]{{#1 \choose #2}}$

$\binom{n+2-k+2i}{m+5}$

$\require{mhchem}$

$\ce{2KMnO4 ->[点燃][] K2MnO4 + MnO2 + O2 ^}$

123

【题目背景】

这是一道交互题。

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】

见选手目录下的 milli/milli2.in 与 milli/milli2.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$。

【评分方式】

注意：选手不应当通过非法方式获取交互库的内部信息，如直接与标准输入、输出流进行交互。